14.03.2024 в 10:22

Алгоритм быстрой сортировки

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

Что такое алгоритм быстрой сортировки?

Алгоритм быстрой сортировки - это еще один пример алгоритма "разделяй и властвуй", который берет несортированный массив и, как вы уже догадались, сортирует его! Он работает, выбирая опорный элемент (обычно последний элемент в массиве), а затем добавляя оставшиеся элементы массива в 2 подмассива - один, содержащий все элементы меньше опорного, и второй, содержащий элементы больше или равные опорному. Затем мы повторяем этот шаг на подмассивах, пока весь массив не будет отсортирован. Этот алгоритм имеет среднюю временную сложность O(nlogn), но его наихудший случай - O(n^2), когда массив уже отсортирован, но в обратном порядке.

Как это работает?

Чтобы объяснить, как это работает, приведём псевдокод:

pivot = arr.length -1
smallerItems = []
largerItems = []

for element in array to sort:
    if element < pivot
        add to smallerItems
    else
        add to largerItems

sort(smallerItems)
sort(largerItems)

Как это реализовать?

Вот хорошо прокомментированная реализация на языке Typescript:

function quickSort(arr: number[]): number[] {
    // base case
    if (arr.length <= 1) {
        return arr;
    }

    // select our pivot -- the last element in the array
    const pivot = arr[arr.length - 1];

    // create 2 sub-arrays
    const leftArr: number[] = [];
    const rightArr: number[] = [];

    // loop through the array
    for (let i = 0; i < arr.length - 1; i++) {
        // if the current item is less than the value of our pivot
        // add the item to our leftArr, otherwise, add it to our
        // rightArr
        if (arr[i] < pivot) {
            leftArr.push(arr[i]);
        } else {
            rightArr.push(arr[i]);
        }
    }

    // repeat/recurse this process for our sub arrays
    return [...quickSort(leftArr), pivot, ...quickSort(rightArr)];
}

Альтернативная реализация

Хотя приведенная выше реализация работает, она будет довольно дорогостоящей в плане памяти, поскольку входной массив увеличивается. Альтернативный способ написания этой функции - разбить её на 3 части и сортировать наш массив в строке без необходимости создавать дополнительные массивы. Давайте посмотрим, как это выглядит...

Во-первых, давайте определим наш интерфейс:

function quickSort(arr: number[]): void {}

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

function sort(arr: number[], lo: number, hi: number): void {
    if (lo >= hi) {
        return;
    }

    const pivotIndex = partition(arr, lo, hi);
    sort(arr, lo, pivotIndex - 1);
    sort(arr, pivotIndex + 1, hi);
}

function quickSort(arr: number[]): void {
    sort(arr, 0, arr.length - 1);
}

Наконец, мы создадим третью функцию, которая будет управлять тремя указателями - нашим пивотом, нашим индексом (который начинается с -1) и элементом, который мы проверяем в данный момент (current). Current проходит по массиву, и если элемент меньше или равен нашему пивоту, мы увеличиваем индекс и меняем местами элементы, расположенные по индексу и current. В конце итерации мы увеличиваем наш индекс и меняем местами элементы, находящиеся по адресу index и pivot, а затем возвращаем индекс. Вот как выглядит эта функция:

function partition(arr: number[], lo: number, hi: number): number {
    // set our pivot to the end of the array
    const pivot = arr[hi];

    // set out index to the start of the array -1
    let idx = lo - 1;

    // loop through our array
    for (let i = lo; i < hi; ++i) {
        // if the item is less than or equal to the pivot
        // increment the index, then swap it with the item
        // at the index
        if (arr[i] <= pivot) {
            idx++;
            [arr[i], arr[idx]] = [arr[idx], arr[i]];
        }
    }

    // after we've finished walking the array,
    // increment the index, then swap the item
    // at the pivot with the item at the index
    idx++;
    [arr[hi], arr[idx]] = [arr[idx], arr[hi]];

    // return the index
    return idx;
}

Хорошо, теперь давайте соберем всё воедино:

function partition(arr: number[], lo: number, hi: number): number {
    const pivot = arr[hi];
    let idx = lo - 1;

    for (let i = lo; i < hi; ++i) {
        if (arr[i] <= pivot) {
            idx++;
            [arr[i], arr[idx]] = [arr[idx], arr[i]];
        }
    }
    idx++;
    [arr[hi], arr[idx]] = [arr[idx], arr[hi]];

    return idx;
}

function sort(arr: number[], lo: number, hi: number): void {
    if (lo >= hi) {
        return;
    }

    const pivotIndex = partition(arr, lo, hi);
    sort(arr, lo, pivotIndex - 1);
    sort(arr, pivotIndex + 1, hi);
}

function quickSort(arr: number[]): void {
    sort(arr, 0, arr.length - 1);
}

Благодарю за прочтение, счастливого кодинга!

Источник:

Exit fullscreen mode

#TypeScript