Устойчивость подсчета сортировки

Question

Я реализовал алгоритм сортировки в python. Я вижу, что учетная сортировка является стабильной, поскольку она сохраняет порядок элемента в исходном массиве. Считаете ли вы, что приведенная ниже реализация является стабильной?

def countingsort(A,n): 
     C = [0]*n 
     B = [0]*n 
     # the value of A[i] becomes the index for counting 
     # C now stores the no. of occurences of element A[i] in A 
     for i in A: 
      C[i] = C[i] + 1 
     print i,C 
     # prepare the indexes for reinsertion 
     # Each position in C now holds the range of array position where a value will be placed 
     i = 0 
     while i < n: 
      #print i 
      C[i] = C[i] + C[i-1] 
      i += 1 
     print "Array position for each element",C 
. 
# the stability part of sort ??? 
     for j in xrange(n-1,0,-1): 
      print "j",j,"A[j]:",A[j] 
      B[C[A[j]]-1] = A[j] 
      print B 
      C[A[j]] = C[A[j]] - 1 
      print C 
     print B 
     return B 


    if __name__ == '__main__': 
     A =[0,2,0,1,3,4,6,1,3,2] 
     countingsort(A,len(A)) 

Что такое использование сортировки в реальном мире?

Answer 1

Каковы реальные возможности подсчета сортировки в реальном мире?

C++ пример сортировки подсчета/радикса для 32-битных целых без знака. Он делает один проход по массиву, создавая 4 набора гистограмм в матрице mIndex [] [] на основе байтов каждого целого числа в массиве. Затем он преобразует гистограммы в индексы. Затем он выполняет 4 байтовых сортировки, младший байт и старший байт. В моей системе Intel 2600K 3.4ghz, сортируя 16 миллионов 32-разрядных целых чисел без знака, занимает около 1,5 секунд с сортировкой слияния снизу вверх и около 0,5 секунды, используя этот пример.

// a is input array, b is working array 
uint32_t * RadixSort(uint32_t * a, uint32_t *b, size_t count) 
{ 
size_t mIndex[4][256] = {0};   // count/index matrix 
size_t i,j,m,n; 
uint32_t u; 
    for(i = 0; i < count; i++){   // generate histograms 
     u = a[i]; 
     for(j = 0; j < 4; j++){ 
      mIndex[j][(size_t)(u & 0xff)]++; 
      u >>= 8; 
     }  
    } 
    for(j = 0; j < 4; j++){    // convert to indices 
     m = 0; 
     for(i = 0; i < 256; i++){ 
      n = mIndex[j][i]; 
      mIndex[j][i] = m; 
      m += n; 
     }  
    } 
    for(j = 0; j < 4; j++){    // radix sort 
     for(i = 0; i < count; i++){  // sort by current lsb 
      u = a[i]; 
      m = (size_t)(u>>(j<<3))&0xff; 
      b[mIndex[j][m]++] = u; 
     } 
     std::swap(a, b);    // swap ptrs 
    } 
    return(a); 
}