Подібно до того, як бульбашки піднімаються з нижньої частини склянки, сортування бульбашок - це простий алгоритм, який сортує список, дозволяючи пускати бульбашки до нижнього чи більшого значення до верхнього. Алгоритм обходить список і порівнює сусідні значення, обмінюючи їх місцями, якщо вони не в правильному порядку.
За найгіршої складності 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]
Очевидно, сортування за допомогою бульбашок - далеко не найефективніший алгоритм сортування. Тим не менш, просто обернути голову і реалізувати себе.
А тепер налийте собі холодного, пухирчастого напою - ви цього заслужили.