Алгоритмы Javascript - Сортировка подсчета

В этом посте мы познакомимся с нашим первым алгоритмом сортировки без сравнения - сортировкой с подсчетом! Будучи алгоритмом без сравнения, подсчетная сортировка на самом деле не заботится о других элементах в списке, когда выясняется отсортированная позиция любого заданного элемента, и вы поймете почему, когда мы погрузимся в теорию, лежащую в основе этого. . Сортировка с подсчетом - это стабильная сортировка, которая выполняется за O (n + k) или линейное время, где n - размер входного списка, а k - значение максимального элемента во входном массиве. Когда k = O (n), то отсчет сортировки выполняется за время O (n). Как правило, алгоритмы сортировки должны работать не быстрее, чем Ω (n log n), но поскольку сортировка с подсчетом не работает в модели сравнения, как это делают другие алгоритмы сортировки, такие как сортировка слиянием или быстрая сортировка, эта граница к нему не относится.

Идея сортировки с подсчетом состоит в том, чтобы начать с инициализации вспомогательного массива длины k, в котором будет храниться счетчик каждого числа. Каждый индекс имеет начальное значение 0. После этого вы просматриваете входной массив и увеличиваете счетчик для каждого значения на 1 каждый раз, когда встречаете это число в массиве. Теперь вспомогательный массив содержит количество раз, когда каждый элемент находится во входном массиве. Последний шаг - перейти от минимального значения к максимальному. В этом цикле вы пройдете по каждому соответствующему значению в массиве count и добавите элементы, число которых больше 0, в массив в последовательном порядке. Вы добавляете каждый элемент, используя вторичную переменную приращения (например, если мы используем i для цикла от минимального до максимального значений, тогда мы будем использовать j для цикла по массиву), затем увеличивая эту вторую переменную приращения. поэтому следующий элемент помещается в следующий наивысший индекс массива, и, наконец, вы уменьшаете значение текущего элемента в массиве count, чтобы не добавлять слишком много элементов с этим значением. Вы можете посмотреть отличную визуализацию этого алгоритма здесь. Эту концепцию понять немного сложнее, но после просмотра кода это может быть проще:

let countingSort = (arr, min, max) => {
    let i = min,
        j = 0,
        len = arr.length,
        count = [];
    for (i; i <= max; i++) {
        count[i] = 0;
    }
    for (i = 0; i < len; i++) {
        count[arr[i]] += 1;
    }
    for (i = min; i <= max; i++) {
        while (count[i] > 0) {
            arr[j] = i;
            j++;
            count[i]--;
        }
    }
    return arr;
};

Мы начинаем с инициализации четырех переменных: «i» (наша первая увеличивающая переменная), «j» (наша вторая увеличивающая переменная), «len» (длина входного массива) и «count» (наш пустой массив, который мы будем используйте для хранения количества появлений каждого элемента во входном массиве). В первом цикле for мы переходим от «i» (или минимума) к максимальному значению, устанавливая счетчик каждого элемента равным 0. В следующем цикле for мы перебираем входной массив и увеличиваем значения каждого элемента в счетный массив. Итак, если наш массив равен [14, 28, 12, 14], на первом проходе мы увеличиваем count [14] до 1, затем count [28] до 1, затем count [12] до 1, затем count [14 ] на 2, так как это второй раз, когда мы видим 14. После этого шага массив count будет содержать количество раз, когда каждый элемент появляется во входном массиве. В последнем цикле for мы переходим от минимального значения к максимальному. Внутри этого цикла мы используем цикл while для проверки значения текущего элемента в массиве count, добавляем его в j-ю позицию во входном массиве, если count больше нуля, увеличиваем j на 1, чтобы следующий элемент был добавлен до позиции j-й + 1, затем уменьшите счетчик текущего элемента. Переменная j будет просто проходить по длине массива и добавлять элементы массива count, значение которых больше 0. Наконец, мы возвращаем отсортированный массив.

Вы можете увидеть последний цикл for с вложенным циклом while и сказать «Эй! Разве это не должно быть O (n²)? » Обратите внимание на то, что повторяются циклы. Внешний цикл (цикл for) выполняется для каждого уникального числа в массиве. Внутренний цикл (цикл while) запускается каждый раз, когда встречается это число. На каждой итерации наших циклов мы добавляем только 1 элемент в отсортированный массив.

Вот и все, что нужно для отсчета сортировки! Спасибо за прочтение!