Что такое пузырьковый сортировщик и как его собрать
Сегодня давайте посмотрим, как работает пузырьковый сортировщик. Я сделаю все возможное, чтобы разбить каждый шаг того, что происходит и как все работает. Как и во всем, что связано с программированием, обычно существует много разных способов сделать что-то. Я покажу вам способ, которым я сначала научился строить сортировщик пузырей.
Что такое пузырьковый сортировщик?
Сортировщик пузырьков берет первое число в массиве и второе число в массиве и решает, какое число больше. Он будет продолжать перемещать большее число вправо, пока не дойдет до конца массива или не найдет большее число. Если он найдет большее число, он захватит это число и продолжит перемещать его вправо. Как только он дойдет до конца массива, он оставит наибольшее найденное число, а затем начнет процесс с начала массива. Он будет продолжать делать это до тех пор, пока не завершит перемещение чисел в правильном порядке.
Поехали!
Первое, что нам нужно сделать, это запустить функцию пузырькового сортировщика и получить пару массивов, чтобы ей было чем заняться. Для одного массива мы можем использовать маленькие числа, расположенные близко друг к другу. С другой стороны, у нас будет набор чисел, чтобы проверить это.
При такой настройке у нас будет функция с именем bubbleSort
, и у нее будет аргумент, который я назову array. Мы вызовем функцию, чтобы она запускалась при запуске файла.
Чтобы упростить задачу, давайте создадим const
, чтобы нам не приходилось вводить array.length
больше одного раза. Вы можете называть переменные как хотите, но в этой статье я хочу, чтобы они были как можно более информативными. При этом нам также нужно настроить первый for loop
, чтобы посмотреть, можем ли мы перебирать числа в наших массивах.
Внутри начального for loop
мы добавим еще один for loop
. Это похоже на начало for loo
p. Внутренний цикл - это цикл, который выполняет всю работу. Внутри этого цикла мы проведем проверки, чтобы увидеть, какое число больше, и решить, будет ли оно сдвинуто или останется на прежнем месте. Внутренний for loop
будет продолжать работать, пока не переместится в конец массива.
После этого мы вернемся к первому for loop
и начнем весь процесс заново. Он снова начнет перемещаться по всем числам, захватывая наибольшее число, и продолжит движение вправо, пока не найдет второе по величине число, и так далее.
Когда я впервые взглянул на код работы пузырькового сортировщика, все выглядело нормально и имело смысл, пока я не нажал на оператор if
. Когда я дошел до этой части, я не мог полностью понять, что происходит. Так что, если вы смотрите на этот код и думаете, что заблудились, это совершенно нормально, и я понимаю это чувство на 100%. Я объясню это как можно лучше здесь. Затем я воспользуюсь числами из array2
, чтобы немного прояснить ситуацию.
Оператор if
будет выполняться только в том случае, если число слева больше числа справа. Сравнение проводится между числом в индексе J и числом в индексе J плюс 1. Поскольку мы хотим переместить число в индексе J вправо, мы используем переменную для хранения его значения. В следующей строке мы говорим, что число в индексе J теперь такое же, как число в индексе J плюс 1. Мы не хотим иметь меньшее число в двух местах, поэтому с третьей строкой внутри оператора if мы помещаем большее число в позицию справа, то есть индекс J плюс 1. После этого мы переходим к следующему числу и повторяем, пока не дойдем до конца.
array2 = [800, 32, 91, 8, 1032, 473, 981, 218, 1031, 1]
Давайте на этот раз разберем, что происходит внутри оператора if
, используя числа. Это помогло мне лучше понять, что происходит.
Первые два числа, которые мы проверяем, - 800 и 32. 800 больше 32, поэтому мы перейдем к оператору if
. В первой строке let bigNumber
= 800 мы используем эту переменную для хранения значения 800 для нас, пока мы перемещаем число 32 влево. Во второй строке мы говорим, что хотим изменить значение 800 (J) на 32 (J + 1).
Если бы мы остановились на этом, первые два числа нашего массива были бы 32, потому что прямо сейчас мы говорим, что значение J равно значению J + 1. Это не то, что мы хотим. Итак, в последней строке мы хотим поместить 800 в слот справа. Вот почему мы используем J + 1, равный bigNumber
.
После этого наш for loop
будет работать. Теперь J снова будет 800, а J + 1 будет теперь 91. Тогда bigNumber
будет равно 800, а J и J + 1 оба будут 91. Мы снова бросим 800 в точку справа, так что теперь первые три числа в нашем array2
- 32, 91, 800. Оператор if
будет выполняться снова, потому что 800 больше 8. Но когда мы дойдем до сравнения 800 с 1032, мы не будем вдаваться в оператор if
, потому что 800 теперь является меньшее количество.
Описанный выше процесс повторяется снова и снова, пока мы не дойдем до конца массива. Таким образом, при первом проходе по массиву последним числом будет 1032. Поскольку мы достигли последней точки массива, внутренний for loop
завершится. Но поскольку внешний for loop
все еще имеет индекс 0, он переместится в индекс 1 и снова запустит процесс. Цель внешнего for loop
- убедиться, что мы пройдемся по массиву достаточно раз, чтобы полностью отсортировать все числа.
Есть и другие способы сделать пузырьковый сортировщик более эффективным, например, уменьшать длину массива после каждого прохода, потому что мы знаем, что последнее число является наибольшим, поэтому нам не нужно его проверять. Кроме того, мы могли бы установить его с помощью do-while loop
, и если он не меняет местами какие-либо числа на проходе, он остановится на этом, потому что массив был отсортирован.
Заключение
Если вы хотите отсортировать массив, я бы не рекомендовал пузырьковый сортировщик. Мне нравится создавать подобные вещи для развлечения, но для практических целей с JavaScript вы можете использовать что-то вроде этого:
Подробнее читайте в MDN Sort.
Я ценю, что вы нашли время прочитать это. Надеюсь, вы нашли это информативным. Мне было очень весело разбирать это, печатать это и помогать себе закрепить то, что я изучаю в этом путешествии по программированию.