Сортировка по линейному времени и по месту

Ответ 1

Во-первых, позвольте перефразировать, как работает сортировка подсчета:

• Укажите, как часто каждый ключ существует в отсортированном массиве. Эти числа записываются в массив размером k.
• Вычислить частичные суммы ключей. Это дает начальную позицию для каждого бина равных ключей в отсортированном массиве.
• Переместите элементы в массиве в их конечную позицию, увеличивая начальную позицию соответствующего бункера для каждого элемента.

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

Проблема с сортировкой сортировки заключается в том, что конечные позиции недоступны, но вычисляются путем увеличения каждой начальной позиции бина в конечном цикле. Чтобы никогда не увеличивать начальную позицию дважды для элемента, мы должны найти способ определить, был ли уже перемещен элемент в определенной позиции. Это можно сделать, отслеживая исходную начальную позицию для каждого бункера. Если элемент находится между исходным исходным положением и положением для следующего элемента бункера, он уже коснулся.

Здесь реализация на C99, которая работает в O(n+k), и требует только два массива размера k в качестве дополнительного хранилища. Конечный шаг перестановки нестабилен.

#include <stdlib.h>

void in_place_counting_sort(int *a, int n, int k)
{
    int *start = (int *)calloc(k + 1, sizeof(int));
    int *end   = (int *)malloc(k * sizeof(int));

    // Count.
    for (int i = 0; i < n; ++i) {
        ++start[a[i]];
    }

    // Compute partial sums.
    for (int bin = 0, sum = 0; bin < k; ++bin) {
        int tmp = start[bin];
        start[bin] = sum;
        end[bin]   = sum;
        sum += tmp;
    }
    start[k] = n;

    // Move elements.
    for (int i = 0, cur_bin = 0; i < n; ++i) {
        while (i >= start[cur_bin+1]) { ++cur_bin; }
        if (i < end[cur_bin]) {
            // Element has already been processed.
            continue;
        }

        int bin = a[i];
        while (bin != cur_bin) {
            int j = end[bin]++;
            // Swap bin and a[j]
            int tmp = a[j];
            a[j] = bin;
            bin = tmp;
        }
        a[i] = bin;
        ++end[cur_bin];
    }

    free(start);
    free(end);
}

Изменить: Здесь другая версия, использующая только один массив размера k на основе подхода Мохита Бхуры.

#include <stdlib.h>

void in_place_counting_sort(int *a, int n, int k)
{
    int *counts = (int *)calloc(k, sizeof(int));

    // Count.
    for (int i = 0; i < n; ++i) {
        ++counts[a[i]];
    }

    // Compute partial sums.
    for (int val = 0, sum = 0; val < k; ++val) {
        int tmp = counts[val];
        counts[val] = sum;
        sum += tmp;
    }

    // Move elements.
    for (int i = n - 1; i >= 0; --i) {
        int val = a[i];
        int j   = counts[val];

        if (j < i) {
            // Process a fresh cycle. Since the index 'i' moves
            // downward and the counts move upward, it is
            // guaranteed that a value is never moved twice.

            do {
                ++counts[val];

                // Swap val and a[j].
                int tmp = val;
                val  = a[j];
                a[j] = tmp;

                j = counts[val];
            } while (j < i);

            // Move final value into place.
            a[i] = val;
        }
    }

    free(counts);
}

Ответ 2

Вот мой код, который работает в O (n + k) времени и использует только 1 дополнительный массив размера k (кроме основного массива размера n)

#include <stdio.h>
#include <string.h>

#include <stdlib.h>


int main(int argc, char const *argv[])
{
int n = atoi(argv[1]);
int k = atoi(argv[2]);

printf("%d\t%d",n,k);

int *a,*c;
int num,index,tmp,i;
a = (int*)malloc(n*sizeof(int));
c = (int*)calloc(k,sizeof(int));

srand(time(NULL));

for(i=0;i<n;i++)
{
    num =  (rand() % (k));
    a[i] = num;
    c[num]++;
}

printf("\n\nArray is : \n");
for(i=0;i<n;i++)
{
    printf("\t%d",a[i]);
    if(i%8==7)
        printf("\n");
}

printf("\n\nCount Array is : \n");
for(i=0;i<k;i++)
{
    printf("\t%d(%d)",c[i],i);
    if(i%8==7)
        printf("\n");
}

//Indexing count Array
c[0]--;
for(i=1;i<k;i++)
{
    c[i] = c[i-1] + c[i];       
}

printf("\n\nCount Array After Indexing is : \n");
for(i=0;i<k;i++)
{
    printf("\t%d(%d)",c[i],i);
    if(i%8==7)
        printf("\n");
} 

// Swapping Elements in Array
for(i=0;i<n;i++)
{
    index = c[a[i]];
    //printf("\na[%d] = %d, going to position %d",i,a[i],index);
    c[a[i]]--;
    if(index > i)
    {
        tmp = a[i];
        a[i] = a[index];
        a[index] = tmp;
        i--;
    }
}

printf("\n\n\tFinal Sorted Array is : \n\n");
for(i=0;i<n;i++)
{
    printf("\t%d",a[i]);
    if(i%8==7)
        printf("\n");
}

printf("\n\n");

return 0;
}

Даже этот алгоритм нестабилен. Все элементы находятся в обратном порядке.

P.s: ключи находятся в диапазоне от 0 до (k-1)

Ответ 3

Пример для целых значений. Сорт нестабилен. Хотя это не так лаконично, как ответ, предложенный Мохитом, он немного быстрее (для обычного случая, когда k < n), пропуская элементы уже в их правильных бункерах (время асимптотически одинаково). На практике я предпочитаю сортировку Mohit для ее более прочной и простой петли.

def sort_inplace(seq):
    min_ = min(seq)
    max_ = max(seq)
    k = max_ - min_ + 1
    stop = [0] * k
    for i in seq:
        stop[i - min_] += 1
    for j in range(1, k):
        stop[j] += stop[j - 1]
    insert = [0] + stop[:k - 1]
    for j in range(k):
        while insert[j] < stop[j] and seq[insert[j]] == j + min_:
            insert[j] += 1
    tmp = None
    for j in range(k):
        while insert[j] < stop[j]:
            tmp, seq[insert[j]] = seq[insert[j]], tmp
            while tmp is not None:
                bin_ = tmp - min_
                tmp, seq[insert[bin_]] = seq[insert[bin_]], tmp
                while insert[bin_] < stop[bin_] and seq[insert[bin_]] == bin_ + min_:
                    insert[bin_] += 1

С более жестким циклом, но все же пропускающий уже перемещенные элементы:

def dave_sort(seq):
    min_ = min(seq)
    max_ = max(seq)
    k = max_ - min_ + 1
    stop = [0] * k

    for i in seq:
        stop[i - min_] += 1

    for i in range(1, k):
        stop[i] += stop[i-1]
    insert = [0] + stop[:k - 1]

    for meh in range(0, k - 1):
        i = insert[meh]
        while i < stop[meh]:
            bin_ = seq[i] - min_
            if insert[bin_] > i:
                tmp = seq[insert[bin_]]
                seq[insert[bin_]] = seq[i]
                seq[i] = tmp
                insert[bin_] += 1
            else:
                i += 1

Изменить: метод Mohit в Python с дополнительными битами, чтобы проверить влияние на стабильность сортировки.

from collections import namedtuple
from random import randrange

KV = namedtuple("KV", "k v")

def mohit_sort(seq, key):
    f = lambda v: getattr(v, key)
    keys = map(f, seq)
    min_ = min(keys)
    max_ = max(keys)
    k = max_ - min_ + 1
    insert = [0] * k

    for i in keys:
        insert[i - min_] += 1

    insert[0] -= 1
    for i in range(1, k):
        insert[i] += insert[i-1]

    i = 0
    n = len(seq)
    while i < n:
        bin_ = f(seq[i])
        if insert[bin_] > i:
            seq[i], seq[insert[bin_]] = seq[insert[bin_]], seq[i]
            i -= 1
        insert[bin_] -= 1
        i += 1


def test(n, k):
    seq = []
    vals = [0] * k
    for _ in range(n):
        key = randrange(k)
        seq.append(KV(key, vals[key]))
        vals[key] += 1
    print(seq)
    mohit_sort(seq, "k")
    print(seq)


if __name__ == "__main__":
    test(20, 3)