Објашњење сортирања мехурића

Баш као и начин на који се мехурићи подижу са дна чаше, сортирање мехурића је једноставан алгоритам који сортира листу, омогућавајући нижим или вишим вредностима да се облаче до врха. Алгоритам прелази листу и упоређује суседне вредности, замењујући их ако нису у исправном редоследу.

Са најгором сложеношћу слова О (н ^ 2), сортирање мехурића је врло споро у поређењу са другим алгоритмима за сортирање, попут брзе сорте. Наопако је то што је то један од најлакших алгоритама за сортирање за разумевање и кодирање од нуле.

Пример:

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

Прво прођите кроз листу:

  • Полазећи од тога [4, 2, 6, 3, 9], алгоритам упоређује прва два елемента у низу, 4 и 2. Замењује их јер је 2 <4:[2, 4, 6, 3, 9]
  • Поређује следеће две вредности, 4 и 6. Како је 4 <6, оне су већ у реду и алгоритам се креће даље: [2, 4, 6, 3, 9]
  • Следеће две вредности се такође замењују јер је 3 <6: [2, 4, 3, 6, 9]
  • Последње две вредности, 6 и 9, су већ у реду, па их алгоритам не замењује.

Други пролазак кроз листу:

  • 2 <4, тако да нема потребе за заменом позиција: [2, 4, 3, 6, 9]
  • Алгоритам замењује следеће две вредности јер је 3 <4: [2, 3, 4, 6, 9]
  • Нема замене као 4 <6: [2, 3, 4, 6, 9]
  • Опет, 6 <9, тако да не долази до замене: [2, 3, 4, 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] =>[2, 4, 3, 6, 9]

Јасно је да је сортирање мехурића далеко од најефикаснијег алгоритма за сортирање. Ипак, једноставно је замотати главу и имплементирати се.

Сада си налијте хладни, мехурићани напитак - заслужили сте.