Start | bubble sort
 

Bubbelsort



Bubbelsort är en sortering som består av en yttre lopp som snurrar sålänge det behövs, dvs sålänge det finns element som behöver byta plats i listan.

Den inre loopen skannar hela listan från början till slut och om den hittar 2 element som står i fel ordning, så byter den plats på dessa.

sortering med bubblesort

Tidskomplexiteten för sortering med bubblesort är O(N2) då vi har 2 stycken loopar i varandra.

Algoritm

Konceptet här, det är att vi har en yttre loop som snurrar tills vidare och enbart avbryts (break) om listan är fullt sorterad. En inre loop som vänder på elementen parvis om de är i fel ordning. Anledningen till att den inre loopen måste utföras upprepade gånger, det är ju därför att varje gång ett felvänt par vänds rätt, så kan de fortfarande vara långt ifrån sin slutgiltiga plats i en sorterad lista.

yttre loop: oändlig


Vi har yttre en oändlig lopp som enbart bryts med break, ifall det inte längre finns några element som måste byta plats efter ett svep över hela listan.

inre loop


Den inre loppen skannar hela listan och byter plats på elementen parvis om de har fel inbördes ordning. För varje sådant här varv när hela listan gås igenom så kommer elementen sakta röra sig mot sin riktiga positioner och i slutändan finns det inte längre några element att byta plats på.

Medan visar 1 svep. För samtliga svep klicka på koden.

0 1 2 3 4 5 6 7 8 9 10
543 123 5 564 43 4 1233 12 3 1 4
123 543 5 564 43 4 1233 12 3 1 4
123 5 543 564 43 4 1233 12 3 1 4
123 5 543 43 564 4 1233 12 3 1 4
123 5 543 43 4 564 1233 12 3 1 4
123 5 543 43 4 564 1233 12 3 1 4
123 5 543 43 4 564 12 1233 3 1 4
123 5 543 43 4 564 12 3 1233 1 4
123 5 543 43 4 564 12 3 1 1233 4
123 5 543 43 4 564 12 3 1 4 1233
Om du klickar kör på nedan kod så ser du fullständig utskift. Notera att på slutet kommer den behöva köra igenom ett helt svep där den inte gör något alls. Flaggan byttplats förblir då falsk och den yttre loppen avbryts.
lista = [543,123,5,564,43,4,1233,12,3,1,4] print(lista) def bubbleSort(lst): n = len (lst) while(True): byttplats = False for i in range(1,n): print(lst) if lst[i-1] > lst[i]: (lst[i],lst[i-1])=(lst[i-1],lst[i]) byttplats = True if(not byttplats): break bubbleSort(lista) print(lista)
Nedan utan utskrifter.
lista = [543,123,5,564,43,4,1233,12,3,1,4] print(lista) def bubbleSort(lst): n = len (lst) while(True): byttplats= False for i in range(1,n): if lst[i-1] > lst[i]: (lst[i],lst[i-1])=(lst[i-1],lst[i]) byttplats= True if(not byttplats): break bubbleSort(lista) print(lista)
15.305042266846 ms