Cos'è questo o (n * k) l'algoritmo di ordinamento?

Question

Quando si lavora su " Il tipo più veloce per Brainf ***" , ho scoperto questo algoritmo, che èO (n * k), dove k è il valore massimo nell'input.Richiede o (n) storage extra.

L'analogia fisica è che hai n pile di token.L'altezza dello stack rappresenta il valore da ordinare.(Ogni token rappresenta un po ').Metti da parte spazio per altri n pile.Si prende un token dalla parte superiore di ogni pila che ha token, quindi aggiungi uno a ciascuna pila nel nuovo set da destra a sinistra finché la tua mano è vuota.Ripeti fino a quando tutte le pile originali sono vuote.Ora il nuovo set è ordinato ascendente a sinistra a destra

in 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);
 }

.

Questo algoritmo ha un nome?Sembra simile a un perline ordina , ma non penso che sia uguale. .

Answer 1

Turns out I wasn't too lazy after all. It is Bead Sort. Here's the definition from the original paper (PDF link):

Consider a set A of n positive integers. . . For all a in A drop a beads (one bead per rod) along the rods, starting from the 1st rod to the a'th rod. Finally, the beads, seen level by level, from the nth level to the first level, represent A in ascending order.

This implementation transforms that algorithm in two ways:

1. Reflect the 'frame' in which it's working across the line y=x. This changes the result such that the number of 'beads' in each column represents the output sorted in descending order. In the original algorithm, the number of 'beads' in each row represents the output sorted in ascending order.
2. Rather than representing the 'frame' as an 2-dimensional array of boolean values, represent it as a 1-dimensional array of integers. Each slot in the array corresponds to a 'rod', and its value represents the number of beads on that rod. This second bit is a natural transformation - it simply acknowledges that, since a 'bead' cannot float in mid-air, recording just the number of beads on the rod tells us all there is to know about how they are arranged on it. You place a bead on a rod by incrementing the corresponding number.

Here's some clarification on that first point, taken straight from the diagram on the paper's second page: As the algorithm is originally implemented, the array [3, 2, 4, 2] would be represented by a grid that looks like:

* * *
* *
* * * *
* *

And letting the beads fall produces:

* *
* *
* * *
* * * *

You then have to read the rows, from top to bottom, to get the output: [2, 2, 3, 4]. Whereas in the version that gives results in descending order, you are effectively doing this instead:

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

Answer 2

I know Radix Sort as one representative in the O(n*K) complexity.

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