Bubble Sort paskaidrots

Tāpat kā veids, kā burbuļi paceļas no glāzes apakšas, arī burbuļu šķirošana ir vienkāršs algoritms, kas sakārto sarakstu, ļaujot zemākām vai augstākām vērtībām burbuļot līdz augšai. Algoritms šķērso sarakstu un salīdzina blakus esošās vērtības, apmainot tās, ja tās nav pareizā secībā.

Ar vissliktāko O (n ^ 2) sarežģītību burbuļu kārtošana ir ļoti lēna, salīdzinot ar citiem šķirošanas algoritmiem, piemēram, quicksort. Augšpusē ir tas, ka tas ir viens no vienkāršākajiem šķirošanas algoritmiem, kas saprotams un kodējams no nulles.

Piemērs:

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; } } }

Pirmais iziet cauri sarakstam:

  • Sākot ar to [4, 2, 6, 3, 9], algoritms salīdzina pirmos divus masīva elementus 4 un 2. Tas tos apmaina, jo 2 <4:[2, 4, 6, 3, 9]
  • Tas salīdzina nākamās divas vērtības, 4 un 6. Tā kā 4 <6, tās jau ir kārtībā, un algoritms virzās tālāk: [2, 4, 6, 3, 9]
  • Arī nākamās divas vērtības tiek apmainītas, jo 3 <6: [2, 4, 3, 6, 9]
  • Divas pēdējās vērtības - 6 un 9 - jau ir sakārtotas, tāpēc algoritms tās nemaina.

Otrais iziet cauri sarakstam:

  • 2 <4, tāpēc nav nepieciešams apmainīt pozīcijas: [2, 4, 3, 6, 9]
  • Algoritms apmaina nākamās divas vērtības, jo 3 <4: [2, 3, 4, 6, 9]
  • Nav mijmaiņas kā 4 <6: [2, 3, 4, 6, 9]
  • Atkal 6 <9, tāpēc mijmaiņa nenotiek: [2, 3, 4, 6, 9]

Saraksts jau ir sakārtots, bet burbuļu kārtošanas algoritms to neapzinās. Drīzāk tam ir jāpabeidz visa caurlaide, nemainot vērtības, lai uzzinātu, ka saraksts ir sakārtots.

Trešais iziet cauri sarakstam:

  • [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]

Skaidrs burbuļu kārtošana ir tālu no visefektīvākā šķirošanas algoritma. Joprojām ir viegli aptīt galvu un īstenot sevi.

Tagad ejiet sev ielejiet aukstu, putojošu dzērienu - jūs to esat pelnījuši.