Пояснене сортування міхурів

Подібно до того, як бульбашки піднімаються з нижньої частини склянки, сортування бульбашок - це простий алгоритм, який сортує список, дозволяючи пускати бульбашки до нижнього чи більшого значення до верхнього. Алгоритм обходить список і порівнює сусідні значення, обмінюючи їх місцями, якщо вони не в правильному порядку.

За найгіршої складності O (n ^ 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]

Очевидно, сортування за допомогою бульбашок - далеко не найефективніший алгоритм сортування. Тим не менш, просто обернути голову і реалізувати себе.

А тепер налийте собі холодного, пухирчастого напою - ви цього заслужили.