Sortowanie w czasie liniowym i na miejscu

Question

Załóżmy, że n rekordów ma klucze w zakresie od 1 do k.

• Napisz algorytm, aby posortować rekordy w miejscu w czasie O (n + k).
• Możesz użyć pamięci O (k) poza tablicą wejściową.
• Czy Twój algorytm jest stabilny?

jeśli używamy sortowania zliczającego, możemy to zrobić w czasie O (n + k) i jest stabilny, ale nie jest na miejscu.
jeśli k = 2 można to zrobić w miejscu, ale nie jest stabilny (przy użyciu dwóch zmiennych do utrzymania indeksów w tablicy dla k = 0 i k = 1)
, ale dla k> 2 nie mogłem wymyślić żadnego dobrego algo

Answer 1

Najpierw powtarzać jak sortowanie przez zliczanie działa:

• hrabia jak często istnieje każdy klucz w tablicy mają być sortowane. Liczby te są zapisywane w tablicy o rozmiarze k.
• Obliczyć sumy częściowe zliczeń kluczy. Daje to pozycję początkową dla każdego bin równego klucza w posortowanej tablicy.
• Przenieś elementy w tablicy do ich ostatecznego położenia, zwiększając pozycję początkową odpowiedniego pojemnika dla każdej pozycji.

Teraz pytanie brzmi, jak wykonać ostatni krok w miejscu. Standardowe podejście do permutacji lokalnej polega na wybraniu pierwszego elementu i zamianie go na element, który zajmuje właściwą pozycję. Ten krok powtarza się z zamienionym elementem, dopóki nie trafimy na element należący do pierwszej pozycji (cykl został zakończony). Następnie cała procedura jest powtarzana dla elementów na pozycji drugiej, trzeciej itd., Dopóki cała macierz nie zostanie przetworzona.

Problem z sortowaniem zliczającym polega na tym, że końcowe pozycje nie są łatwo dostępne, ale są obliczane poprzez zwiększenie pozycji wyjściowej każdego pojemnika w końcowej pętli. Aby nigdy nie zwiększać dwukrotnie pozycji wyjściowej dla elementu, musimy znaleźć sposób na ustalenie, czy element w danej pozycji został już tam przeniesiony. Można to zrobić, śledząc oryginalną pozycję początkową dla każdego pojemnika. Jeśli element znajduje się pomiędzy początkową pozycją początkową a pozycją następnego elementu pojemnika, został już dotknięty.

Oto implementacja w C99, która działa w O(n+k) i wymaga tylko dwóch tablic o rozmiarze k jako dodatkowej pamięci. Ostateczny etap permutacji nie jest stabilny.

#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: Oto kolejna wersja używając tylko jednego wachlarz rozmiarów k opartej na podejściu mohit Bhura użytkownika.

#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

Oto mój kod, który działa w czasie O (n + k) czasu i wykorzystuje tylko 1 dodatkową tablicę o rozmiarze K (oprócz głównej tablicy o rozmiarze 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; 
} 

Nawet to algo nie jest stabilny. Wszystkie elementy są w odwrotnej kolejności.

P.s: klucze są w zakresie od 0 do (K-1)

Answer 3

przykład dla liczb całkowitych o wartości sekwencji. Sortowanie jest niestabilne. Chociaż nie jest tak zwięzła, jak odpowiedź udzielona przez Mohita, jest nieznacznie szybsza (dla wspólnego przypadku, gdzie k < < n) poprzez pomijanie elementów już w ich właściwych pojemnikach (czas jest asymptotycznie taki sam). W praktyce wolę rodzaj Mohita za jego mocniejszą, prostszą pętlę.

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 

Z mocniej pętlę ale pomijam już przemieszczane elementy:

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: podejście mohit w Pythonie z dodatkowych bitów do zweryfikowania wpływ na stabilność rodzaju.

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)