Пошаговое руководство по алгоритму JavaScript

Алгоритмы, алгоритмы, алгоритмы! Веселая штука! И нет, я не саркастичен, мне очень нравится эта логика! Не стесняйтесь @ me, когда я обращаюсь к двоичным деревьям и другим структурам данных, потому что тогда я могу петь другую мелодию. На данный момент я все еще работаю над более простыми алгоритмами, так что в Шондалэнде все хорошо!

Подобно большинству представителей высшего общества Лондона эпохи Регентства, пузырьковая сортировка является одним из самых неэффективных алгоритмов. Его неэффективное время работы, O (n²), могло сравниться только с неспособностью Дафны и Энтони Бриджертонов зажечь простую плиту для нагрева молока. Вы НЕ хотите, чтобы братья и сестры Бриджертона находились на кухне больше, чем вы хотели бы использовать пузырьковую сортировку для больших массивов (если вы в конечном итоге ее используете). Подобно тому, как есть люди, лучше подходящие для кухни, существуют алгоритмы, лучше подходящие для сортировки списков. Просто нужно было убрать это с дороги, прежде чем мы пойдем дальше.

Весь смысл пузырьковой сортировки состоит в том, чтобы сравнить каждую пару соседних значений в массиве. Выполняя итерацию по массиву, нужно проверять каждую пару чисел. Если первое значение больше второго, то вы меняете позиции. Наибольшее значение откладывается крайним правее после каждой итерации.

Распад Бриджертона: если бы мы представили королеве массив Фезерингтонов для сортировки по социальному статусу, и Пруденс неожиданно потерпела крах, ее социальный статус также резко упал (теперь она является Фезерингтоном самой низкой ценности по сравнению с ее сестрами).

let Featheringtons = ["Philipa","Prudence","Penelope"]
if (Philipa > Prudence), then we will swap their positions.

При сравнении первых двух значений Philipa и Prudence, Prudence будет иметь меньшее значение и, следовательно, поменяется местами с Philipa, которому удалось оставаться в вертикальном положении, приветствуя королеву. Это будет новый массив.

let Featheringtons = ["Prudence", "Philipa","Penelope"]

Итак, чтобы было ясно, если мы сортируем массив в порядке возрастания, алгоритм начнется со сравнения первой пары значений, Philipa и Prudence. Поскольку статус Филиппы выше, чем у Пруденс, они поменяются местами, и Пруденс теперь находится в начале списка - там, где нам нужны самые низкие значения. Затем мы переходим к следующей паре, Филиппе и Пенелопе. Он будет сравнивать их и соответственно сортировать и так далее, пока массив не будет отсортирован.

Итерация Бриджертона: [Филипа, Пруденс, Пенелопа] → [Пруденс, Филипа, Пенелопа] → [Пруденс, Пенелопа, Филипа]

Числовая итерация: [5,3, 4] → [3 , 5,4] → [3,4,5]

Теперь, когда мы поняли суть, давайте перейдем к мелочам.

let array = [95, 31, 19, 7]

function bubbleSort(arr){
  let swap = (arr, a, b) => ([arr[a], arr[b]] = [arr[b], arr[a]])
  let swapped
  for(let i = arr.length; i > 0; i --){
    swapped = false
    for(let j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        swap(arr, j, j+1)
        swapped = true
      }
    }
    if(!swapped)break
  }
  return arr
}
  1. Первое, что мне нравится делать при написании моей функции пузырьковой сортировки, - это немедленно определять функцию «подкачки» для переключения элементов в массиве. Функция подкачки принимает 3 аргумента: массив, индекс1 и индекс2.
let swap = (arr, a, b) => ([arr[a], arr[b]] = [arr[b], arr[a]])

Он примет исходный порядок index1 и index2 и переключит их, как показано выше.

Я решил инкапсулировать свою функцию подкачки в переменной в моей функции пузырьковой сортировки, но вы также можете написать отдельную вспомогательную функцию для вызова внутри вашей функции пузырьковой сортировки, если это имеет для вас больше смысла.

2. Затем я создаю замененную переменную, чтобы использовать ее позже в моем коде. Будет установлено логическое значение, чтобы проверить, поменялись ли числа местами после завершения внутреннего цикла.

3. Теперь мы начинаем наш внешний цикл for. Этот цикл будет перебирать массив в обратном направлении. Мы начинаем с конца, потому что, как упоминалось ранее, array [3] (последний индекс массива) - это позиция, в которой самое большое значение, 95, окажется в конце первой итерации внутреннего цикла. Первоначально мы установили для swapped значение false. (Мы вернемся к этому позже.)

let array = [95, 31, 19, 7]

function bubbleSort(arr){
  let swap = (arr, a, b) => ([arr[a], arr[b]] = [arr[b], arr[a]])
  let swapped
  for(let i = arr.length; i > 0; i --){
    swapped = false
  }
}

4. Далее идет наш внутренний цикл, который повторяется с начала массива и предназначен для сравнения каждой пары значений с помощью условного оператора. Если currentElement ›nextElement, мы вызовем нашу удобную функцию подкачки. Помните, Пруденс заставила королеву недовольно скривиться и имеет наименьшее значение, поэтому ее меняют с сестрой на передний план. То же самое и здесь. Поскольку своп был выполнен, мы обновляем нашу переменную swapped до значения true. В приведенном ниже примере 95 и 31 поменяются местами после первой итерации внутреннего цикла.

let array = [95, 31, 19, 7]

function bubbleSort(arr){
  let swap = (arr, a, b) => ([arr[a], arr[b]] = [arr[b], arr[a]])
  let swapped
  for(let i = arr.length; i > 0; i --){
    swapped = false
    for(let j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        swap(arr, j, j+1)
        swapped = true
      }
    }
  }
  return arr
}

5. Здесь мы делаем все, что в наших силах, чтобы повысить эффективность этого ужасно сложного по времени алгоритма, выйдя из внутреннего цикла, если массив уже отсортирован в порядке возрастания. Проверяя swapped с помощью оператора bang, мы говорим, что если НЕ swapped, выйдите из этого внутреннего цикла. Помните, что мы меняем местами только если currentEle ›nextEle, поэтому, если это условие никогда не было выполнено, это потому, что массив уже отсортирован в порядке возрастания. Следовательно, у нас больше нет необходимости в цикле, и мы можем выйти из него.

let array = [95, 31, 19, 7]

function bubbleSort(arr){
  let swap = (arr, a, b) => ([arr[a], arr[b]] = [arr[b], arr[a]])
  let swapped
  for(let i = arr.length; i > 0; i --){
    swapped = false
    for(let j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        swap(arr, j, j+1)
        swapped = true
      }
    }
    if(!swapped)break
  }
  return arr
}

Верните массив за пределы внешнего цикла for, чтобы убедиться, что все итерации выполнены, и все готово!