Boble sortering

Sortering efter simple udvekslinger , sortering efter en boble ( engelsk bubble sort ) er en simpel sorteringsalgoritme . At forstå og implementere denne algoritme er den enkleste, men den er kun effektiv for små arrays. Algoritmens kompleksitet : . $O$ $(n^{2})$

Algoritmen betragtes som pædagogisk og bruges praktisk talt ikke uden for undervisningslitteraturen, i stedet bruges mere effektive sorteringsalgoritmer i praksis. Samtidig ligger udvekslingssorteringsmetoden til grund for nogle af de mere avancerede algoritmer, såsom shaker sort , heap sort og quick sort .

Algoritme

Algoritmen består af gentagne gennemløb gennem det sorterede array. For hver gennemgang sammenlignes elementerne sekventielt i par, og hvis rækkefølgen i parret er forkert, permuteres elementerne. Gennemløb gennem arrayet gentages én gang, eller indtil det ved næste gennemløb viser sig, at udvekslingerne ikke længere er nødvendige, hvilket betyder, at arrayet er sorteret. Med hver passage af algoritmen gennem den indre sløjfe sættes det næststørste element i arrayet på plads i slutningen af arrayet ved siden af det forrige "største element", og det mindste element flytter en position til begyndelsen af arrayet. array ("flyder" til den ønskede position, som en boble i vand - deraf og navnet på algoritmen). $N-1$

Implementering

Sværhedsgrad :. $O(n^{2})$

Worst case:

Antallet af sammenligninger i loop body er . $(N-1){\frac N2}$
Antallet af sammenligninger i loop-headers er . $(N-1){\frac N2}$
Det samlede antal sammenligninger er . $(N-1)N$
Antallet af opgaver i loop-headere er . $(N-1){\frac N2}$
Antallet af udvekslinger er lig med , hvilket er gange mere end i udvælgelsessortering . $(N-1){\frac N2}$ ${\frac N2}$

Bedste tilfælde (allerede sorteret array er input):

Antallet af sammenligninger i loop body er . $(N-1){\frac N2}$
Antallet af sammenligninger i loop-headers er . $(N-1){\frac N2}$
Det samlede antal sammenligninger er . $(N-1)N$
Antallet af udvekslinger er . $0$

Det særlige ved denne algoritme er som følger: efter den første afslutning af den indre løkke er det maksimale element i arrayet altid i den -th position. På det andet gennemløb er det næststørste element på plads. Og så videre. Ved hver efterfølgende gennemgang reduceres antallet af behandlede elementer med 1, og der er ikke behov for at "traverse" hele arrayet fra start til slut hver gang. $N$ $N-1$

Da en underarray af et element ikke skal sorteres, kræver sortering ikke mere end iterationer af den ydre sløjfe. Derfor kører den ydre sløjfe i nogle implementeringer altid problemfrit og holder ikke styr på, om der var eller ikke var udvekslinger ved hver iteration. $N-1$ $N-1$

Indførelsen af en indikator (flag F) for faktiske udvekslinger i den indre sløjfe reducerer antallet af ekstra gennemløb i tilfælde med delvist sorterede input-arrays. Før hver passage gennem den indre sløjfe nulstilles flaget til 0, og efter udvekslingen faktisk fandt sted, sættes det til 1. Hvis flaget er 0 efter at have forladt den indre sløjfe, var der ingen udvekslinger, det vil sige arrayet er sorteret, og du kan afslutte sorteringsprogrammet før tidsplanen.

Pseudokode til en endnu mere forbedret algoritme med kontrol for virkelig forekomne udvekslinger i den indre løkke.

Input: matrix bestående af elementer, nummereret fra til $A[N]$ $N$ $A[0]$ $A[N-1]$

SLØKKE FOR J = 1 TIL N - 1 TRIN 1 FOR J = 1 TIL N - 1 TRIN 1 F = 0 F = 0 SLØKKE FOR I = 0 TIL N - 1 - J TRIN 1 FOR I = 0 TIL N - 1 - J TRIN 1 HVIS A [ I ] > A [ I + 1 ] SÅ BYT A [ I ], A [ I + 1 ]: F = 1 HVIS A [ I ] > A [ I + 1 ] SÅ SWAP A [ I ], A [ I + 1 ]: F = 1 NÆSTE I NÆSTE I HVIS F = 0 SÅ AFSLUT LOOP HVIS F = 0 SÅ AFSLUT FOR NÆSTE J NÆSTE J

I tilfælde af en tidlig exit fra sortering, gør denne algoritme én overflødig gennemgang uden udvekslinger.

Worst case (forbedrer ikke):

Antallet af sammenligninger i loop body er . $(N-1){\frac N2}$
Antal sammenligninger i loop-headers . $(N-1){\frac N2}$
Det samlede antal sammenligninger er . $(N-1)N$
Antallet af opgaver i loop-headere er . $(N-1){\frac N2}$
Antallet af udvekslinger er . $(N-1){\frac N2}$

Bedste tilfælde (forbedret):

Antallet af sammenligninger i loop body er . $(N-1)$
Antal sammenligninger i loop-headers . $(N-1)$
Det samlede antal sammenligninger er . $2(N-1)$
Antallet af udvekslinger er . $0$

Tidspunktet for sortering af 10.000 korte heltal på det samme hardware-software kompleks (sammenligningsoperation ≈3,4 µs, udveksling ≈2,3 µs) efter udvælgelsessortering var ≈40 sek., ved endnu mere forbedret boblesortering ≈30 sek. og ved hurtig sortering ≈ 0,027 sek.

$O(n\cdot n)$ større end merge sort , men i det små er forskellen ikke særlig stor, og programkoden er meget enkel, så det er helt acceptabelt at bruge bubble sort til mange opgaver med lavdimensionelle arrays på inaktive og let belastede maskiner. $O(n\cdot\log n)$ $n$

Algoritmen kan forbedres en smule ved at gøre følgende:

Den indre sløjfe kan modificeres, så den skiftevis scanner arrayet fra begyndelsen og derefter fra slutningen. En algoritme, der er ændret på denne måde, kaldes shuffle sort eller shaker sort. Dette reducerer ikke kompleksiteten . $O(n\cdot n)$

I boblesortering kan du med hver passage gennem den indre sløjfe tilføje definitionen af det næste minimumselement og placere det i begyndelsen af arrayet, det vil sige kombinere boblesorterings- og selektionssorteringsalgoritmerne , mens antallet af passeringer igennem den indre løkke halveres, men antallet af sammenligninger og en udveksling tilføjes efter hver passage gennem den indre løkke.

Pseudokode for den kombinerede boblesorterings- og selektionssorteringsalgoritme ( stabil implementering):

FOR J = 0 TIL N - 1 TRIN 1 F = 0 MIN = J FOR I = J TIL N - 1 - J TRIN 1 HVIS Y [ I ] > Y [ I + 1 ] SÅ SKIFTS Y [ I ], Y [ I 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Et eksempel på, hvordan algoritmen fungerer

Lad os tage en matrix med tallene "5 1 4 2 8" og sortere værdierne i stigende rækkefølge ved hjælp af boblesortering. De elementer, der sammenlignes på dette stadium, er fremhævet.

Første pass:

( 5 1 4 2 8) ( 1 5 4 2 8), Her sammenligner algoritmen de to første elementer og bytter dem. (1 5 4 2 8) (1 4 5 2 8), Bytter pga

5>4

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

5>2

(1 4 2 5 8 ) (1 4 2 5 8 ), Nu, da elementerne er på deres pladser ( ), bytter algoritmen dem ikke.

8>5

Andet gennemløb:

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

4>2

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

Nu er arrayet fuldstændigt sorteret, men det ved algoritmen ikke. Derfor skal han lave en fuld aflevering og fastslå, at der ikke var nogen permutationer af elementer.

Tredje pas:

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

Nu er arrayet sorteret, og algoritmen kan fuldføres.

Links

Animation af sorteringsalgoritmer
Dynamisk visualisering 7 Open Source-sorteringsalgoritmer
Levitin A. V. Kapitel 3. Brute force metode: Boblesortering // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 144-146. — 576 s. — ISBN 978-5-8459-0987-9

Ordbøger og encyklopædier	stor kinesisk

Sorteringsalgoritmer
Teori	Kompleksitet O notation Ordreforhold Sorter typer bæredygtige Indre Ekstern
Udveksling	boble Omrøring Dværge Hurtig Kam Sortering lige-ulige Bitvis
Valg	Valg Pyramideformet Glat
indsætter	indsætter shella træ
fusion	fusion
Ingen sammenligninger	Tæller blok
hybrid	introsort Timsort
Andet	Topologisk netværk biton
upraktisk	Bogosort Stooge sort pandekage langsom