Programme C pour le tri par base

Sort Algorithm est un algorithme qui organise les composants d'une liste dans un ordre spécifique. Les ordres les plus couramment utilisés sont l’ordre numérique et l’ordre du dictionnaire.

Cardinxsort est un algorithme de tri non comparatif. L'algorithme de tri par base est l'algorithme préféré pour les listes non triées.

Il trie les éléments en regroupant initialement des nombres individuels de même valeur de position. L'idée du tri par base est de trier petit à petit du chiffre le moins significatif (LSD) au chiffre le plus significatif (MSD) par ordre croissant/décroissant. Le tri par base est une petite méthode utilisée plusieurs fois pour trier de très grandes listes de noms par ordre alphabétique. Plus précisément, la liste des noms était initialement triée selon la première lettre de chaque nom, c'est-à-dire que les noms étaient organisés en vingt-six catégories.

Revoyons l'illustration ci-dessous pour bien comprendre le fonctionnement de l'algorithme de tri par base. Évidemment, le nombre de passes/itérations dépend de la taille du nombre individuel le plus élevé.

Dans l'exemple ci-dessus, l'entrée est la colonne principale. Les colonnes restantes montrent Une liste triée séquentiellement de positions numériques d’importance croissante.

Analyse de complexité du tri de base O(m.n).

Cependant, si l'on regarde ces deux valeurs, la taille des touches est relativement petite par rapport au nombre de touches. Par exemple, si nous avions une clé à six chiffres, nous pourrions avoir 1 000 000 d’enregistrements complètement différents.

Ici, nous avons tendance à voir que la taille de la clé n'a pas d'importance et que l'algorithme est une masse linéaire O(n)

algorithme

Radix_sort (list, n)
shift = 1
for loop = 1 to keysize do
   for entry = 1 to n do
   bucketnumber = (list[entry].key / shift) mod 10
   append (bucket[bucketnumber], list[entry])
list = combinebuckets()
shift = shift * 10

Exemple

Il s'agit d'un programme C qui implémente le tri par base.

Démonstration en direct

#include<stdio.h>
int get_max (int a[], int n){
   int max = a[0];
   for (int i = 1; i < n; i++)
      if (a[i] > max)
         max = a[i];
   return max;
}
void radix_sort (int a[], int n){
   int bucket[10][10], bucket_cnt[10];
   int i, j, k, r, NOP = 0, divisor = 1, lar, pass;
   lar = get_max (a, n);
   while (lar > 0){
      NOP++;
      lar /= 10;
   }
   for (pass = 0; pass < NOP; pass++){
      for (i = 0; i < 10; i++){
         bucket_cnt[i] = 0;
      }
      for (i = 0; i < n; i++){
         r = (a[i] / divisor) % 10;
         bucket[r][bucket_cnt[r]] = a[i];
         bucket_cnt[r] += 1;
      }
      i = 0;
      for (k = 0; k < 10; k++){
         for (j = 0; j < bucket_cnt[k]; j++){
            a[i] = bucket[k][j];
            i++;
         }
      }
      divisor *= 10;
      printf ("After pass %d : ", pass + 1);
      for (i = 0; i < n; i++)
         printf ("%d ", a[i]);
      printf ("</p><p>");
   }
}
int main (){
   int i, n, a[10];
   printf ("Enter the number of items to be sorted: ");
   scanf ("%d", &n);
   printf ("Enter items: ");
   for (i = 0; i < n; i++){
      scanf ("%d", &a[i]);
   }
   radix_sort (a, n);
   printf ("Sorted items : ");
   for (i = 0; i < n; i++)
      printf ("%d ", a[i]);
   printf ("</p><p>");
   return 0;
}

Sortie

Enter number of items to be sorted 6
Enter items:567 789 121 212 563 562
After pass 1 : 121 212 562 563 567 789
After pass 2 : 212 121 562 563 567 789
After pass 3 : 121 212 562 563 567 789
Sorted items : 121 212 562 563 567 789

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!