Алгоритм недели: целочисленные алгоритмы линейной сортировки по времени

С другой стороны, есть и алгоритмы сортировки, которые работают лучше. Это семейство алгоритмов целочисленной сортировки. Эти алгоритмы используют целочисленные свойства для их сортировки без сравнения. Их можно использовать только для сортировки целых чисел. Тем не менее, хеш-функция может использоваться для присвоения уникального целого числа любому значению и сортировки любого значения. Все эти алгоритмы используют дополнительное пространство. Существует несколько таких алгоритмов. В этой статье мы увидим три из них, и я представлю реализацию на C ++. В конце статьи я сравню их с std :: sort .

В этой статье я буду использовать n в качестве размера массива для сортировки и m в качестве максимального числа, допустимого в массиве.

Бин Сортировать

Bin Sort или Bucket Sort — это очень простой алгоритм, который разбивает все входные числа на несколько сегментов. Затем все сегменты выводятся в массиве по порядку, что приводит к сортировке массива. Я решил реализовать простейший случай сортировки бинов, где каждое число идет в отдельном сегменте, поэтому существует m блоков.

Реализация довольно проста:

void binsort(std::vector<std::size_t>& A){
    std::vector<std::vector<std::size_t>> B(MAX + 1);

    for(std::size_t i = 0; i < SIZE; ++i){
        B[A[i]].push_back(A[i]);
    }

    std::size_t current = 0;
    for(std::size_t i = 0; i < MAX; ++i){
        for(auto item : B[i]){
            A[current++] = item;
        }
    }
}

B — массив блоков. Каждый сегмент реализован как std :: vector. Алгоритм начинается с заполнения каждого сегмента числами из входного массива. Затем он выводит их по порядку в массиве.

Этот алгоритм работает в  O (n + m)  и требует  O (m)  дополнительной памяти. С этими свойствами он создает очень ограниченный алгоритм, потому что, если вы не знаете максимальное число, и вам нужно использовать максимальное число типа массива, вам придется выделить, например, 2 ^ 32 сегмента. Это не будет возможно.

Сортировка

Интересный факт о бинсорте состоит в том, что каждое ведро содержит только одинаковые числа. Размер ведра будет достаточно. Это именно то, что считает Сортировка. Он подсчитывает количество раз, когда элемент присутствует вместо самих элементов. Я представлю две версии. Первый — это версия, использующая вторичный массив и затем снова копируемая во входной массив, а вторая — сортировка на месте.

void counting_sort(std::vector<std::size_t>& A){
    std::vector<std::size_t> B(SIZE);
    std::vector<std::size_t> C(MAX);
    for (std::size_t i = 0; i < SIZE; ++i){
        ++C[A[i]];
    }
    for (std::size_t i = 1; i <= MAX; ++i){
        C[i] += C[i - 1];
    }
    for (long i = SIZE - 1; i >= 0; --i) {
        B[C[A[i]] - 1] = A[i];
        --C[A[i]];
    }
    for (std::size_t i = 0; i < SIZE; ++i){
        A[i] = B[i];
    }
}

Алгоритм также прост. Он начинается с подсчета количества элементов в каждой корзине. Затем он агрегирует число, суммируя их, чтобы получить позицию элемента в конечном отсортированном массиве. Затем все элементы копируются во временный массив. Наконец, временный массив копируется в окончательный массив. Этот алгоритм работает в O (m + n) и требует O (m + n) . Эта версия представлена ​​только потому, что она присутствует в литературе. Мы можем сделать намного лучше, избегая временного массива и немного оптимизируя его:

void in_place_counting_sort(std::vector<std::size_t>& A){
    std::vector<std::size_t> C(MAX + 1);

    for (std::size_t i = 0; i < SIZE; ++i){
        ++C[A[i]];
    }

    int current = 0;
    for (std::size_t i = 0; i < MAX; ++i){
        for(std::size_t j =0; j < C[i]; ++j){
            A[current++] = i;
        }
    }
}

Временный массив удаляется, а элементы записываются непосредственно в отсортированный массив. Счета не используются непосредственно в качестве позиции, поэтому нет необходимости их суммировать. Эта версия все еще работает в O (m + n), но требует только O (m) дополнительной памяти. Это намного быстрее, чем в предыдущей версии.

Radix Sort

Последняя версия, которую я расскажу здесь, это Radix Sort. Этот алгоритм сортирует цифру цифра за цифрой по определенному основанию. Это форма сортировки ведра, где есть ячейка за цифрой. Как и Counting Sort, нужны только подсчеты. Например, если вы используете основную сортировку в базе 10. Сначала она отсортирует все числа по первой цифре, а затем по второй,…. Он может работать на любой базе, и в этом его сила. С хорошо выбранной базой, это может быть очень мощным. Здесь мы сосредоточимся на основаниях, которые находятся в форме 2 ^ r. У этих основ есть хорошие свойства, мы можем использовать сдвиги и маску для выполнения деления и по модулю, что делает алгоритм намного быстрее.

Реализация немного сложнее, чем другие реализации:

static const std::size_t digits = 2;        //Digits
static const std::size_t r = 16;                 //Bits
static const std::size_t radix = 1 << r;         //Bins
static const std::size_t mask = radix - 1;

void radix_sort(std::vector<std::size_t>& A){
    std::vector<std::size_t> B(SIZE);
    std::vector<std::size_t> cnt(radix);

    for(std::size_t i = 0, shift = 0; i < digits; i++, shift += r){
        for(std::size_t j = 0; j < radix; ++j){
            cnt[j] = 0;
        }

        for(std::size_t j = 0; j < SIZE; ++j){
            ++cnt[(A[j] >> shift) & mask];
        }

        for(std::size_t j = 1; j < radix; ++j){
            cnt[j] += cnt[j - 1];
        }

        for(long j = SIZE - 1; j >= 0; --j){
            B[--cnt[(A[j] >> shift) & mask]] = A[j];
        }

        for(std::size_t j = 0; j < SIZE; ++j){
           A[j] = B[j];
        }
    }
}

r обозначает степень двух, используемую как основание (2 ^ r). Маска используется для вычисления по модулю быстрее. Алгоритм повторяет шаги для каждой цифры. Здесь цифры равны 2. Это означает, что мы поддерживаем 2 ^ 32 значения. 32-битное значение сортируется в два прохода. Шаги очень похожи на подсчет сортировки. Каждое значение цифры подсчитывается, а затем суммы суммируются, чтобы определить положение числа. Наконец, числа упорядочиваются во временном массиве и копируются в A.

Этот алгоритм работает в O (цифры (m + основание)) и требует O (n + основание) дополнительной памяти. Очень хорошо то, что алгоритм не требует пространства на основе максимального значения, только на основе основ.

Полученные результаты

Пришло время сравнить различные реализации с точки зрения времени выполнения. Для каждого размера каждая версия тестируется 25 раз на разных случайных массивах. Массивы одинаковы для каждого алгоритма. Число — это время, необходимое для сортировки 25 массивов. Тест был компилятором с GCC 4.7.

Первый тест проводится с очень небольшим количеством дубликатов (m = 10n).

Нормальный масштаб

Логарифмическая шкала

Radix Sort в этом случае оказывается самым быстрым, вдвое быстрее, чем std :: sort . Сортировка по месту имеет почти такую ​​же производительность, как std :: sort . Другие работают хуже.

Второй тест проводится с несколькими дубликатами (m ~ = n).

Нормальная шкала