Boblesortering forklaret

Ligesom den måde, hvorpå bobler stiger op fra bunden af ​​et glas, er boblesortering en simpel algoritme, der sorterer en liste, der tillader enten lavere eller højere værdier at boble op til toppen. Algoritmen krydser en liste og sammenligner tilstødende værdier og bytter dem, hvis de ikke er i den rigtige rækkefølge.

Med en worst-case kompleksitet på O (n ^ 2) er boblesortering meget langsom sammenlignet med andre sorteringsalgoritmer som quicksort. Opadrettede er, at det er en af ​​de nemmeste sorteringsalgoritmer at forstå og kode fra bunden.

Eksempel:

let arr = [4, 2, 6, 3, 9]; let sorted = false while(!sorted) { sorted = true for(var i = 0; i < arr.length; i++) { if(arr[i] < arr[i - 1]) { let temp = arr[i]; arr[i] = arr[i - 1]; arr[i - 1] = temp; sorted = false; } } }

Først gennem listen:

  • Startende med [4, 2, 6, 3, 9]sammenligner algoritmen de to første elementer i arrayet, 4 og 2. Den bytter dem, fordi 2 <4:[2, 4, 6, 3, 9]
  • Den sammenligner de to næste værdier, 4 og 6. Da 4 <6 er disse allerede i orden, og algoritmen bevæger sig videre: [2, 4, 6, 3, 9]
  • De næste to værdier byttes også, fordi 3 <6: [2, 4, 3, 6, 9]
  • De sidste to værdier, 6 og 9, er allerede i orden, så algoritmen bytter dem ikke.

Anden passage gennem listen:

  • 2 <4, så der er ingen grund til at bytte position: [2, 4, 3, 6, 9]
  • Algoritmen bytter de næste to værdier, fordi 3 <4: [2, 3, 4, 6, 9]
  • Ingen bytte som 4 <6: [2, 3, 4, 6, 9]
  • Igen, 6 <9, så ingen swap forekommer: [2, 3, 4, 6, 9]

Listen er allerede sorteret, men boblesorteringsalgoritmen er ikke klar over dette. Det skal snarere udføres en hel gennemgang af listen uden at bytte nogen værdier for at vide, at listen er sorteret.

Tredje gennemgang af listen:

  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]
  • [2, 4, 3, 6, 9] =>[2, 4, 3, 6, 9]

Det er klart, at boblesortering er langt fra den mest effektive sorteringsalgoritme. Alligevel er det nemt at pakke hovedet rundt og implementere dig selv.

Gå hæld dig selv en kold, sprudlende drik - du fortjener det.