Bubbla sortera

Sortering efter enkla byten , sortering efter en bubbla ( engelsk bubble sort ) är en enkel sorteringsalgoritm . Att förstå och implementera denna algoritm är det enklaste, men det är endast effektivt för små arrayer. Algoritmens komplexitet : . $O$ $(n^{2})$

Algoritmen anses pedagogisk och används praktiskt taget inte utanför utbildningslitteraturen, istället används effektivare sorteringsalgoritmer i praktiken. Samtidigt ligger utbytessorteringsmetoden bakom några av de mer avancerade algoritmerna, som shaker sort , heap sort , och quick sort .

Algoritm

Algoritmen består av upprepade passeringar genom den sorterade matrisen. För varje pass jämförs elementen sekventiellt i par och, om ordningen i paret är felaktig, permuteras elementen. Passeringar genom arrayen upprepas en gång eller tills det vid nästa pass visar sig att växlingarna inte längre behövs, vilket gör att arrayen sorteras. Med varje passage av algoritmen genom den inre slingan, placeras det näst största elementet i arrayen på sin plats i slutet av arrayen bredvid det föregående "största elementet", och det minsta elementet flyttas en position till början av arrayen. array ("flyter" till önskad position, som en bubbla i vatten - därav och namnet på algoritmen). $N-1$

Implementering

Svårighetsgrad: . $O(n^{2})$

Värsta fall:

Antalet jämförelser i loopkroppen är . $(N-1){\frac N2}$
Antalet jämförelser i looprubriker är . $(N-1){\frac N2}$
Det totala antalet jämförelser är . $(N-1)N$
Antalet tilldelningar i looprubriker är . $(N-1){\frac N2}$
Antalet byten är lika med , vilket är gånger fler än i urvalssorteringen . $(N-1){\frac N2}$ ${\frac N2}$

Bästa fall (redan sorterad array matas in):

Antalet jämförelser i loopkroppen är . $(N-1){\frac N2}$
Antalet jämförelser i looprubriker är . $(N-1){\frac N2}$
Det totala antalet jämförelser är . $(N-1)N$
Antalet byten är . $0$

Det speciella med denna algoritm är följande: efter den första slutförandet av den inre slingan är det maximala elementet i arrayen alltid på -th position. På andra passet är det näst största elementet på plats. Och så vidare. Sålunda, vid varje efterföljande pass, reduceras antalet bearbetade element med 1 och det finns inget behov av att "traversera" hela arrayen från början till slut varje gång. $N$ $N-1$

Eftersom en undergrupp av ett element inte behöver sorteras, kräver sortering inte mer än iterationer av den yttre slingan. Därför, i vissa implementeringar, löper den yttre slingan alltid smidigt och håller inte reda på om det fanns eller inte fanns några utbyten vid varje iteration. $N-1$ $N-1$

Införandet av en indikator (flagga F) för faktiska utbyten i den inre slingan minskar antalet extra pass i fall med delvis sorterade inmatningsmatriser. Före varje passage genom den inre slingan återställs flaggan till 0, och efter att utbytet faktiskt inträffade sätts den till 1. Om flaggan är 0 efter att ha lämnat den inre slingan, fanns det inga utbyten, det vill säga arrayen är sorterad och du kan avsluta sorteringsprogrammet före schemat.

Pseudokod för en ännu mer förbättrad algoritm med kontroll av verkligen inträffade utbyten i den inre slingan.

Indata: array som består av element, numrerade från till $EN]$ $N$ $A[0]$ $A[N-1]$

SLÖGLA FÖR J = 1 TILL N - 1 STEG 1 FÖR J = 1 TILL N - 1 STEG 1 F = 0 F = 0 SLÄNG FÖR I = 0 TILL N - 1 - J STEG 1 FÖR I = 0 TILL N - 1 - J STEG 1 OM A [ I ] > A [ I + 1 ] SÅ BYTA A [ I ], A [ I + 1 ]: F = 1 IF A [ I ] > A [ I + 1 ] SÅ BYTA A [ I ], A [ I + 1 ]: F = 1 NÄSTA I NÄSTA I OM F = 0 SÅ AVSLUTA SLÄNGAN OM F = 0 SÅ AVSLUTA FÖR NÄSTA J NÄSTA J

I fallet med en tidig utgång från sortering gör denna algoritm ett överflödigt pass utan byten.

I värsta fall (förbättras inte):

Antalet jämförelser i loopkroppen är . $(N-1){\frac N2}$
Antal jämförelser i looprubriker . $(N-1){\frac N2}$
Det totala antalet jämförelser är . $(N-1)N$
Antalet tilldelningar i looprubriker är . $(N-1){\frac N2}$
Antalet byten är . $(N-1){\frac N2}$

Bästa fall (förbättrat):

Antalet jämförelser i loopkroppen är . $(N-1)$
Antal jämförelser i looprubriker . $(N-1)$
Det totala antalet jämförelser är . $2(N-1)$
Antalet byten är . $0$

Tiden för sortering av 10 000 korta heltal på samma hårdvaru-mjukvarukomplex (jämförelseoperation ≈3,4 µs, utbyte ≈2,3 µs) efter urvalssortering var ≈40 sek, med ännu mer förbättrad bubbelsortering ≈30 sek, och genom snabbsortering ≈ 0,027 sek.

$O(n\cdot n)$ större än merge sort , men i liten utsträckning är skillnaden inte särskilt stor, och programkoden är väldigt enkel, så det är helt acceptabelt att använda bubble sort för många uppgifter med lågdimensionella arrayer på lediga och lätt belastade maskiner. $O(n\cdot\log n)$ $n$

Algoritmen kan förbättras något genom att göra följande:

Den inre slingan kan modifieras så att den växelvis skannar arrayen från början och sedan från slutet. En algoritm som modifierats på detta sätt kallas shuffle sort eller shaker sort. Detta minskar inte komplexiteten . $O(n\cdot n)$

I bubbelsortering kan du för varje passage genom den inre slingan lägga till definitionen av nästa minimielement och placera den i början av matrisen, det vill säga kombinera bubbelsorterings- och urvalssorteringsalgoritmerna medan antalet passeringar genom den inre slingan halveras, men antalet jämförelser och ett utbyte läggs till efter varje passage genom den inre slingan.

Pseudokoden för den kombinerade bubbelsorterings- och urvalssorteringsalgoritmen ( stabil implementering):

FÖR J = 0 TILL N - 1 STEG 1 F = 0 MIN = J FÖR I = J TILL N - 1 - J STEG 1 OM Y [ I ] > Y [ I + 1 ] BYTA DÅ Y [ I ], Y [ I + 1 ]: F = 1 OM Y [ I ] < Y [ MIN ] SÅ MIN = I NÄSTA I OM F = 0 SÅ AVSLUTA FÖR IF MIN <> J DÅ BYTA Y [ J ], Y [ MIN ] NÄSTA J

Ett exempel på hur algoritmen fungerar

Låt oss ta en matris med siffrorna "5 1 4 2 8" och sortera värdena i stigande ordning med hjälp av bubbelsortering. De element som jämförs i detta skede markeras.

Första passet:

( 5 1 4 2 8) ( 1 5 4 2 8), Här jämför algoritmen de två första elementen och byter ut dem. (1 5 4 2 8) (1 4 5 2 8), Byter pga

5>4

(1 4 5 2 8) (1 4 2 5 8), Byter pga

5>2

(1 4 2 5 8 ) (1 4 2 5 8 ), Eftersom elementen är på sina platser ( ), byter algoritmen dem inte.

8>5

Andra passet:

( 1 4 2 5 8) ( 1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8), Byter pga

4>2

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

Nu är arrayen helt sorterad, men algoritmen vet inte detta. Därför måste han göra en hel passning och fastställa att det inte fanns några permutationer av element.

Tredje passet:

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

Nu är matrisen sorterad och algoritmen kan slutföras.

Länkar

Animation av sorteringsalgoritmer
Dynamisk visualisering 7 sorteringsalgoritmer med öppen källkod
Levitin A. V. Kapitel 3. Brute force-metod: Bubblesortering // Algoritmer. Introduktion till utveckling och analys - M . : Williams , 2006. - S. 144-146. — 576 sid. — ISBN 978-5-8459-0987-9

Ordböcker och uppslagsverk	stor kines

Sorteringsalgoritmer
Teori	Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern
Utbyta	bubbla Omrörning Dvärgar Snabb Hårkam Sortering jämnt-udda Bitvis
Val	Val Pyramidformad Slät
Insatser	Insatser shella träd
fusion	fusion
Inga jämförelser	Räkning blockera
hybrid	introsort Timsort
Övrig	Topologiska nätverk biton
opraktisk	Bogosort Stooge sort pannkaka långsam