Как недавний выпускник учебного курса по кодированию, я очень мало знаю о компьютерных науках. Проходя буткемп по программированию, мы в основном концентрируемся на умении программировать, а не на понимании того, почему все работает именно так, а не иначе. Поэтому каждую неделю я хочу изучить и понять новый алгоритм сортировки.
Первый алгоритм сортировки — пузырьковая сортировка.
Насколько я могу судить, пузырьковая сортировка — крайне неэффективный алгоритм сортировки, который используется только в учебных целях. Когда дело доходит до скорости и «большой нотации O», в худшем случае скорость составляет O (n²).
Пузырьковая сортировка работает так: допустим, у нас есть массив с кучей чисел. Так:
пусть обр = [2,4,3,1,5]
Как выглядит сортировка, она принимает два индекса (числа, выделенные жирным шрифтом в этом массиве) [2,4,3,1,5].
Если первый индекс меньше индекса рядом с ним, поменяйте их местами. Если нет, перейдите к следующему индексу.
Таким образом, итерации этого будут выглядеть так:
Итерация 1: [2,4,3,1,5], [2,4,3, 1,5], [2,3,4,1,5], [2,3,1,4, 5].
Итерация 2: [2,3,1,4,5], [2,3,1, 4,5], [2,1,3,4,5], [2,1,3,4, 5].
Итерация 3: [2,1,3,4,5], [1,2,3, 4,5], [1,2,3,4,5], [1,2,3,4, 5].
Итерация 4: [1,2,3,4,5], [1,2,3, 4,5], [1,2,3,4,5], [1,2,3,4, 5],
Дело в том, что он проходит через массив много раз через рекурсию. Как только он проходит через массив один раз и проверяет, он вырезает и возвращает ваш массив.
Вот мое представление о том, что такое сортировка пузырьком. Количество раз, которое он проходит через массив, равно количеству индексов.
Я также видел другое исполнение Bubble Sort.
Эта версия сортировки узнает последние индексы массива по мере того, как она проходит. Таким образом, каждый раз arr.length уменьшается на единицу, потому что он знает, что последние были помещены туда при сортировке.
Этот вариант исключает более половины итераций, потому что ему не нужно сортировать индексы, которые уже были отсортированы. Однако это только дискретная оптимизация, и событие по-прежнему равно O(n²).
