Burbuļu šķirošanas algoritms ar Python, izmantojot saraksta piemēru

Satura rādītājs:

Anonim

Kas ir burbuļu šķirošana?

Bubble Sort ir šķirošanas algoritms, ko izmanto, lai kārtotu saraksta elementus augošā secībā, salīdzinot divas blakus esošās vērtības. Ja pirmā vērtība ir augstāka par otro, pirmā vērtība ieņem otro vērtību, bet otrā vērtība - pirmo vērtību. Ja pirmā vērtība ir mazāka par otro, tad netiek veikta maiņa.

Šis process tiek atkārtots, līdz visas saraksta vērtības ir salīdzinātas un, ja nepieciešams, mainītas. Katru atkārtojumu parasti sauc par caurlaidi. Pāreju skaits burbuļu kārtošanā ir vienāds ar elementu skaitu sarakstā mīnus viens.

Šajā Bubble Sorting Python apmācībā jūs uzzināsiet:

  • Kas ir burbuļu šķirošana?
  • Burbuļu šķirošanas algoritma ieviešana
  • Optimizēts burbuļu šķirošanas algoritms
  • Vizuālā pārstāvība
  • Python piemēri
  • Kods Paskaidrojums
  • Burbuļu šķirošanas priekšrocības
  • Burbuļu šķirošana Trūkumi
  • Burbuļu šķirošanas sarežģītības analīze

Burbuļu šķirošanas algoritma ieviešana

Mēs sadalīsim ieviešanu trīs (3) posmos, proti, problēmu, risinājumu un algoritmu, ar kuru mēs varam rakstīt kodu jebkurai valodai.

Problēma

Priekšmetu saraksts tiek dots nejaušā secībā, un mēs vēlētos tos sakārtot kārtīgi

Apsveriet šādu sarakstu:

[21,6,9,33,3]

Atrisinājums

Atkārtojiet sarakstu, salīdzinot divus blakus esošos elementus un mainot tos, ja pirmā vērtība ir augstāka par otro.

Rezultātam jābūt šādam:

[3,6,9,21,33]

Algoritms

Burbuļu kārtošanas algoritms darbojas šādi

1. solis. Iegūstiet kopējo elementu skaitu. Iegūstiet kopējo vienumu skaitu norādītajā sarakstā

2. solis. Nosakiet veicamo ārējo piespēļu skaitu (n - 1). Tās garums ir saraksts mīnus viens

3. solis. Veiciet iekšējās caurlaides (n - 1) reizes ārējai pārejai 1. Iegūstiet pirmā elementa vērtību un salīdziniet to ar otro vērtību. Ja otrā vērtība ir mazāka par pirmo, nomainiet pozīcijas

4. solis) Atkārtojiet 3. soli, līdz sasniedzat ārējo pāreju (n - 1). Iegūstiet nākamo elementu sarakstā, pēc tam atkārtojiet procesu, kas tika veikts 3. darbībā, līdz visas vērtības ir ievietotas pareizajā augošā secībā.

5. solis. Atgrieziet rezultātu, kad visas piespēles ir izpildītas. Atgrieziet sakārtotā saraksta rezultātus

6. solis) Optimizēt algoritmu

Izvairieties no nevajadzīgām iekšējām caurlaidēm, ja saraksts vai blakus esošās vērtības jau ir sakārtotas. Piemēram, ja sniegtajā sarakstā jau ir elementi, kas ir sakārtoti augošā secībā, tad mēs varam lauzīt cilpu agri.

Optimizēts burbuļu šķirošanas algoritms

Pēc noklusējuma burbuļu kārtošanas algoritms Python salīdzina visus saraksta vienumus neatkarīgi no tā, vai saraksts jau ir sakārtots vai nē. Ja dotais saraksts jau ir sakārtots, visu vērtību salīdzināšana ir laika un resursu izšķiešana.

Burbuļu šķirošanas optimizēšana palīdz mums izvairīties no nevajadzīgām atkārtojumiem un ietaupīt laiku un resursus.

Piemēram, ja pirmais un otrais vienums jau ir sakārtoti, nav nepieciešams atkārtot pārējās vērtības. Iterācija tiek pārtraukta un nākamā tiek uzsākta, līdz process ir pabeigts, kā parādīts zemāk esošajā burbuļu kārtošanas piemērā.

Optimizācija tiek veikta, izmantojot šādas darbības

1. solis. Izveidojiet karodziņa mainīgo, kas uzrauga, vai iekšējā cilpā ir notikusi maiņa

2. solis. Ja vērtības ir mainījušās ar pozīcijām, turpiniet nākamo atkārtojumu

3. solis) Ja priekšrocības nav mainījušas pozīcijas, pārtrauciet iekšējo cilpu un turpiniet ar ārējo cilpu.

Optimizēta burbuļu kārtošana ir efektīvāka, jo tā veic tikai nepieciešamās darbības un izlaiž tās, kas nav nepieciešamas.

Vizuālā pārstāvība

Ņemot vērā piecu elementu sarakstu, šie attēli ilustrē, kā burbuļu kārtošana atkārtojas pa vērtībām, tos šķirojot

Šis attēls parāda nešķiroto sarakstu

Pirmais atkārtojums

1. darbība)

Vērtības 21 un 6 tiek salīdzinātas, lai pārbaudītu, kura ir lielāka par otru.

21 ir lielāks par 6, tāpēc 21 ieņem pozīciju, ko ieņem 6, bet 6 ieņem 21, kuru ieņem 21

Mūsu modificētais saraksts tagad izskatās kā iepriekš.

2. solis)

Tiek salīdzinātas vērtības 21 un 9.

21 ir lielāks par 9, tāpēc mēs mainām pozīcijas 21 un 9

Jaunais saraksts tagad ir tāds pats kā iepriekš

3. solis)

Vērtības 21 un 33 tiek salīdzinātas, lai atrastu lielāko.

Vērtība 33 ir lielāka par 21, tāpēc apmaiņa nenotiek.

4. solis)

Vērtības 33 un 3 tiek salīdzinātas, lai atrastu lielāko.

Vērtība 33 ir lielāka par 3, tāpēc mēs mainām viņu pozīcijas.

Kārtotais saraksts pirmās iterācijas beigās ir tāds pats kā iepriekš

Otrais atkārtojums

Jaunais saraksts pēc otrās atkārtošanas ir šāds

Trešais atkārtojums

Jaunais saraksts pēc trešās atkārtošanas ir šāds

Ceturtais atkārtojums

Jaunais saraksts pēc ceturtās atkārtošanas ir šāds

Python piemēri

Šis kods parāda, kā ieviest Bubble Sort algoritmu Python.

def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)

Izpildot iepriekš minēto burbuļu kārtošanas programmu Python, tiek iegūti šādi rezultāti

[6, 9, 21, 3, 33]

Kods Paskaidrojums

Programmas Python Bubble Sort koda skaidrojums ir šāds

ŠEIT,

  1. Definē funkciju bubbleSort, kas pieņem parametru theSeq. Kods neko neizraisa.
  2. Iegūst masīva garumu un piešķir vērtību mainīgajam n. Kods neko neizraisa
  3. Tiek sākta cilpa for for, kas palaiž burbuļu kārtošanas algoritmu (n - 1) reizes. Šī ir ārējā cilpa. Kods neko neizraisa
  4. Definē karodziņa mainīgo, kas tiks izmantots, lai noteiktu, vai ir notikusi mijmaiņa. Tas paredzēts optimizācijas nolūkos. Kods neko neizraisa
  5. Sākas iekšējā cilpa, kas salīdzina visas saraksta vērtības no pirmās līdz pēdējai. Kods neko neizraisa.
  6. Izmanto if paziņojumu, lai pārbaudītu, vai kreisajā pusē esošā vērtība ir lielāka par vērtību tieši labajā pusē. Kods neko neizraisa.
  7. Piešķir sekvences [j] vērtību laika mainīgajam tmp, ja nosacījums tiek vērtēts kā patiess. Kods neko neizraisa
  8. Seq [j + 1] vērtība tiek piešķirta Seq [j] pozīcijai. Kods neko neizraisa
  9. Mainīgā tmp vērtība tiek piešķirta pozīcijai theSeq [j + 1]. Kods neko neizraisa
  10. Karodziņa mainīgajam tiek piešķirta vērtība 1, kas norāda, ka ir notikusi mijmaiņa. Kods neko neizraisa
  11. Izmanto if paziņojumu, lai pārbaudītu, vai mainīgā karoga vērtība ir 0. Kods neko neizdod
  12. Ja vērtība ir 0, tad mēs saucam pārtraukuma paziņojumu, kas iziet no iekšējās cilpas.
  13. Atgriež secības vērtību pēc tam, kad tā ir sakārtota. Kods izvada sakārtoto sarakstu.
  14. Definē mainīgo el, kas satur nejaušu skaitļu sarakstu. Kods neko neizraisa.
  15. Piešķir funkcijas bubbleSort vērtību mainīgajam rezultātam.
  16. Izdrukā mainīgā rezultāta vērtību.

Burbuļu šķirošanas priekšrocības

Tālāk ir norādītas dažas burbuļu šķirošanas algoritma priekšrocības

  • To ir viegli saprast
  • Tas darbojas ļoti labi, ja saraksts jau ir vai ir gandrīz sakārtots
  • Tam nav nepieciešama plaša atmiņa.
  • Algoritma kodu ir viegli uzrakstīt
  • Vietas prasības ir minimālas, salīdzinot ar citiem šķirošanas algoritmiem.

Burbuļu šķirošana Trūkumi

Tālāk ir minēti daži burbuļu šķirošanas algoritma trūkumi

  • Šķirojot lielus sarakstus, tas nedarbojas labi. Tas prasa pārāk daudz laika un resursu.
  • To galvenokārt izmanto akadēmiskiem mērķiem, nevis reālai lietošanai.
  • Sarakstu kārtošanai nepieciešamo darbību skaits ir secībā n 2

Burbuļu šķirošanas sarežģītības analīze

Ir trīs sarežģītības veidi:

1) kārtot sarežģītību

Kārtošanas sarežģītība tiek izmantota, lai izteiktu izpildes laiku un vietu, kas nepieciešama saraksta kārtošanai. Burbuļu kārtošana veic (n - 1) atkārtojumus, lai kārtotu sarakstu, kur n ir kopējais elementu skaits sarakstā.

2) Laika sarežģītība

Burbuļu veida laika sarežģītība ir O (n 2 )

Laika sarežģītību var klasificēt kā:

  • Sliktākais gadījums - šeit sniegtais saraksts ir dilstošā secībā. Algoritms izpilda maksimālo izpildījumu skaitu, kas izteikts kā [Big-O] O (n 2 )
  • Labākais gadījums - tas notiek, kad sniegtais saraksts jau ir sakārtots. Algoritms veic minimālo izpildījumu skaitu, kas izteikts kā [Big-Omega] Ω (n)
  • Vidējais gadījums - tas notiek, ja saraksts ir nejaušā secībā. Vidējo sarežģītību attēlo kā [Big-theta] ⊝ (n 2 )

3) Kosmosa sarežģītība

Vietas sarežģītība nosaka papildu vietas daudzumu, kas nepieciešams saraksta kārtošanai. Burbuļu kārtošanai ir nepieciešama tikai viena (1) papildu vieta laika mainīgajam, ko izmanto vērtību maiņai. Tāpēc tam ir O (1) telpas sarežģītība.

Kopsavilkums

  • Burbuļu kārtošanas algoritms darbojas, salīdzinot divas blakus esošās vērtības un nomainot tās, ja kreisajā pusē esošā vērtība ir mazāka par vērtību labajā pusē.
  • Burbuļu kārtošanas algoritma ieviešana ar Python ir salīdzinoši vienkārša. Viss, kas jums jāizmanto, ir cikliem un if paziņojumiem.
  • Problēma, kuru atrisina burbuļu šķirošanas algoritms, ir nejauša vienumu saraksta ņemšana un pārveidošana par sakārtotu sarakstu.
  • Burbuļu kārtošanas algoritms datu struktūrā vislabāk darbojas, ja saraksts jau ir sakārtots, jo tas veic minimālu atkārtojumu skaitu.
  • Burbuļu kārtošanas algoritms nedarbojas labi, ja saraksts ir apgrieztā secībā.
  • Burbuļotāju kārtošanai ir laika sarežģītība O (n 2 ) un telpas sarežģītība O (1)
  • Burbuļotāju kārtošanas algoritms ir vislabāk piemērots akadēmiskiem mērķiem, nevis reālās pasaules lietojumiem.
  • Optimizētā burbuļu kārtošana padara algoritmu efektīvāku, izlaižot nevajadzīgas atkārtojumus, pārbaudot vērtības, kas jau ir sakārtotas.