Tri Radix vs tri Comptage vs tri Bucket. Quelle est la différence?

Question

Je lis les définitions de radix, de comptage et de types de seaux et il semble que tous ne soient que le code ci-dessous:

 public static void sort(int[] a, int maxVal){
    int [] bucket=new int[maxVal+1];

    for (int i=0; i<bucket.length; i++){
        bucket[i]=0;
    }

    for (int i=0; i<a.length; i++){
        bucket[a[i]]++;
    }

    int outPos=0;
    for (int i=0; i<bucket.length; i++){
        for (int j=0; j<bucket[i]; j++){
            a[outPos++]=i;
        }
    }
}
 

Je sais que je ne peux pas avoir raison, alors qu'est-ce qui me manque? Montrez le code si vous pensez que cela peut aider à expliquer en Java ou C. Merci.

Answer 1

Nous allons commencer avec quelques réécriture de votre code en C, car C plus familier pour moi de l'expliquer. Donc, permet de rappeler votre code avec quelques commentaires:

int
counting_sort(int a[], int a_len, int maxVal)
{
  int i, j, outPos = 0;
  int bucket_len = maxVal+1;
  int bucket[bucket_len]; /* simple bucket structure */

  memset(bucket, 0, sizeof(int) * bucket_len);

  /* one loop bucket processing */
  for (i = 0; i < a_len; i++)
    {
      bucket[a[i]]++; /* simple work with buckets */
    }

  for (i=0; i < bucket_len; i++)
    {
      for (j = 0; j < bucket[i]; j++)
        {
          a[outPos++] = i;
        }
    }

  return 0;
}

Maintenant permet d'offrir à ce mec un peu réaliste de données:

[126, 348, 343, 432, 316, 171, 556, 223, 670, 201]

Sur la sortie, nous avons

[126, 171, 201, 223, 316, 343, 348, 432, 556, 670]

Il semble que tout est ok? Pas encore de. Permet de regarder maxVal. Il est de 670 (!) Pour le tri de tableau de 10 éléments, ici, nous avons utilisé la matrice de 670 éléments, principalement des zéros. Terriblement. Pour gérer ce problème de comptage, de tri, nous avons deux façons possibles de généralisation:

1) tout d'Abord, comme pour se faire de tri chiffres-sage. Ceci est appelé radix-tri. Permet de montrer un peu de code, et essayer d'en faire à proximité de comptage, de tri code que possible. Regardez à nouveau les commentaires:

int
radix_sort(int a[], int a_len, int ndigits)
{
  int i;
  int b[a_len];
  int expn = 1;

  /* additional loop for digits */
  for (i = 0; i != ndigits; ++i)
    {
      int j;
      int bucket[10] = {0}; /* still simple buckets */

      /* bucket processing becomes tricky */
      for (j = 0; j != a_len; ++j)
        bucket[ a[j] / expn % 10 ]++;

      for (j = 1; j != 10; ++j)
        bucket[j] += bucket[j - 1];

      for (j = a_len - 1; j >= 0; --j)
        b[--bucket[a[j] / expn % 10]] = a[j];

      for (j = 0; j != a_len; ++j)
        a[j] = b[j];

      expn *= 10;
    }
}

Nous sommes en négociation multiplicateur près de N pour la mémoire. Le Profit? Peut-être. Mais dans certains cas, le multiplicateur près de N est très important. Programme de travail d'une journée et de travail d'une semaine sont très différentes de vue des utilisateurs, même si les deux œuvres 1*O(N) et 7*O(N) respectivement. Nous sommes donc en venir à une seconde généralisation:

2) Deuxièmement, comme pour se faire des seaux de plus en plus sophistiqués. Ceci est appelé le seau de tri.

Permet une fois de plus, avec un peu de code. Je préfère plus de code avant arguments philosophiques. Toujours regarder les commentaires, ils sont essentiels.

int
bucket_sort(int a[], int a_len, int maxVal)
{
  int i, aidx;

  typedef struct tag_list {
    int elem;
    struct tag_list *next;
  } list_t, *list_p;

  list_p bucket[10] = {0}; /* sophisticated buckets */

  /* one loop simple processing with one more inner loop 
    to get sorted buckets (insert-sort on lists, Cormen-style) */
  for (i = 0; i != a_len; ++i)
    {
      int bnum = (10 * a[i]) / maxVal;
      list_p bptr = bucket[bnum];
      list_p belem = malloc(sizeof(list_t));
      belem->elem = a[i];
      if (bptr == 0)
        {
          bucket[bnum] = belem;
          belem->next = 0;
          continue;
        }
      else if (a[i] <= bptr->elem)
        {
          belem->next = bptr;
          bucket[bnum] = belem;
          continue;
        }
      else
        {
          while (bptr != 0)
            {
              if ((bptr->elem <= a[i]) && ((bptr->next == 0) || (bptr->next->elem > a[i])))
                {
                  belem->next = bptr->next;
                  bptr->next = belem;
                  break;
                }
            }
         }
    }

  /* one loop (looks as two) to get all back */
  aidx = 0;

  for (i = 0; i != 10; ++i)
    {
      list_p bptr = bucket[i];
      while (bptr)
        {
          list_p optr = bptr;
          a[aidx] = bptr->elem;
          aidx += 1;
          bptr = bptr->next;
          free(optr);
        }
    }

  return 0;
}

Alors, que faisons-nous ici? Nous sommes en négociation sophistiqués seau de la structure et de l'exigence de la mémoire allouée dynamiquement, mais la victoire de mémoire statique, et le multiplicateur près de N dans la moyenne.

Maintenant, permet de rappeler ce que nous avons vu dans le code:

1. Comptage tri -- simples seaux, un traitement simple, surcharge de la mémoire
2. Radix genre -- de simples seaux, de traitement sophistiqués, la vitesse, les frais généraux (et encore besoin de plus de mémoire statique)
3. Seau tri -- sophistiqué seaux, un traitement simple, nécessite de la mémoire dynamique, bonne moyenne

Radix et un seau sortes sont donc de deux généralisations de comptage, de tri. Ils ont beaucoup en commun avec le comptage de tri et les uns avec les autres, mais dans tous les cas nous sont en train de perdre quelque chose et de gagner quelque chose. Génie logiciel est un équilibre entre ces possibilités.

Answer 2

Radix tri vs Comptage tri vs Seau de tri. Quelle est la différence?

Seau de tri des endroits clés ou des éléments triés dans des seaux. Comment ils sont places dans des seaux est arbitraire et peut être des parties d'une clé composite et toute distribution vous le souhaitez. L'individu seaux peuvent avoir besoin de trier davantage.

Le tri de la mémoire est plus rapide que le tri sur le disque. Toutefois, si vous avez plus de données que ne le fit dans la mémoire, vous avez besoin d'une autre option. Ce que vous pouvez faire est un seau de tri, où les seaux sont assez grand pour tenir en mémoire. c'est à dire il y a un grand nombre d'entrées dans chaque seau. Vous pouvez trier rapide individuellement.

Radix sort est un type spécifique de seau de tri. Il commence avec les n premiers bits ou n-chiffres et peut trier les seaux à l'aide d'une base de tri, etc, jusqu'à ce que toutes les entrées sont triées.

Le comptage, le tri est comme l'utilisation de radix sorte, sauf que vous utilisez l'ensemble de la valeur. Au lieu de l'enregistrement de chaque objet, il a un seau, pour chaque objet, et il compte le nombre d'occurrences. Cela fonctionne bien lorsque vous avez un nombre limité de clés possibles et vous avez de nombreux doublons.

Answer 3

Votre code est simple variante de comptage, de tri, sans données, il suffit de clés.

Radix de tri de tri basé sur cette méthode. Le problème avec le comptage, le tri est exigence de mémoire: int [] bucket=new int[maxVal+1];. Radix de tri permet de résoudre ce problème. L'idée est d'utiliser le comptage de tri à plusieurs reprises, d'abord pour les chiffres inférieurs, puis pour les plus élevés. Par exemple, pour trier les nombres entiers de 32 bits, vous pouvez utiliser:

sort(a, 65535) using lower half as key
sort(a, 65535) using higher half as key

Il fonctionne, parce que le comptage, le tri est stable - il maintient l'ordre des données avec l'égalité des touches. C'est comme le tri dans la feuille de calcul: sort by B; sort by A vous donne les éléments triés par A et par B lorsque égale.

Seau de tri est une généralisation du comptage de tri. Vous pouvez l'utiliser pour trier les nombres réels de certains prévisibles de distribution de probabilité (par exemple. uniforme (0,1)). L'idée est d'utiliser le comptage de tri (à l'aide d' floor(x*N_BUCKETS) clés) et ensuite seulement de trier chaque seau de façon indépendante.

Answer 4

Tout d'abord regardons la différence entre Radix de Tri et d'un Seau de Tri parce que c'est généralement une source de confusion, parce que l'idée semble le même. Ensuite, nous regardons le Comptage de Tri qui est comme une version primaire de ces deux et que des problèmes avec le comptage de tri cause les deux autres à être utilisé

Le passage initial à la fois de Base et d'un Seau de tri sont les mêmes.Les éléments sont placés dans des "Seaux" je.e de 0 à 10, 11 à 20, ...et ainsi de suite, selon le nombre de chiffres dans le plus grand pas, j'.e le radix. Dans le passage suivant, cependant, seau tri des commandes jusqu'ces "seaux" et ajoute-les dans un tableau. Cependant, la méthode de tri radix ajoute les seaux avec d'autres de tri, et de "ré-seaux" il basé sur le deuxième chiffre (des dizaines) de nombres. Par conséquent, Seau tri est plus efficace pour les Denses tableaux, alors que Radix de Tri peut manipuler des matrices creuses bien. Bien penser seau de sorte que ce

Supposons que vous avez une liste de n enregistrements, chacun avec une clé qui est un nombre de 1 à k (on généralise le problème un peu si k n'est pas nécessairement égal à n).

Nous pouvons résoudre ce problème en faisant un tableau de listes chaînées. Nous nous déplaçons chaque enregistrement de l'entrée dans la liste dans la position appropriée du tableau puis concaténer toutes les listes ensemble dans l'ordre.

 bucket sort(L)
    {
    list Y[k+1]
    for (i = 0; i <= k; i++) Y[i] = empty
    while L nonempty
    {
        let X = first record in L
        move X to Y[key(X)]
    }
    for (i = 0; i <= k; i++)
    concatenate Y[i] onto end of L
    }

Que faire lorsque k est grand? Penser la représentation décimale d'un nombre x = a + 10 b + 100 ° c + 1000 de d + ... où a,b,c etc, tout dans la gamme 0..9. Ces chiffres sont facilement assez petit pour ne seau de tri.

   radix sort(L):
    {
    bucket sort by a
    bucket sort by b
    bucket sort by c
    ...
    }

ou, plus simplement,

radix sort(L):
{
while (some key is nonzero)
{
    bucket sort(keys mod 10)
    keys = keys / 10
}
}

Pourquoi faisons-nous de la sorte moins importants chiffres d'abord? D'ailleurs, pourquoi faisons-nous de plus d'un compartiment de tri, depuis le dernier est celui qui met tout en place? Réponse: Si nous essayons d'arranger les choses en main, nous avons tendance à faire quelque chose de différent: faire d'abord un seau de tri, puis, de manière récursive trier les valeurs partageant un même premier chiffre. Cela fonctionne, mais est moins efficace car il divise le problème en plusieurs sous-problèmes. En revanche, tri radix jamais se divise la liste; elle s'applique uniquement seau tri plusieurs fois à la même liste. Dans radix tri, le dernier col de seau de tri est celui qui a le plus d'effet sur l'ensemble de la commande. Si nous voulons qu'il soit le seul à l'aide de la plupart des chiffres significatifs. La précédente seau tri de passe sont utilisés seulement pour prendre soin de l'affaire dans laquelle deux éléments ont la même clé (mod 10) sur la dernière passe.

Maintenant que nous avons que de la route que le Comptage de tri n'est il garde un auxiliaire de la matrice de C à k éléments, tous initialisés à 0.

Nous faisons un passage par le tableau d'entrée A et pour chaque élément i dans Un ce que nous voyons, nous incrément de C[i] par 1. Après nous parcourir le n les éléments de l'Un et de mise à jour de C, la valeur à l'indice j de C correspond à combien de fois j paru dans A. Cette étape prend O(n) le temps à la parcourir par A. une Fois que nous avons C, nous pouvons construire la version triée d'Un par l'itération sur les C et de l'insertion de chaque élément j un total de C[j] fois dans une nouvelle liste (ou lui-même). L'itération sur les C prend O(k) temps.L' résultat de fin est un classement Un et, au total, il a fallu O(n + k) temps de le faire.

La chute de comptage, de tri, c'est qu'il ne peut pas être trop pratique si la gamme des éléments est trop importante. Par exemple, si la plage de n éléments à trier était de 1 à n 3 , alors la simple création d'une auxiliaire de tableau C prendra O(n^3) temps de comptage et de tri doit asymptotiquement faire pire que le tri par insertion. Cela prend également en O(n^3) de l'espace qui est important plus que tout de l'espace utilisé par un autre algorithme de tri que nous avons appris jusqu'à présent. Radix de tri permet de résoudre ce problème par un tri des éléments digit par digit

Remarque: les Sources pour les réponses et pour en savoir plus:

http://htmltolatex.sourceforge.net/samples/sample4.html

La première réponse à: Quelle est la différence entre le seau de tri et tri radix?

Answer 5

Pour trier un tableau à l'aide du tri par nombre:

 #define MAX_INPUT 1000

void sort(int arr[100], int n)
{
    static int hash[MAX_INPUT], i, j;

    memset(hash, 0, sizeof hash);

    for (i = 0; i < n; ++i) ++hash[arr[i]];

    j = 0;
    for (i = 0; i < MAX_INPUT; ++i)
        while (hash[i]--)
           arr[j++] = i;
}
 

Ce n'est que O(MAX_INPUT) , triant ainsi en temps linéaire. Pour le tri par seau, c'est très différent. Voici une implémentation