Что это за алгоритм O (N * k)?

Question

Работая над « Самая быстрая сортировка для BrainF ***» , я обнаружил этот алгоритм, который представляет собой O (N * k), где k - максимальное значение на входе.Требуется O (N) дополнительного хранилища.

Физическая аналогия состоит в том, что у вас есть N стеков токенов.Высота стека представляет значение для сортировки.(Каждый токен представляет немного).Выделите место для еще N стеков.Вы берете один жетон с вершины каждого стека, в котором есть токены, и затем добавляете один жетон в каждый стек нового набора справа налево, пока ваша рука не опустеет.Повторяйте, пока все оригинальные стеки не опустеют.Теперь новый набор отсортирован по возрастанию слева направо

В C:

 void sort(int A[], int N)
 {
    int *R = calloc(N,sizeof(int));
    do {
      int i,count=0; 
      for (i=0;i<N;i++) if A[i] { count++; A[i]--;}
      for (i=0;i<count;i++) R[i]++;
    } while (count);
    memcpy(A,R,N);  //A is now sorted descending.
    free(R);
 }

У этого алгоритма есть имя?Это похоже на сортировку бисером , но я не думаю, что это совсем то же самое.

Answer 1

Оказывается, я все-таки не поленился.Это бисерная сортировка.Вот определение из оригинальной статьи (ссылка в формате PDF):

Рассмотрим набор A из n натуральных чисел.,,Для всех a в A капля a бусины (по одной бусе на стержень) вдоль стержней, начиная с 1-го стержня до a й род.Наконец, бусины, видимые уровень за уровнем от n -го уровня до первого уровня, представляют A в порядке возрастания.

Эта реализация преобразовываетэтот алгоритм двумя способами:

1. Отразите «кадр», в котором он работает, через линию y=x.Это изменяет результат так, что число «шариков» в каждом столбце представляет результат, отсортированный в порядке убывания.В исходном алгоритме число «шариков» в каждой строке представляет выходные данные, отсортированные в порядке возрастания.
2. Вместо того, чтобы представлять «рамку» в виде двумерного массива логических значений, представьте его как 1массив целых чисел.Каждый слот в массиве соответствует «стержню», а его значение представляет количество шариков на этом стержне.Этот второй бит является естественным преобразованием - он просто признает, что, поскольку «шарик» не может плавать в воздухе, запись только количества шариков на стержне говорит нам все, что нужно знать о том, как они расположены на нем.Вы помещаете шарик на стержень, увеличивая соответствующее число.

Вот некоторые пояснения по этому первому пункту, взятые прямо из диаграммы на второй странице статьи: Поскольку алгоритм изначально реализован, массив[3, 2, 4, 2] будет представлена ​​сеткой, которая выглядит следующим образом:

* * *
* *
* * * *
* *

И если шарики упадут, то получится:

* *
* *
* * *
* * * *

Затем вам нужно прочитатьстроки сверху вниз, чтобы получить вывод: [2, 2, 3, 4].В то время как в версии, которая дает результаты в порядке убывания, вы фактически делаете это вместо этого:

  *          *
  *   *      * *
* * * *  ->  * * * *
* * * *      * * * *

Answer 2

Я знаю Radix Sort как одного из представителей сложности O (n * K).

http://en.wikipedia.org/wiki/Radix_sort