Buborék fajta

Az egyszerű cserék szerinti rendezés, a buborék szerinti rendezés ( angolul bubble sort ) egy egyszerű rendezési algoritmus . Ennek az algoritmusnak a megértése és megvalósítása a legegyszerűbb, de csak kis tömbök esetén hatásos. Az algoritmus összetettsége : . $O$ $(n^{2})$

Az algoritmust oktató jellegűnek tekintik, és gyakorlatilag nem használják az oktatási szakirodalomon kívül, ehelyett hatékonyabb rendezési algoritmusokat alkalmaznak a gyakorlatban. Ugyanakkor a csererendezési módszer néhány fejlettebb algoritmus alapjául szolgál, mint például a shaker rendezés , a kupac rendezés és a gyors rendezés .

Algoritmus

Az algoritmus a rendezett tömbön való ismételt áthaladásokból áll. Minden egyes lépésnél az elemek egymás után páronként összehasonlításra kerülnek, és ha a párban a sorrend helytelen, az elemek permutálódnak. A tömbön való áthaladás egyszer megismétlődik, vagy amíg a következő lépésnél ki nem derül, hogy a cserékre már nincs szükség, ami azt jelenti, hogy a tömb rendezve van. Az algoritmus minden egyes áthaladásakor a belső hurkon a tömb következő legnagyobb eleme a helyére kerül a tömb végére az előző „legnagyobb elem” mellé, és a legkisebb elem egy pozícióval a tömb elejére kerül. tömb ("lebeg" a kívánt pozícióba, mint egy buborék a vízben - innen és az algoritmus neve). $N-1$

Megvalósítás

Nehézségi fok: . $O(n^{2})$

Legrosszabb esetben:

Az összehasonlítások száma a ciklustörzsben . $(N-1){\frac N2}$
A hurokfejlécekben lévő összehasonlítások száma . $(N-1){\frac N2}$
Az összehasonlítások teljes száma . $(N-1)N$
A hurokfejlécekben lévő hozzárendelések száma . $(N-1){\frac N2}$
A cserék száma megegyezik a -val , ami többszöröse, mint a kiválasztási rendezésben . $(N-1){\frac N2}$ ${\frac N2}$

Legjobb eset (a már rendezett tömb bevitele):

Az összehasonlítások száma a ciklustörzsben . $(N-1){\frac N2}$
A hurokfejlécekben lévő összehasonlítások száma . $(N-1){\frac N2}$
Az összehasonlítások teljes száma . $(N-1)N$
A cserék száma . $0$

Ennek az algoritmusnak a sajátossága a következő: a belső ciklus első befejezése után a tömb maximális eleme mindig a -edik pozícióban van. A második menetnél a következő legnagyobb elem a helyén van. Stb. Így minden következő lépésben a feldolgozott elemek száma 1-gyel csökken, és nem kell minden alkalommal "bejárni" a teljes tömböt az elejétől a végéig. $N$ $N-1$

Mivel egy elemből álló altömböt nem kell rendezni, a rendezés nem igényel többet, mint a külső ciklus iterációit. Ezért egyes megvalósításokban a külső ciklus mindig zökkenőmentesen fut , és nem követi nyomon, hogy voltak-e cserék az egyes iterációk során. $N-1$ $N-1$

A tényleges cserék indikátorának (F jelzőjének) bevezetése a belső hurokban csökkenti az extra lépések számát a részben rendezett bemeneti tömbök esetén. A belső hurkon való minden egyes áthaladás előtt a jelző 0-ra áll vissza, a csere tényleges megtörténte után pedig 1-re. Ha a jelző 0 a belső hurokból való kilépés után, akkor nem volt csere, vagyis a tömb rendezve van, és a rendezési programból az ütemezés előtt kiléphet.

Pszeudo kód egy még továbbfejlesztett algoritmushoz, amely ellenőrzi, hogy valóban történt-e csere a belső hurokban.

Bemenet: elemekből álló tömb, től- ig számozott $A[N]$ $N$ $A[0]$ $A[N-1]$

HURKOZÁS J - HOZ = 1 - N - 1 1. LÉPÉS J = 1 - N - 1 1. LÉPÉS F = 0 F = 0 CIKK I = 0 - N - 1 - J HOGY 1. LÉPÉS I - HOZ = 0 - N - 1 - J 1. LÉPÉS HA A [ I ] > A [ I + 1 ] MAJD CSERÉLJE MEG A [ I ], A [ I + 1 ]: F = 1 HA A [ I ] > A [ I + 1 ] AKKOR CSERÉLJE A [ I ]-t, A [ I + 1 ]: F = 1 KÖVETKEZŐ I KÖVETKEZŐ I HA F = 0 , akkor KILÉPÉS KI HA F = 0 , MAJD KILÉPÉS A KÖVETKEZŐ J KÖVETKEZŐ J

A rendezésből való korai kilépés esetén ez az algoritmus egy redundáns lépést tesz cserék nélkül.

Legrosszabb eset (nem javul):

Az összehasonlítások száma a ciklustörzsben . $(N-1){\frac N2}$
Összehasonlítások száma a hurokfejlécekben . $(N-1){\frac N2}$
Az összehasonlítások teljes száma . $(N-1)N$
A hurokfejlécekben lévő hozzárendelések száma . $(N-1){\frac N2}$
A cserék száma . $(N-1){\frac N2}$

Legjobb eset (javított):

Az összehasonlítások száma a ciklustörzsben . $(N-1)$
Összehasonlítások száma a hurokfejlécekben . $(N-1)$
Az összehasonlítások teljes száma . $2 (N-1)$
A cserék száma . $0$

10 000 rövid egész szám rendezési ideje ugyanazon a hardver-szoftver komplexen (összehasonlítási művelet ≈3,4 µs, csere ≈2,3 µs) kiválasztási rendezés szerint ≈40 mp, még továbbfejlesztett buborékrendezés esetén ≈30 mp, gyorsrendezés esetén pedig ≈ 0,027 mp.

$O(n\cdot n)$ nagyobb, mint a merge sort , de kicsinél nem túl nagy a különbség, és a programkód nagyon egyszerű, így teljesen elfogadható a buborékos rendezés használata sok feladathoz alacsony dimenziós tömbökkel üresjárati és enyhén terhelt gépeken. $O(n\cdot\log n)$ $n$

Az algoritmus némileg javítható a következőkkel:

A belső ciklus módosítható úgy, hogy felváltva az elejétől, majd a végétől pásztázza a tömböt. Az így módosított algoritmust véletlenszerű rendezésnek vagy shaker rendezésnek nevezzük . Ez nem csökkenti a bonyolultságot . $O(n\cdot n)$

A buborékos rendezésnél a belső hurkon minden egyes átlépésnél hozzáadhatja a következő minimális elem definícióját és elhelyezheti a tömb elejére, azaz kombinálhatja a buborékrendezési és kijelölési rendezési algoritmusokat , miközben az áthaladások száma a belső hurok felére csökken, de az összehasonlítások száma és egy csere hozzáadódik minden egyes áthaladás után a belső hurkon.

A kombinált buborékrendezési és kiválasztási rendezési algoritmus pszeudokódja ( stabil megvalósítás):

J = 0 - N - 1 1. LÉPÉS F = 0 PERC = J I = J - N - 1 - J 1. LÉPÉS HA I [ I ] > I [ I + 1 ] , AKKOR CSERÉLJE MEG Y [ I ] , Y [ I + 1 ]: F = 1 HA I [ I ] < I [ MIN ] MAJD MIN = I NEXT I HA F = 0 AKKOR KILÉPÉS IF MIN <> J -RE, MAJD CSERÉLJE MEG Y [ J ], Y [ MIN ] NEXT J

Példa az algoritmus működésére

Vegyünk egy tömböt „5 1 4 2 8” számokkal, és rendezzük az értékeket növekvő sorrendbe a buborékos rendezés segítségével. Az ebben a szakaszban összehasonlított elemek kiemelve vannak.

Első menet:

( 5 1 4 2 8) ( 1 5 4 2 8), Itt az algoritmus összehasonlítja az első két elemet és felcseréli őket. (1 5 4 2 8) (1 4 5 2 8), Csere, mert

5>4

(1 4 5 2 8) (1 4 2 5 8), Csere, mert

5>2

(1 4 2 5 8 ) (1 4 2 5 8 ), Most, mivel az elemek a helyükön vannak ( ), az algoritmus nem cseréli fel őket.

8>5

Második menet:

( 1 4 2 5 8) ( 1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8), Csere, mert

4>2

(1 2 4 5 8) (1 2 4 5 8)

Most a tömb teljesen rendezve van, de az algoritmus ezt nem tudja. Ezért teljes átlépést kell végrehajtania, és meg kell határoznia, hogy nem voltak-e elemek permutációi.

Harmadik passz:

( 1 2 4 5 8) ( 1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8)

Most a tömb rendezve van, és az algoritmus befejezhető.

Linkek

Rendezési algoritmusok animációja
Dinamikus megjelenítés 7 Nyílt forráskódú rendezési algoritmusok
Levitin A. V. 3. fejezet: Brute force módszer: Bubble sort // Algoritmusok. Bevezetés a fejlesztésbe és elemzésbe - M . : Williams , 2006. - S. 144-146. — 576 p. — ISBN 978-5-8459-0987-9

Szótárak és enciklopédiák	nagy kínai

Rendezési algoritmusok
Elmélet	Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső
Csere	buborék Keverés Törpék Gyors Fésű Rendezés páros-páratlan Bitenként
Választás	Választás Piramis alakú Sima
Betétek	Betétek shella fa
egyesülés	egyesülés
Nincs összehasonlítás	Számolás Blokk
hibrid	introsort Timsort
Egyéb	Topológiai hálózatok biton
nem praktikus	Bogosort Stooge fajta palacsinta lassú