Информатика в JavaScript: Быстрая сортировка (Quicksort)

Published in

devSchacht

6 min readApr 26, 2017

Перевод статьи Nicholas C. Zakas: Computer science in JavaScript: Quicksort.

Большинство дискуссий по поводу алгоритмов сортировки, как правило, заканчиваются обсуждением алгоритма быстрой сортировки из-за его скорости. Курсы информатики, как правило, охватывают quicksort¹ потому, что он имеет отличный показатель средней сложности O(n log n) и относительно высокую производительность по сравнению с другими, менее эффективными алгоритмами вроде buble sort или insert sort для больших наборов данных. В отличие от других алгоритмов сортировки, существует множество различных реализаций quicksort, одни направлены на повышение производительности, другие — на устойчивость (эквивалентные элементы, остаются в том же порядке, в котором они изначально встречаются).

Быстрая сортировка — это “разделяй и властвуй” алгоритм в стиле “сортировка слиянием”. Основная идея заключается в том, чтобы найти опорный элемент в массиве для сравнения с остальными частями, затем сдвигать элементы так, чтобы все части перед опорным элементом были меньше его, а все элементы после опорного были больше его. После этого рекурсивно выполнить ту же операцию на элементы до и после опорного. Существует множество различных алгоритмов для достижения быстрой сортировки, в этой статье рассматривается только один из них.

Существует две базовые операции в алгоритме: замена элемента на месте и разбиение массива на части. Основные шаги для разделения массива:

Найти опорный элемент в массиве. Этот элемент — основа для сравнения за одни проход.
Установить указатель (левый указатель) с первого элемента в массиве.
Установить указатель (правый указатель) с последнего элемента в массиве.
Пока значение левого указателя в массиве меньше, чем значение опорного элемента, сдвигать левый указатель вправо (добавить 1). Продолжить пока значение левого указателя не станет большим или равным опорному.
Пока значение правого указателя в массиве больше, чем значение опорного элемента, сдвигать правый указатель влево (вычитать 1). Продолжать пока значение правого указателя не станет меньшим или равным значению разделителя.
Если левый указатель меньше или равен правому указателю, поменять значения в этих местах в массиве.
Сдвинуть левый указатель вправо на одну позицию и правый указатель на одну позицию влево.
Если левый указатель и правый указатель не встретятся, перейти к шагу 1.

Как и многие другие алгоритмы, эти распределения проще понять, глядя на пример. Предположим, у вас есть следующий массив:

var items = [4, 2, 6, 5, 3, 9];

Существует множество способов найти значение разделителя. Некоторые алгоритмы берут первый элемент в качестве опорного. Это не самый лучший выбор, потому что он дает наихудшие показатели для уже отсортированных массивов. Лучше взять в качестве разделителя элемент из середины, для нас разделителем будет 5 (длинна массива, разделенная на 2). Далее установим левый указатель на нулевую позицию и правый указатель на позицию 5 (последний элемент в массиве). Поскольку 4 меньше 5, переместим левый указатель на 1 позицию. Поскольку 2 меньше 5, переместим левый указатель во вторую позицию. Сейчас 6 не меньше 5, перестаем сдвигать левый указатель и начинаем сдвигать правый. Так как 9 больше 5, правый указатель перемещаем на позицию 4. Значение 3 не больше 5, поэтому правый указатель останавливается. Поскольку левый указатель находится в положении 2, а правый указатель в положении 4, и эти два элемента не встречались, значения 6 и 3 должны быть поменяны местами.

Далее, левый указатель увеличивается на единицу, а правый уменьшается на единицу. В обоих случаях значение будет равно опорному элементу (5). Это сигнализирует, что операция завершена. Теперь все элементы в массиве слева от разделителя меньше, чем сам разделитель и все элементы справа от разделителя больше него самого. Имейте в виду, что это не значит, что массив уже отсортирован, только то, что есть две части массива: секция, где все значения меньше, чем опорный элемент, и секции, где все значения больше опорного элемента. Смотрим рисунок ниже:

Реализация функции разбиения использует функцию swop(), код этой функции:

function swap(items, firstIndex, secondIndex){
    const temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
}

Функция разделитель сама по себе довольно проста и следующий алгоритм почти точен.

function partition(items, left, right) {    var pivot   = items[Math.floor((right + left) / 2)],
        i       = left,
        j       = right;
    while (i <= j) {        while (items[i] < pivot) {
            i++;
        }        while (items[j] > pivot) {
            j--;
        }        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }    return i;
}

Эта функция принимает три аргумента: items - массив для сортировки, left - индекс, устанавливающий левый указатель, и right, устанавливающий правый указатель. Опорный элемент определяется путем сложения left и right значений и делением этой суммы на 2. Так как это значение может быть числом с плавающей точкой, необходимо выполнить округление. В данном случае, я решил использовать функцию Math.floor, но вы можете точно также использовать функцию Math.ceil или Math.round с немного другой логикой. Переменная i - левый указатель, а переменная j - правый.

Весь алгоритм — просто цикл из циклов. Внешний цикл определяет, когда все элементы массива были обработаны. Два внутренних цикла управляют движением левого и правого указателей. Когда оба из внутренних циклов завершены, то указатели сравниваются, чтобы определить, необходимо ли их поменять местами. После замены, оба указателя сдвигаются, так что внешний цикл продолжается с нужного места. Функция возвращает значение левого указателя, это нужно, чтобы определить, откуда начинать разметку в следующий раз. Имейте в виду, что разбиение происходит на месте, без создания дополнительных массивов.

Алгоритм quicksort в основном работает путем разбиения всего массива, а затем рекурсивного разбиения левой и правой частей массива до тех пор, пока весь массив не будет отсортирован. Левая и правая части массива определяют индекс и возвращают его значение после каждой операции. Этот индекс фактически становится границей между левой и правой частями массива. В предыдущем примере массив стал [4, 2, 3, 5, 6, 9], а после первого прохода индекс становится равным 4 (последнее место левого указателя). После этого, левая часть массива (элементы с 0 по 3) разбивается, как показано на следующем рисунке.

После этого прохода массив будет [3, 2, 4, 5, 6, 9], а в качестве индекса вернется 1. Эта "пульсация" будет продолжаться до тех пор, пока левая сторона массива не будет отсортирована. Затем те же процессы пройдут по правой стороне массива. Основной логарифм для быстрой сортировки довольно прост:

function quickSort(items, left, right) {    var index;    if (items.length > 1) {        index = partition(items, left, right);        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }        if (index < right) {
            quickSort(items, index, right);
        }    }    return items;
}
// first call
var result = quickSort(items, 0, items.length - 1);

Функция quicksort() принимает три аргумента: массив для сортировки, индекс для установки левого указателя и индекс для установки правого указателя. Для оптимизации производительности, массив не будет отсортирован, если у него ноль или один элемент. Если в массиве два или более элементов, он является "разбиваемым". Если left меньше, чем возвращенный index минус единица, то слева еще остались элементы для сортировки и функция quickSort()вызывается для них рекурсивно. Аналогичным образом, если index меньше правого указателя, то элементы справа сортируются. Как только все это сделано, массив возвращается в качестве результата.

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

function quickSort(items, left, right) {    var index;    if (items.length > 1) {        left = typeof left != "number" ? 0 : left;
        right = typeof right != "number" ? items.length - 1 : right;        index = partition(items, left, right);        if (left < index - 1) {
            quickSort(items, left, index - 1);
        }        if (index < right) {
            quickSort(items, index, right);
        }    }    return items;
}// first call
var result = quickSort(items);

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

Quicksort, как правило, считается самой эффективной и быстрой и поэтому используется в V8 как реализация Array.prototype.sort() для массивов с более чем 23 элементами. Для менее чем 23 элемента в V8 используется insertion sort2. Merge sort - конкурент quicksort, аналогично ему он также эффективный и быстрый, но имеет дополнительное преимущество - устойчивость. Поэтому Mozilla и Safari используют его для имплементации Array.prototype.sort().

Слушайте наш подкаст в iTunes и SoundCloud, читайте нас на Medium, контрибьютьте на GitHub, общайтесь в группе Telegram, следите в Twitter и канале Telegram, рекомендуйте в VK и Facebook.

Ссылка на github

Информатика в JavaScript: Быстрая сортировка (Quicksort)

Written by Vladislav Khvostov