Алгоритмы сортировок на JavaScript

Метод сортировки, который многие обычно осваивают раньше других из-за его исключительной простоты, называется пузырьковой сортировкой (bubble sort), в рамках которой выполняются следующие действия: проход по файлу с обменом местами соседних элементов, нарушающих заданный порядок, до тех пор, пока файл не будет окончательно отсортирован. Основное достоинство пузырьковой сортировки заключается в том, что его легко реализовать в виде программы. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²).

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

function BubbleSort(A)       // A - массив, который нужно
{                            // отсортировать по возрастанию.
    var n = A.length;
    for (var i = 0; i < n - 1; i++) {
        for (var j = 0; j < n - 1 - i; j++) {
            if (A[j + 1] < A[j]) { var t = A[j + 1]; A[j + 1] = A[j]; A[j] = t; }
        }
    }
    return A; // На выходе сортированный по возрастанию массив A.
}

Сортировка выбором начинается с поиска наименьшего элемента в списке и обмена его с первым элементом (таким образом, наименьший элемент помещается в окончательную позицию в отсортированном массиве). Затем мы сканируем массив, начиная со второго элемента, в поисках наименьшего среди оставшихся \( n-1 \) элементов и обмениваем найденный наименьший элемент со вторым, т.е. помещаем второй наименьший элемент в окончательную позицию в отсортированном массиве. В общем случае, при i-ом проходе по списку \( (0\leqslant i\leqslant n-2) \) алгоритм ищет наименьший элемент среди последних \( n-i \) элементов и обменивает его \( A[ i ] \). После выполнения \( n-1 \) проходов список оказывается отсортирован.

function SelectionSort(A)       // A - массив, который нужно
{                               // отсортировать по возрастанию.
    var n = A.length;
    for (var i = 0; i < n - 1; i++) {
        var min = i;
        for (var j = i + 1; j < n; j++) { if (A[j] < A[min]) min = j; }
        var t = A[min]; A[min] = A[i]; A[i] = t;
    }
    return A; // На выходе сортированный по возрастанию массив A.
}

На каждом шаге алгоритма сортировки встаками выбирается один из элементов входного массива и вставляется на нужную позицию в уже отсортированном массиве, до тех пор, пока входных элементы не будут исчерпана. Метод выбора очередного элемента из исходного массива произволен; может использоваться практически любой алгоритм выбора. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. В приведённой ниже реализации на JavaScript алгоритма сортировки встаками используется именно эта стратегия выбора.

function InsertionSort(A)       // A - массив, который нужно
{                               // отсортировать по возрастанию.
    var n = A.length;
    for (var i = 0; i < n; i++) {
        var v = A[i], j = i - 1;
        while (j >= 0 && A[j] > v) { A[j + 1] = A[j]; j--; }
        A[j + 1] = v;
    }
    return A; // На выходе сортированный по возрастанию массив A.
}

function ShellSort(A) {
    var n = A.length, i = Math.floor(n / 2);
    while (i > 0) {
        for (var j = 0; j < n; j++) {
            var k = j, t = A[j];
            while (k >= i && A[k - i] > t) { A[k] = A[k - i]; k -= i; }
            A[k] = t;
        }
        i = (i == 2) ? 1 : Math.floor(i * 5 / 11);
    }
    return A;
}

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

function SimpleCountingSort(A) {
    var n = A.length, Count = [], B = [];
    for (var i = 0; i < n; i++) Count[i] = 0;
    for (var i = 0; i < n - 1; i++) {
        for (var j = i + 1; j < n; j++) {
            if (A[i] < A[j]) Count[j]++;
            else Count[i]++;
        }
    }
    for (var i = 0; i < n; i++) B[Count[i]] = A[i];
    return B;
}

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

function newGap(gap) // Вспомогательная функция.
{
    gap /= 1.3;
    if (gap == 9 || gap == 10) gap = 11;
    if (gap < 1) return 1;
    return gap;
}

function CombSort(A) // Функция сортировки расчёской.
{
    var n = A.length, gap = n;
    do {
        swapped = false;
        gap = newGap(gap);
        for (var i = 0; i < n - gap; ++i) {
            if (A[i] > A[i + gap]) {
                swapped = true;
                var t = A[i + gap]; A[i + gap] = A[i]; A[i] = t;
            }
        }
    } while (gap > 1 || swapped);
    return A;
}

function Merge(a, low, mid, high) //Вспомогательная функция.
{
    var b = new Array(high + 1 - low), h, i, j = mid + 1, k, h = low, i = 0;
    while (h <= mid && j <= high) {
        if (a[h] <= a[j]) { b[i] = a[h]; h++; }
        else { b[i] = a[j]; j++; }
        i++;
    }
    if (h > mid) { for (k = j; k <= high; k++) { b[i] = a[k]; i++; } }
    else { for (k = h; k <= mid; k++) { b[i] = a[k]; i++; } }
    for (k = 0; k <= high - low; k++) a[k + low] = b[k];
    return a;
}

function MergeSort(A) //Функция сортировки слиянияем.
{
    function merge_sort(a, low, high) {
        if (low < high) {
            var mid = Math.floor((low + high) / 2);
            merge_sort(a, low, mid);
            merge_sort(a, mid + 1, high);
            Merge(a, low, mid, high);
        }
    }
    var n = A.length;
    merge_sort(A, 0, n - 1);
    return A;
}

function HeapSort(A) {
    if (A.length == 0) return [];
    var n = A.length, i = Math.floor(n / 2), j, k, t;
    while (true) {
        if (i > 0) t = A[--i];
        else {
            n--;
            if (n == 0) return A;
            t = A[n]; A[n] = A[0];
        }
        j = i; k = j * 2 + 1;
        while (k < n) {
            if (k + 1 < n && A[k + 1] > A[k]) k++;
            if (A[k] > t) { A[j] = A[k]; j = k; k = j * 2 + 1; }
            else break;
        }
        A[j] = t;
    }
}

function QuickSort(A) {
    if (A.length == 0) return [];
    var a = [], b = [], p = A[0];
    for (var i = 1; i < A.length; i++) {
        if (A[i] < p) a[a.length] = A[i];
        else b[b.length] = A[i];
    }
    return QuickSort(a).concat(p, QuickSort(b));
}

Сортировка перемешиванием (шейкерная сортировка, англ. Cocktail sort) — разновидность пузырьковой сортировки.

function CocktailSort(A) //Также называют ShakerSort.
{
    var i = 0,
        j = A.length - 1,
        s = true,
        t;
    while (i < j && s) {
        s = false;
        for (var k = i; k < j; k++) {
            if (A[k] > A[k + 1]) {
                t = A[k];
                A[k] = A[k + 1];
                A[k + 1] = t;
                s = true;
            }
        }
        j--;
        if (s) {
            s = false;
            for (var k = j; k > i; k--) {
                if (A[k] < A[k - 1]) {
                    t = A[k];
                    A[k] = A[k - 1];
                    A[k - 1] = t;
                    s = true;
                }
            }
        }
        i++;
    }
    return A;
}

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

function GnomeSort(A) {
    var n = A.length,
        i = 1,
        j = 2;
    while (i < n) {
        if (A[i - 1] < A[i]) {
            i = j;
            j++;
        } else {
            var t = A[i - 1];
            A[i - 1] = A[i];
            A[i] = t;
            i--;
            if (i == 0) {
                i = j;
                j++;
            }
        }
    }
    return A;
}

Естественная сортировка (англ. Natural sort) — простая и эффективная модификация сортировки слиянием, которая учитывает, что данные (или их часть) могут быть уже отсортированы. Суть её в том, что нужно образовывать цепочки, и производить их слияние не в заранее определённом и фиксированном порядке, а анализировать имеющиеся в массиве данные.

function NaturalSort(string_array) // string_array - это массив со строками (!), не числами.
{
    var splitters = string_array.map(makeSplitter),
        sorted = splitters.sort(compareSplitters);
    return sorted.map(function (splitter) {
        return splitter.item
    });

    function makeSplitter(item) {
        return new Splitter(item)
    }

    function Splitter(item) {
        var index = 0,
            from = 0,
            parts = [],
            completed = false;
        this.item = item;
        var key = item;
        this.key = key;
        this.count = function () {
            return parts.length;
        };
        this.part = function (i) {
            while (parts.length <= i && !completed) next();
            return i < parts.length ? parts[i] : null;
        };

        function next() {
            if (index < key.length) {
                while (++index) {
                    var currentIsDigit = isDigit(key.charAt(index - 1)),
                        nextChar = key.charAt(index),
                        currentIsLast = index === key.length,
                        isBorder = currentIsLast || xor(currentIsDigit, isDigit(nextChar));
                    if (isBorder) {
                        var partStr = key.slice(from, index);
                        parts.push(new Part(partStr, currentIsDigit));
                        from = index;
                        break;
                    }
                }
            } else completed = true;
        }

        function Part(text, isNumber) {
            this.isNumber = isNumber;
            this.value = isNumber ? Number(text) : text;
        }
    }

    function compareSplitters(sp1, sp2) {
        var i = 0;
        do {
            var first = sp1.part(i),
                second = sp2.part(i);
            if (null !== first && null !== second) {
                if (xor(first.isNumber, second.isNumber)) {
                    return first.isNumber ? -1 : 1;
                } else {
                    var comp = compare(first.value, second.value);
                    if (comp != 0) return comp;
                }
            } else return compare(sp1.count(), sp2.count());
        } while (++i);

        function compare(a, b) {
            return a < b ? -1 : a > b ? 1 : 0;
        }
    }

    function xor(a, b) {
        return a ? !b : b;
    }

    function isDigit(chr) {
        var code = charCode(chr);
        return code >= charCode("0") && code <= charCode("9");

        function charCode(c) {
            return c.charCodeAt(0);
        }
    }
}