Ordinamento in ora lineare e sul posto

Question

Supponiamo che n record abbiano chiavi nell'intervallo da 1 a k.

• Scrivere un algoritmo per ordinare i record in atto nel tempo O (n + k).
• È possibile utilizzare la memoria O (k) all'esterno dell'array di input.
• Il tuo algoritmo è stabile?

se usiamo il conteggio sort per poterlo fare in tempo O (n + k) ed è stabile ma non al suo posto.
se k = 2 può essere eseguito sul posto ma non è stabile (utilizzando due variabili per mantenere gli indici nell'array per k = 0 e k = 1)
ma per k> 2 non potrei pensare ad alcun buon algo

Answer 1

per prima cosa, come rimaneggiamento counting sort funziona:

• Conte quanto spesso esiste ogni chiave nella matrice da ordinare. Questi conteggi sono scritti su un array di dimensioni k.
• Calcola le somme parziali dei conteggi delle chiavi. Questo dà la posizione di partenza per ogni cestino di chiavi uguali nell'array ordinato.
• Spostare gli elementi dell'array nella posizione finale incrementando la posizione iniziale del contenitore corrispondente per ogni articolo.

Ora la domanda è come eseguire il passaggio finale sul posto. L'approccio standard per una permutazione sul posto consiste nel selezionare il primo elemento e scambiarlo con l'elemento che assume la sua posizione corretta. Questo passaggio viene ripetuto con l'elemento scambiato fino a quando non si preme un elemento che appartiene alla prima posizione (un ciclo è stato completato). Quindi l'intera procedura viene ripetuta per gli elementi nella seconda, terza, ecc. Posizione fino a quando l'intero array è stato elaborato.

Il problema con il conteggio degli ordinamenti è che le posizioni finali non sono prontamente disponibili, ma sono calcolate incrementando la posizione di partenza di ciascun cestino nel ciclo finale. Per non incrementare mai la posizione di partenza due volte per un elemento, dobbiamo trovare un modo per determinare se un elemento in una determinata posizione è già stato spostato lì. Questo può essere fatto tenendo traccia della posizione iniziale originale per ogni cestino. Se un elemento si trova tra la posizione iniziale originale e la posizione per l'elemento successivo di un raccoglitore, è già stato toccato.

Ecco un'implementazione in C99 che viene eseguita in O(n+k) e richiede solo due array di dimensioni k come spazio di archiviazione aggiuntivo. Il passaggio di permutazione finale non è stabile.

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

Edit: Ecco un'altra versione utilizzando solo un singolo array di dimensione k basata su un approccio di Mohit Bhura.

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

Answer 2

Ecco il mio codice che viene eseguito in O (n + k) tempo e utilizza solo 1 campo extra di dimensione k (a parte la matrice principale di dimensione 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; 
} 

Anche questo algo non è stabile Tutti gli elementi sono nel loro ordine inverso.

P.S: chiavi sono nella gamma da 0 a (k-1)

Answer 3

Un esempio per le sequenze di valori interi. L'ordinamento è instabile. Anche se non è così conciso come la risposta fornita da Mohit, è leggermente più veloce (per il caso comune in cui k < < n) saltando gli elementi già nei loro bin corretti (il tempo è asintoticamente lo stesso). In pratica, preferisco il tipo di Mohit per il suo ciclo più stretto e semplice.

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 

Con un ciclo stretto, ma ancora saltare elementi già trasferito:

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 

Edit: l'approccio di Mohit in Python con bit extra per verificare l'effetto sulla stabilità del genere.

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)