Распространенные алгоритмы сортировки с примерами на JavaScript

0
1854
views

Перевод статьи «Common Sorting Algorithms in JavaScript».

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

Мы рассмотрим следующие алгоритмы:

  • Сортировка пузырьком
  • Сортировка выбором
  • Сортировка вставками
  • Сортировка слиянием
  • Быстрая сортировка
  • Блочная сортировка

Примечание редакции Techrocks: объяснение алгоритмов сортировки с примерами на Python смотрите здесь.

Вспомогательные методы для перемены местами и сравнения

Мы часто будем менять местами элементы в массивах, поэтому давайте начнем с написания вспомогательного метода swap:

function swap(arr, a, b) {
    let temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

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

const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
};

function defaultCompare(a, b) {
    if (a === b) {
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

Хорошо, с этим мы разобрались, можно переходить к сортировкам!

Сортировка пузырьком

Временная сложность в наилучшем случае — O(N), в наихудшем — O(N^2).

Сортировка пузырьком

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

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

Сортировка пузырьком
function bubbleSort(arr, compare = defaultCompare) {
    const { length } = arr;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) { // refer to note below
            if (compare(arr[j], arr[j + 1]) === Compare.BIGGER_THAN) {
                swap(arr, j, j + 1);
            }
        }
    }
    return arr;
}

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

Сортировка выбором

Временная сложность в наилучшем и наихудшем случае — O(N^2).

Сортировка выбором

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

Сортировка выбором
function selectionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let minIndex;
    for (let i = 0; i < length - 1; i++) {
        minIndex = i;
        for (let j = i; j < length; j++) {
            if (compare(arr[minIndex], arr[j]) === Compare.BIGGER_THAN) {
                minIndex = j;
            }
        }
        if (i !== minIndex) {
            swap(arr, i, minIndex);
        }
    }
    return arr;
}

Следующая диаграмма показывает алгоритм сортировки выбором в действии:

Сортировка вставками

Временная сложность в наилучшем случае — O(N), в наихудшем — O(N^2).

Сортировка вставками

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

  1. Предполагаем, что первый элемент уже отсортирован.
  2. Сравниваем первый элемент со вторым: должно ли второе значение остаться на месте или же оно должно быть вставлено перед первым значением?
  3. Далее аналогичное сравнение делается для третьего значения: должно ли оно быть вставлено на первую, вторую или третью позицию? И так далее.
function insertionSort(arr, compare = defaultCompare) {
    const { length } = arr;
    let temp;
    for (let i = 1; i < length; i++) {
        let j = i;
        temp = arr[i];
        while (j > 0 && compare(arr[j - 1], temp) === Compare.BIGGER_THAN) {
            arr[j] = arr[j - 1];
            j--;
        }
        arr[j] = temp;
    }
    return arr;
}

На диаграмме вы видите пример сортировки вставками в действии:

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

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

Временная сложность в наилучшем и наихудшем случае — O(N Log N).

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

Алгоритм сортировки слиянием это один из алгоритмов «разделяй и властвуй»). Другими словами, он делит исходный массив на более мелкие массивы, пока каждый маленький массив не будет содержать всего одну позицию, а затем сливает маленькие массивы в более крупный и отсортированный.

Здесь реализация рекурсивная. Она состоит из двух функций: одна для деления массивов на более мелкие, а другая — для осуществления сортировки.

function mergeSort(arr, compare = defaultCompare) {
    if (arr.length > 1) {
        const { length } = arr;
        const middle = Math.floor(length / 2);
        const left = mergeSort(arr.slice(0, middle), compare);
        const right = mergeSort(arr.slice(middle, length), compare);
        arr = merge(left, right, compare);
    }
    return arr;
}

function merge(left, right, compare) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(compare(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++]);
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

Вот диаграмма для визуализации процесса:

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

Временная сложность в наилучшем/среднем случае — O(N Log N), в наихудшем — O(N^2).

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

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

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

  1. Выбираем значение в массиве, которое назовем опорным. Обычно это значение в середине массива.
  2. Осуществляем операцию распределения, в результате которой значения меньше опорного смещаются влево от опорного, а большие — вправо от него.
  3. Повторяем первые два шага для каждого подмассива (левого и правого), пока массивы не будут полностью отсортированы.
function quickSort(arr, compare = defaultCompare) {
    return quick(arr, 0, arr.length - 1, compare);
}

function quick(arr, left, right, compare) {
    let i;
    if (arr.length > 1) {
        i = partition(arr, left, right, compare);
        if (left < i - 1) {
            quick(arr, left, i - 1, compare);
        }
        if (i < right) {
            quick(arr, i, right, compare);
        }
    }
    return arr;
}

function partition(arr, left, right, compare) {
    const pivot = arr[Math.floor((right, left) / 2)];
    let i = left;
    let j = right;

    while (i <= j) {
        while (compare(arr[i], pivot) === Compare.LESS_THAN) {
            i++;
        }
        while (compare(arr[j], pivot) === Compare.BIGGER_THAN) {
            j--;
        }
        if (i <= j) {
            swap(arr, i, j);
            i++;
            j--;
        }
    }
    return i;
}

Блочная сортировка

Временная сложность в наилучшем/среднем случае — O(N + k), в наихудшем — O(N^2).

Блочная сортировка
function bucketSort(arr, bucketSize) {
    if (arr.length < 2) {
        return arr;
    }
    // create buckets and distribute the elements
    const buckets = createBuckets(arr, bucketSize);
    // sort the buckets using insertion sort and add all bucket elements to sorted result 
    return sortBuckets(buckets);
}

function createBuckets(arr, bucketSize) {
    // determine the bucket count
    let min = arr[0];
    let max = arr[0];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < min) {
            min = arr[i];
        } else if (arr[i] > max) {
            max = arr[i];
        }
    }
    const bucketCount = Math.floor((max - min) / bucketSize) + 1;

    // initialize each bucket (a multidimensional array)
    const buckets = [];
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = [];
    }

    // distribute elements into buckets
    for (let i = 0; i < arr.length; i++) {
        const bucketIndex = Math.floor((arr[i] - min) / bucketSize);
        buckets[bucketIndex].push(arr[i]);
    }
    return buckets;
}

function sortBuckets(buckets) {
    const sortedArr = [];
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            insertionSort(buckets[i]); // quick sort is another good option
            sortedArr.push(...buckets[i]);
        }
    }
    return sortedArr;
}

Алгоритм блочной сортировки — это распределенный алгоритм сортировки, который разделяет элементы на разные блоки (или более мелкие массивы), а затем использует более простой алгоритм для сортировки этих маленьких массивов. В роли более простого алгоритма может выступать, например, алгоритм сортировки вставками.

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

Следующая диаграмма показывает алгоритм блочной сортировки в действии:

Заключение

Мы рассмотрели лишь некоторые из наиболее часто встречающихся алгоритмов сортировки. На самом деле таких алгоритмов гораздо больше.

ОСТАВЬТЕ ОТВЕТ

Please enter your comment!
Please enter your name here