Bucket Trier la mise en œuvre

Question

Je dois mettre en œuvre un seau sorte pour qu'il trie un tableau avec size = 100 avec des nombres générés aléatoirement entre 0 et 100. Mes seaux sont les suivantes:

Bucket0: (0<=x<10) 
Bucket1: (10<=x<20) 
. 
. 
. 
Bucket9: (90<=x<100) 

Maintenant, je comprends la théorie derrière la tri de seau, où j'insère les éléments dans chaque seau individuel, mais ce que je ne comprends pas comment créer réellement les seaux. Est-ce que je crée un tableau disons B avec les pelles étant elles-mêmes des matrices? Ou est-ce une manière plus standard d'implémenter un tri de seau avec des entiers?

J'ai juste besoin d'un coup de pouce dans la bonne direction, merci pour toute aide!

Answer 1

Oui.
Vous devez déclarer un autre tableau (nous pouvons dire b) avec une longueur de 101. La longueur représente et la plage de nos nombres.

Maintenant vous devez sur le premier tableau et pour chaque cellule, et quand vous trouvez tous les nombres k (0 < = k < = 100), vous devez ++ le b [k]. Quelque chose comme: b[a[i]]++;

Maintenant, nous avons le tableau b qui représente combien de fois chaque numéro k est apparu dans le premier tableau. On peut remplacer le premier tableau:

for(int i = 0; i <= RANGE; i++) 
    for(int j = 0; j < b[i]; j++) 
     a[p++] = i; 

Alors que sur votre cas, RANGE est 100.

complexité: O (n)

Notez que nous pouvons mettre en œuvre que d'une variable au lieu d'utiliser un tableau , qui fait la même chose, mais chaque fois pour un nombre différent. Pas économise beaucoup mais économise un peu la complexité de l'espace.