C-Programm zur Basissortierung

Sortieralgorithmus ist ein Algorithmus, der die Komponenten einer Liste in einer bestimmten Reihenfolge anordnet. Die am häufigsten verwendeten Reihenfolgen sind die numerische Reihenfolge und die Wörterbuchreihenfolge.

Cardinal sort ist ein nicht vergleichender Sortieralgorithmus. Der Radix-Sortieralgorithmus ist der bevorzugte Algorithmus für unsortierte Listen.

Es sortiert Elemente, indem zunächst einzelne Zahlen mit demselben Stellenwert gruppiert werden. Die Idee der Basissortierung besteht darin, Stück für Stück von der niedrigstwertigen Ziffer (LSD) zur höchstwertigen Ziffer (MSD) in aufsteigender/absteigender Reihenfolge zu sortieren. Die Radix-Sortierung ist eine kleine Methode, die häufig zum alphabetischen Sortieren sehr großer Namenslisten verwendet wird. Konkret wurde die Namensliste zunächst nach dem Anfangsbuchstaben jedes Namens sortiert, d. h. die Namen wurden in 26 Kategorien eingeteilt.

Sehen wir uns die Abbildung unten an, um ein klares Verständnis dafür zu bekommen, wie der Radix-Sortieralgorithmus funktioniert. Offensichtlich hängt die Anzahl der Durchgänge/Iterationen von der Größe der höchsten Einzelzahl ab.

Im obigen Beispiel ist die Eingabe die Hauptspalte. Die restlichen Spalten werden angezeigt Eine sequentiell sortierte Liste numerischer Positionen mit zunehmender Bedeutung.

Komplexitätsanalyse der Basissortierung O(m.n).

Wenn wir uns jedoch diese beiden Werte ansehen, ist die Größe der Schlüssel im Vergleich zur Anzahl der Schlüssel relativ klein. Wenn wir beispielsweise einen sechsstelligen Schlüssel hätten, könnten wir 1.000.000 völlig unterschiedliche Datensätze haben.

Hier sehen wir tendenziell, dass die Größe des Schlüssels keine Rolle spielt und der Algorithmus eine lineare Masse O(n) ist.

Live-Demonstration

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

Ausgabe

#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;
}

Das obige ist der detaillierte Inhalt vonC-Programm zur Basissortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!