Сегодня я собираюсь поговорить о быстрой сортировке. Довольно интересно, правда? Раньше я писал о реализации очень простой версии быстрой сортировки в Ruby, но сегодня я хочу использовать Javascript и создать более правильную версию алгоритма.

Правильнее? Да! Я расскажу, почему это так, позже, а также покажу вам пример базовой версии с использованием javascript. Хорошо, пора приступить!

Что такое быстрая сортировка?

Быстрая сортировка - это нестабильная сортировка по принципу «разделяй и властвуй», которая может работать с массивами на месте. Что все это значит?

Разделяй и властвуй

Означает, на что это похоже. Алгоритм «разделяй и властвуй» разбивает проблему на более мелкие подзадачи и решает их, объединяя решения подзадач, чтобы получить решение всей проблемы.

Нестабильный

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

Допустим, у вас есть три игральные карты: бубновый король, семерка треф и король пик в указанном порядке.

K♦, 7♣, K♠

Вы хотите расположить эти карты в порядке возрастания их стоимости.

Стабильная сортировка увидит, что два короля имеют одинаковое значение, и оставит бубнового короля перед королем пик.

7♣, K♦, K♠

Нестабильный сорт может поменять местами двух королей и поставить Бубнового Короля после Пикового Короля.

7♣, K♠, K♦

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

Сравнительная сортировка

Алгоритм сравнительной сортировки считывает все значения в списке за одну операцию сравнения. Часто сортировка выполняется путем проверки того, меньше ли одно значение другому или равно ему.

Есть правила, которым должна следовать операция сравнения. Первый - это транзитивность. По сути, вы должны уметь точно выводить логику от операции к операции. Возьмем этот пример:

a ≤ b ≤ c

Используя операцию «меньше или равно», мы должны иметь возможность точно вывести, что:

a ≤ c

Вот что мы подразумеваем под транзитивностью. Вот определение Мерриам Вебстер, если вы хотите его прочесть:

Транзитивность: являясь или относящаяся к отношению со свойством, что, если отношение выполняется между первым элементом и вторым и между вторым элементом и третьим, оно сохраняется между первым и третьим элементами.

Другое правило состоит в том, что операция должна быть трихотомической. Это означает, что для любых двух пар одно из трех должно быть истинным. Итак, для сравнения a с b:

a < b, a > b, or a = b

Большой! Двигаемся дальше.

Алгоритмы на месте

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

Я читал некоторые дискуссии о том, является ли быстрая сортировка на самом деле алгоритмом на месте из-за того, что он имеет пространственную сложность O (log (n)). Технически, насколько я понимаю, алгоритм на месте должен иметь пространственную сложность только O (1). Но почему-то быстрая сортировка почти всегда упоминается как алгоритм на месте.

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

Для наших целей здесь и здесь только на месте алгоритм ...

Алгоритм, в котором обрабатываемые данные не покидают свою структуру данных.

Поэтому, если в вашу функцию передан массив, вы перемещаете только элементы массива внутри него и не удаляете их из исходного массива. Для функции сортировки в Javascript возвращаемое значение должно быть исходным массивом, который был передан, и не должно быть Array.prototype.pop () или Array.prototype.splice () или что-нибудь еще, что извлекает данные из массива.

В этом большая разница между базовой реализацией, о которой я писал на Ruby, и более правильной версией, которую я собираюсь вам показать. В конце я расскажу об этом подробнее и покажу вам JS-версию той же реализации.

Большой! Перейдем к алгоритму.

Шаги быстрой сортировки

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

  1. Выберите элемент, называемый точкой поворота, из массива.
  2. Секционирование: измените порядок массива так, чтобы все элементы со значениями, меньшими, чем точка поворота, располагались перед точкой поворота, а все элементы со значениями, превышающими точку поворота, располагались после нее (равные значения могут быть в любом случае). После этого разбиения стержень находится в окончательном положении. Это называется операцией разбиения.
  3. Рекурсивно примените вышеуказанные шаги к подмассиву элементов с меньшими значениями и отдельно к подмассиву элементов с большими значениями.

Хорошо, пойдем!

Шаг 1

Выберите элемент, называемый опорной точкой, из массива.

Немного расплывчато, правда? Как мы узнаем, какой элемент выбрать? Есть ли правильный или неправильный способ выбора?

Нет неправильного пути. Кто-то выбирает первый элемент, кто-то последний или средний, а кто-то выбирает медиану из трех.

Если вы выберете первый или последний элемент, вы получите наихудшее время выполнения для уже отсортированных массивов, что мне кажется очень глупым. Он уже отсортирован, так что моя функция сортировки не должна много работать, верно? Эта проблема решается путем выбора случайного элемента, медианы или просто элемента посередине. Начнем с середины:

Потрясающие. У нас есть основная ценность! Следующий шаг!

Шаг 2

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

Мы собираемся использовать метод разделения, называемый схемой разделения Хора, названный в честь сэра Чарльза Энтони Ричарда Хора, который разработал алгоритм быстрой сортировки.

Этот метод работает путем создания двух указателей, называемых «левым» и «правым», и размещения их на обоих концах массива. Два указателя перемещаются к центру, пока каждый не найдет пару элементов, находящихся в неправильном месте. Два элемента переключаются, и процесс продолжается до тех пор, пока все элементы не будут разделены на два подмассива, при этом левые значения будут меньше или равны оси поворота, а правые значения - больше оси поворота.

Не волнуйтесь, если это еще не имеет смысла. Мы разберем это кодом. Во-первых, давайте создадим нашу функцию разделения и настроим два указателя.

Раздел должен принять массив, индекс левого указателя (мы увидим почему позже), индекс правого указателя и значение поворота.

Итак, теперь нам нужно переместить наши указатели к центру, пока они не найдут элементы, которые нужно переключить.

Большой! Итак, как только эти циклы while достигнут своего условия выхода, мы будем знать, что элементы, на которые они указывают, необходимо переключить. Посмотрим, как это отразится на практике.

Скажем, у нас есть этот массив:

let arr = [1, 3, 7, 4, 5, 2, 6]

Предположим, что мы выбрали опорную точку 4. Мы бы использовали 0 для нашего левого значения и 6 как наше правое значение для нашего первого вызова, потому что мы хотим разбить весь массив.

Примечание: позже, когда мы начнем рекурсивно вызывать быструю сортировку, мы захотим разделить только часть нашего массива, поэтому я установил left и right в качестве аргументов для передачи, а не жестко закодировал их как 0 и arr.length -1.

Итак, наш первый цикл while будет продолжать перемещать левый указатель, пока не достигнет 7 в индексе 2.

Наш второй цикл while будет перемещать правый указатель, пока он не достигнет 2 в индексе 5.

Следующее, что нам нужно сделать, это переключить эти элементы, чтобы наш массив выглядел так:

[1, 3, 2, 4, 5, 7, 6]

Обратите внимание, как элементы разделены вокруг этих 4? Все, что слева от 4, меньше, а все, что справа, больше. Вот чего мы хотим!

Добавим это к нашей статистической сумме. Сначала мы проверим, находится ли левый указатель по-прежнему слева от правого указателя, а затем поменяем элементы.

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

Итак, давайте начнем с перемещения левого и правого указателей после нашей замены, так как два элемента, на которые они сейчас указывают, находятся в правильном месте. Затем мы можем заключить все это в цикл while, который завершится, когда левый указатель пройдет мимо правого указателя. Это будет означать, что весь массив разбит на разделы.

Большой! Теперь этот процесс будет повторяться до тех пор, пока массив действительно не будет разбит на разделы вокруг этого значения поворота. Переходим к шагу 3!

ИЗМЕНИТЬ: см. последний фрагмент кода внизу статьи. Добавлена ​​дополнительная проверка для массивов с одинаковым значением. В строке 3 этого кода должно быть указано while (arr[left] < pivot && left <= right)

Шаг 3

Рекурсивно примените описанные выше шаги к подмассиву элементов с меньшими значениями и отдельно к подмассиву элементов с большими значениями.

Отличная рекурсия! Это смешно. Итак, сначала нам нужно создать базовый случай, чтобы наша функция не вызывала себя бесконечное количество раз.

Мы собираемся сделать это, передав еще два аргумента нашей функции быстрой сортировки. Это будут дополнительные «левые» и «правые» указатели, которые мы будем использовать для разделения массива на его подмассивы для будущих рекурсивных вызовов.

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

Наш базовый случай будет всякий раз, когда эти два указателя встречаются друг с другом (что будет означать, что наш подмассив имеет длину 1).

Обратите внимание, что здесь, в строке 3, мы также изменили определение точки поворота. Нам нужно убедиться, что точка поворота находится на полпути между левым и правым указателями, а не только на полпути через массив.

Большой! Теперь у нас есть базовый вариант и точка поворота. Итак, давайте подключим нашу функцию разделения!

Потрясающие! Теперь нам просто нужно…

Хм…

Ну, нам нужно рекурсивно вызывать быструю сортировку для левого и правого подмассивов, верно? Но мы не знаем, где находится наша точка поворота в массиве, теперь, когда все было поменяно местами и перемещено. Без этого мы не сможем узнать, где начинаются и заканчиваются подмассивы.

Что мы можем сделать?

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

Когда мы выходим из цикла while в строке 2, наш левый указатель будет в индексе справа от точки поворота! Дикий, правда? Взгляните на наш пример массива ранее:

[1, 3, 7, 4, 5, 2, 6]

После разрыва цикла while массив будет выглядеть так:

[1, 3, 2, 4, 5, 7, 6]

Наш цикл while в строке 2 прерывается, когда левый указатель проходит вправо, что происходит, когда «left» указывает на 5 (или индекс 4). Это элемент справа от оси поворота, что означает, что здесь заканчивается левый подмассив и начинается правый.

Довольно полезно, да? Давайте просто вернемся слева от нашей функции разделения и установим для нее переменную в нашей функции быстрой сортировки.

Снова читаем третий шаг:

Рекурсивно примените описанные выше действия к подмассиву элементов с меньшими значениями и отдельно к подмассиву элементов с большими значениями.

Теперь, когда мы знаем, где эти подмассивы начинаются и заканчиваются, мы можем рекурсивно вызвать для них быструю сортировку. Давай сделаем это!

Теперь осталось только вернуть наш массив. Помните, поскольку мы работаем на месте, нашим возвращаемым значением будет исходный массив.

Итак, наш код выглядит так:

На месте, часть 2

Помните, я сказал, что данные никогда не покинут исходную структуру данных при реализации на месте? Этого мы достигли, применив схему разбиения Хоара и все эти указатели. Существует множество реализаций быстрой сортировки, которые выглядят примерно так:

Видите, как мы помещаем эти элементы в новые массивы в строке 8? Это данные, покидающие исходную структуру данных, что означает, что эта реализация не на месте. Мы также создаем новые массивы для хранения наших значений, что требует дополнительной памяти. Как только вы начинаете сортировать списки из миллиона с лишним элементов, между этими двумя реализациями становится заметна разница в производительности.

Заключение и фрагменты кода

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

Быстрая сортировка

function basicQuicksort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr.splice(Math.floor(Math.random() * (arr.length - 1)), 1);
  const left = [];
  const right = [];
  arr.forEach(el => el < pivot ? left.push(el) : right.push(el));
  const sortedLeft = basicQuicksort(left);
  const sortedRight = basicQuicksort(right);
  return [...sortedLeft, ...pivot, ...sortedRight];
}

Быстрая сортировка со схемой разбиения Хоара

function quicksort(arr, left = 0, right = arr.length - 1) {
  if (left >= right) return;
  const pivot = arr[Math.floor((left + right) / 2)];
  const index = partition(arr, left, right, pivot);
  quicksort(arr, left, index - 1);
  quicksort(arr, index, right);
  return arr;
}
function partition(arr, left, right, pivot) {
  while (left <= right) {
    while (arr[left] < pivot && left <= right) {
      left++;
    }
    while (arr[right] > pivot) {
      right--;
    }
    if (left <= right) {
      [arr[left], arr[right]] = [arr[right], arr[left]];
      left++;
      right--;
    }
  }
  return left;
}