Buborék rendezése az egyik legegyszerűbb rendezési algoritmusnak számít, amely úgy működik, hogy a szomszédos elemeket többször felcseréli, ha rossz sorrendben vannak. A buborék rendezési algoritmussal láthatja, hogy a legnagyobb elem (feltételezve, hogy a legkisebbtől a legnagyobbig válogatunk) “buborékolni fog” a lista vagy tömb tetejéig.

Példa:
Tegyük fel, hogy az elemek listáját vagy tömbjét növekvő sorrendben szeretnénk rendezni (a legkisebbtől a legnagyobbig): List = (3,1,2)

Mivel nem történt cserélés, ez azt mondja nekünk, hogy a tömb már növekvő sorrendben rendezve!

Legjobb eset

Most próbáljuk meg ugyanezt az algoritmust, de ezúttal a legjobb esetben, amikor az elemek már rendezve vannak a sorrendben ( emelkedő) szeretnénk.

Mivel nem történt cserélés, készen vagyunk, és az algoritmus csak 2 összehasonlítást hajtott végre, és a tömb elemeinek számát n = 3-nak hívjuk. Tehát láthatjuk, hogy n esetén Ez az algoritmus a legjobb esetben csak n-1 összehasonlítást igényel, n-1 = O (n)

Az általunk használt eljárás vagy algoritmus a következő:

Ez az algoritmus zászlót használ megmondani, hogy az elemeket felcserélték-e vagy sem , amely lehetővé teszi, hogy a buborék rendezési algoritmus legjobb esetben O (n) legyen O (n²) helyett, mint a buborék rendezés másik megvalósítása.

A fenti algoritmus
Legrosszabb eset = O (n²)
Legjobb eset = O (n)

Vessünk egy pillantást a buborék-rendezési algoritmus egy másik megvalósítására:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

A fenti algoritmus
Legrosszabb eset = O (n²)
Legjobb eset = O (n²)

Legrosszabb eset

Rendezzünk egy tömböt vagy listát = (3,2,1) ez lenne a legrosszabb eset, amikor a lista teljesen ellentétes sorrendben van, mint amit szeretnénk (növekvő sorrendben) a fenti algoritmus használatával.

Első lépés:
(3,2,1) – > Hasonlítsa össze a 3 elemeket & 2
(2,3 , 1) – > Cseréljen 3 & 2-et 2 < 3
(( 2,3,1) – > Hasonlítsa össze az elemeket 3 & 1
(2,1,3) – > Csere 1 & 3 óta 1 < 3

Második lépés:
(2,1,3) – > Hasonlítsa össze a 2 elemeket & 1
(1,2,3) – > Cserélje 2 & 1 óta 1 < 2
(1,2,3) – > Hasonlítsa össze a 2. elem & 3
(1,2,3) – > Nincs szükség cserére, mivel 2 < 3

Most befejeztük a hurkolást mindkét hurkon, így a tömböt növekvő sorrendbe kell rendezni.

Megjegyezzük, hogy a fenti második példában 4 összehasonlítást végeztünk, és a tömb elemeinek számát ‘n’ = 3-nak hívjuk, így az összehasonlítások száma (n-1) ², és (n-1) ² = O (n²)

A kódolási interjú feltörésének is nevezzük azt a nagyszerű könyvet, amely felkészít az interjúk kódolására / programozására. Ez segít megismerkedni az algoritmusok rendezésével és a problémamegoldással, ezért mindenképpen ellenőrizze!

Köszönjük, hogy elolvasta ezt a cikket, remélem, hogy hasznos lesz mindannyian! Folytassa a tanulást, és ha további algoritmuselemző videókat szeretne, látogasson el és iratkozzon fel a YouTube-csatornáimra (randerson112358 & compsci112358)

Ellenőrizze a következőket: további tartalom / videó az algoritmuselemzésről és -programozásról:

YouTube-csatorna:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Webhely:

Videó oktatóanyagok a megismétlődés kapcsolatáról:

Videó oktatóanyagok az algoritmusok elemzéséről:

Twitter: