Burbulų rūšiavimo algoritmas su „Python“ naudojant sąrašo pavyzdį

Turinys:

Anonim

Kas yra burbulų rūšiavimas?

„Bubble Sort“ yra rūšiavimo algoritmas, naudojamas sąrašo elementams rūšiuoti didėjimo tvarka, lyginant dvi gretimas vertes. Jei pirmoji reikšmė yra didesnė nei antroji, pirmoji reikšmė užima antrąją, o antroji - pirmąją. Jei pirmoji reikšmė yra mažesnė nei antroji, tada nepakeičiama.

Šis procesas kartojamas tol, kol visos sąrašo reikšmės bus palygintos ir, jei reikia, pakeistos. Kiekviena iteracija paprastai vadinama praėjimu. Burbulinės rūšies perdavimų skaičius yra lygus sąrašo elementų skaičiui atėmus vieną.

Šioje „Python“ burbulų rūšiavimo pamokoje sužinosite:

  • Kas yra burbulų rūšiavimas?
  • Burbulų rūšiavimo algoritmo įgyvendinimas
  • Optimizuotas burbulų rūšiavimo algoritmas
  • Vaizdinis vaizdavimas
  • „Python“ pavyzdžiai
  • Kodo paaiškinimas
  • Burbulų rūšiavimo privalumai
  • Burbulų rūšiavimas Trūkumai
  • Burbulų rūšiavimo sudėtingumo analizė

Burbulų rūšiavimo algoritmo įgyvendinimas

Įgyvendinimą suskirstysime į tris (3) etapus, būtent problemą, sprendimą ir algoritmą, kurį galime naudoti rašydami kodą bet kuriai kalbai.

Problema

Elementų sąrašas pateikiamas atsitiktine tvarka, ir mes norėtume išdėstyti daiktus tvarkingai

Apsvarstykite šį sąrašą:

[21,6,9,33,3]

Sprendimas

Kartokite sąrašą, lygindami du gretimus elementus ir keisdami juos, jei pirmoji reikšmė yra didesnė už antrąją.

Rezultatas turėtų būti toks:

[3,6,9,21,33]

Algoritmas

Burbulų rūšiavimo algoritmas veikia taip

1 žingsnis) Gaukite bendrą elementų skaičių. Gaukite bendrą nurodytame sąraše esančių elementų skaičių

2 žingsnis. Nustatykite atliktų išorinių praėjimų skaičių (n - 1). Jo ilgis yra sąrašas atėmus vieną

3 žingsnis. Atlikite vidinius praėjimus (n - 1) išoriniam praėjimui 1. Gaukite pirmojo elemento vertę ir palyginkite ją su antrąja verte. Jei antroji vertė yra mažesnė už pirmąją, tada pakeiskite pozicijas

4 žingsnis) Pakartokite 3 žingsnį, kol pasieksite išorinį praėjimą (n - 1). Gaukite kitą elementą sąraše, tada pakartokite procesą, atliktą atlikus 3 veiksmą, kol visos vertės bus išdėstytos teisinga didėjimo tvarka.

5 žingsnis. Grąžinkite rezultatą, kai visi perdavimai buvo atlikti. Grąžinkite surūšiuoto sąrašo rezultatus

6 žingsnis) Optimizuokite algoritmą

Venkite nereikalingų vidinių leidimų, jei sąrašas ar gretimos vertės jau yra surūšiuotos. Pavyzdžiui, jei pateiktame sąraše jau yra elementų, kurie buvo surūšiuoti didėjimo tvarka, tada mes galime anksti nutraukti kilpą.

Optimizuotas burbulų rūšiavimo algoritmas

Pagal numatytuosius nustatymus „Python“ burbulų rūšiavimo algoritmas lygina visus sąrašo elementus, neatsižvelgdamas į tai, ar sąrašas jau surūšiuotas, ar ne. Jei pateiktas sąrašas jau yra rūšiuojamas, visų reikšmių palyginimas yra laiko ir išteklių švaistymas.

Burbulų rūšiavimo optimizavimas padeda išvengti nereikalingų pasikartojimų ir sutaupyti laiko bei išteklių.

Pavyzdžiui, jei pirmasis ir antrasis elementai jau yra rūšiuojami, tada nereikia kartoti likusių verčių. Kartojimas nutraukiamas, o kitas pradedamas tol, kol procesas bus baigtas, kaip parodyta toliau pateiktame „Bubble Sort“ pavyzdyje.

Optimizavimas atliekamas naudojant šiuos veiksmus

1 žingsnis. Sukurkite vėliavos kintamąjį, kuris stebi, ar vidinėje kilpoje įvyko pasikeitimas

2 žingsnis) Jei reikšmės pasikeitė pozicijomis, eikite į kitą kartojimą

3 žingsnis) Jei išmokos nepasikeitė pozicijomis, nutraukite vidinę kilpą ir tęskite išorinę kilpą.

Optimizuotas burbulų rūšiavimas yra efektyvesnis, nes jis atlieka tik būtinus veiksmus ir praleidžia nereikalingus.

Vaizdinis vaizdavimas

Pateikiant penkių elementų sąrašą, šie vaizdai iliustruoja, kaip burbulas rūšiuoti per vertes juos rūšiuojant

Šiame paveikslėlyje rodomas nerūšiuotas sąrašas

Pirmoji kartojimas

1 žingsnis)

21 ir 6 vertės lyginamos, norint patikrinti, kuri iš jų yra didesnė už kitą.

21 yra didesnis nei 6, taigi 21 užima poziciją, kurią užima 6, o 6 užima poziciją, kurią užėmė 21

Mūsų modifikuotas sąrašas dabar atrodo kaip aukščiau pateiktas.

2 žingsnis)

Palyginamos 21 ir 9 vertės.

21 yra didesnis nei 9, todėl mes keičiamės 21 ir 9 pozicijomis

Naujas sąrašas dabar yra toks pat, kaip aukščiau

3 žingsnis)

Palyginamos 21 ir 33 vertės, kad būtų galima rasti didesnę.

33 reikšmė yra didesnė nei 21, todėl nekeičiama.

4 žingsnis)

33 ir 3 vertės palyginamos, kad būtų galima rasti didesnę.

33 vertė yra didesnė nei 3, todėl mes keičiamės jų pozicijomis.

Rūšiuotas sąrašas pirmosios kartojimo pabaigoje yra panašus į aukščiau pateiktą

Antroji kartojimas

Naujas sąrašas po antrojo kartojimo yra toks

Trečioji kartojimas

Naujas sąrašas po trečios kartojimo yra toks

Ketvirtoji kartojimas

Naujas sąrašas po ketvirtosios kartojimo yra toks

„Python“ pavyzdžiai

Šis kodas parodo, kaip „Bubble Sort“ algoritmą įdiegti „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)

Vykdant aukščiau pateiktą burbulų rūšiavimo programą „Python“, gaunami šie rezultatai

[6, 9, 21, 3, 33]

Kodo paaiškinimas

„Python Bubble Sort“ programos kodo paaiškinimas yra toks

ČIA

  1. Apibrėžia funkciją „bubbleSort“, kuri priima parametrą theSeq. Kodas nieko neišleidžia.
  2. Gauna masyvo ilgį ir priskiria reikšmę kintamajam n. Kodas nieko neišleidžia
  3. Paleidžiama for for loop, kuri vykdo burbulų rūšiavimo algoritmą (n - 1) kartus. Tai yra išorinė kilpa. Kodas nieko neišleidžia
  4. Nurodo žymimąjį kintamąjį, kuris bus naudojamas nustatyti, ar įvyko apsikeitimo sandoris. Tai yra optimizavimo tikslais. Kodas nieko neišleidžia
  5. Pradedama vidinė kilpa, lyginanti visas sąrašo reikšmes nuo pirmosios iki paskutinės. Kodas nieko neišleidžia.
  6. Naudoja teiginį „if“, kad patikrintų, ar kairėje pusėje esanti vertė yra didesnė nei esanti dešinėje pusėje. Kodas nieko neišleidžia.
  7. Priskiria theSeq [j] reikšmę laiko kintamajam tmp, jei sąlyga vertinama kaip teisinga. Kodas nieko neišleidžia
  8. „Seq [j + 1]“ vertė priskiriama „Seq [j]“ padėčiai. Kodas nieko neišleidžia
  9. Kintamojo tmp reikšmė priskiriama pozicijai theSeq [j + 1]. Kodas nieko neišleidžia
  10. Vėliavos kintamajam priskiriama 1 vertė, nurodanti, kad įvyko apsikeitimas. Kodas nieko neišleidžia
  11. Naudoja „if“ sakinį, kad patikrintų, ar kintamojo vėliavos vertė yra 0. Kodas nieko neišleidžia
  12. Jei vertė lygi 0, vadiname lūžio sakinį, kuris išeina iš vidinės kilpos.
  13. Pateikia theSeq reikšmę, kai ji buvo išrūšiuota. Kodas pateikia išrūšiuotą sąrašą.
  14. Apibrėžia kintamąjį el, kuriame yra atsitiktinių skaičių sąrašas. Kodas nieko neišleidžia.
  15. Priskiria funkcijos „bubbleSort“ vertę kintamam rezultatui.
  16. Spausdina kintamojo rezultato vertę.

Burbulų rūšiavimo privalumai

Toliau pateikiami keli burbulų rūšiavimo algoritmo pranašumai

  • Tai lengva suprasti
  • Tai veikia labai gerai, kai sąrašas jau yra arba beveik surūšiuotas
  • Tam nereikia didelės atminties.
  • Algoritmo kodą lengva parašyti
  • Vietos poreikis yra minimalus, palyginti su kitais rūšiavimo algoritmais.

Burbulų rūšiavimas Trūkumai

Toliau pateikiami keli burbulų rūšiavimo algoritmo trūkumai

  • Rūšiuojant didelius sąrašus, tai nėra gerai. Tai užima per daug laiko ir išteklių.
  • Dažniausiai jis naudojamas akademiniams tikslams, o ne realiame pasaulyje.
  • Sąrašui rūšiuoti reikalingų žingsnių skaičius yra eilės Nr. 2

Burbulų rūšiavimo sudėtingumo analizė

Yra trys sudėtingumo tipai:

1) Rūšiuoti sudėtingumą

Rūšiavimo sudėtingumas naudojamas norint išreikšti vykdymo trukmę ir vietą, kurios reikia sąrašui rūšiuoti. Burbulinis rūšiavimas daro (n - 1) pakartojimus, kad surūšiuotų sąrašą, kur n yra bendras sąrašo elementų skaičius.

2) Laiko sudėtingumas

Burbulų rūšies laiko sudėtingumas yra O (n 2 )

Laiko sudėtingumą galima suskirstyti į:

  • Blogiausias atvejis - čia pateikiamas sąrašas mažėjančia tvarka. Algoritmas atlieka maksimalų įvykdymų skaičių, kuris išreiškiamas kaip [Big-O] O (n 2 )
  • Geriausias atvejis - tai atsitinka, kai pateiktas sąrašas jau yra rūšiuojamas. Algoritmas atlieka mažiausią įvykdymų skaičių, kuris išreiškiamas [Big-Omega] Ω (n)
  • Vidutinis atvejis - tai atsitinka, kai sąrašas yra atsitiktine tvarka. Vidutinis sudėtingumas pateikiamas kaip [Didžioji teta] ⊝ (n 2 )

3) Erdvės sudėtingumas

Erdvės sudėtingumas matuoja papildomos vietos kiekį, kurio reikia rūšiuojant sąrašą. Burbulų rūšiavimui reikalinga tik viena (1) papildoma vieta laiko kintamajam, naudojamam reikšmių keitimui. Todėl jis turi erdvės O (1) sudėtingumą.

Santrauka

  • Burbulų rūšiavimo algoritmas veikia lyginant dvi gretimas vertes ir pakeičiant jas, jei kairėje esanti vertė yra mažesnė nei dešinėje.
  • Naudojant „Python“, burbulų rūšiavimo algoritmas yra gana tiesus. Viskas, ką jums reikia naudoti, yra kilpos ir if teiginiai.
  • Problema, kurią išsprendžia burbulų rūšiavimo algoritmas, yra atsitiktinio elementų sąrašo paėmimas ir pavertimas tvarkytu sąrašu.
  • Duomenų struktūros burbulų rūšiavimo algoritmas geriausiai veikia tada, kai sąrašas jau yra rūšiuojamas, nes jis atlieka minimalų pakartojimų skaičių.
  • Burbulų rūšiavimo algoritmas neveikia gerai, kai sąrašas yra atvirkštine tvarka.
  • Burbuliatoriaus rūšis turi laiko sudėtingumą O (n 2 ) ir erdvės sudėtingumą O (1)
  • Burbuliatoriaus rūšiavimo algoritmas geriausiai tinka akademiniams tikslams, o ne realaus pasaulio taikymams.
  • Optimizuotas burbulų rūšiavimas daro algoritmą efektyvesnį, praleidžiant nereikalingas iteracijas tikrinant jau surūšiuotas reikšmes.