Tri du comptage - différences d'implémentation

Question

J'ai entendu parler de Counting Sort et j'ai écrit ma version en fonction de ce que j'ai compris.

public void my_counting_sort(int[] arr) 
    { 
     int range = 100; 
     int[] count = new int[range]; 
     for (int i = 0; i < arr.Length; i++) count[arr[i]]++; 
     int index = 0; 
     for (int i = 0; i < count.Length; i++) 
     { 
      while (count[i] != 0) 
      { 
       arr[index++] = i; 
       count[i]--; 
      } 
     } 
    } 

Le code ci-dessus fonctionne parfaitement.

Cependant, l'algorithme donné dans CLRS est différent. Ci-dessous est ma mise en œuvre

public int[] counting_sort(int[] arr) 
    { 
     int k = 100; 
     int[] count = new int[k + 1]; 
     for (int i = 0; i < arr.Length; i++) 
      count[arr[i]]++; 
     for (int i = 1; i <= k; i++) 
      count[i] = count[i] + count[i - 1]; 
     int[] b = new int[arr.Length]; 
     for (int i = arr.Length - 1; i >= 0; i--) 
     { 
      b[count[arr[i]]] = arr[i]; 
      count[arr[i]]--; 
     } 
     return b; 
    } 

J'ai traduit directement ce pseudocode en C#. Le code ne fonctionne pas et j'obtiens une exception IndexOutOfRange.

Mes questions sont les suivantes:

• Quel est le problème avec le deuxième morceau de code?
• Quelle est la différence d'algorithme entre ma mise en œuvre naïve et celle donnée dans le livre?

Answer 1

Le problème avec votre version est qu'elle ne fonctionnera pas si les éléments ont des données satellites.

La version CLRS fonctionnerait et elle est stable.

EDIT:

est ici une implémentation de la version CLRS en Python, qui trie les paires (clé, valeur) par clé:

def sort(a): 
    B = 101 
    count = [0] * B 
    for (k, v) in a: 
    count[k] += 1 
    for i in range(1, B): 
    count[i] += count[i-1] 
    b = [None] * len(a) 
    for i in range(len(a) - 1, -1, -1): 
    (k, v) = a[i] 
    count[k] -= 1 
    b[count[k]] = a[i] 
    return b  


>>> print sort([(3,'b'),(2,'a'),(3,'l'),(1,'s'),(1,'t'),(3,'e')]) 
[(1, 's'), (1, 't'), (2, 'a'), (3, 'b'), (3, 'l'), (3, 'e')] 

Answer 2

Il devrait être

b[count[arr[i]]-1] = arr[i]; 

Je vais laisser à vous de retrouver pourquoi ;-).

Je ne pense pas qu'ils fonctionnent différemment. La seconde pousse simplement la corrélation des comptes hors de la boucle afin qu'elle soit un peu simplifiée dans la boucle finale. Ce n'est pas nécessaire en ce qui me concerne. Votre chemin est tout aussi simple et probablement plus lisible. En fait (je ne connais pas C# depuis que je suis un mec Java), je m'attendrais à ce que vous puissiez remplacer cette boucle while interne par un remplissage de tableau de bibliothèque; quelque chose comme ceci:

 for (int i = 0; i < count.Length; i++) 
    { 
     arrayFill(arr, index, count[i], i); 
     index += count[i]; 
    } 

En Java, la méthode est java.util.Arrays.fill(...).

Answer 3

Le problème est que vous avez codé en dur la longueur du tableau que vous utilisez à 100. La longueur du tableau doit être m + 1 où m est l'élément maximum sur le tableau d'origine. C'est la première raison que vous pourriez penser en utilisant counting-sort, si vous avez des informations sur les éléments du tableau sont tous mineurs qu'une certaine constante et cela fonctionnerait bien.