基数ソート用の C プログラム

並べ替えアルゴリズムは、リストのコンポーネントを特定の順序で配置するアルゴリズムです。最も一般的に使用される順序は、数値順と辞書順です。

Cardix 並べ替えは、非比較並べ替えアルゴリズムです。基数ソート アルゴリズムは、ソートされていないリストに推奨されるアルゴリズムです。

最初に同じ位の値の個々の数値をグループ化することによって要素を並べ替えます。基数ソートの考え方は、最下位桁 (LSD) から最上位桁 (MSD) まで昇順/降順でビットごとにソートすることです。基数ソートは、名前の非常に大きなリストをアルファベット順にソートするときに何度も使用される小さな方法です。具体的には、名前リストは最初、各名前の最初の文字に従って並べ替えられました。つまり、名前は 26 のカテゴリに編成されました。

基数ソート アルゴリズムがどのように機能するかを明確に理解するために、下の図を確認してみましょう。明らかに、パス/反復の数は最大の個別の数値のサイズに依存します。

上記の例では、メイン列が入力されています。残りの列には、 重要度が増加する数値位置の順番にソートされたリスト。

基数ソート O(m.n) の複雑さの分析。

ただし、両方の値を見ると、キーのサイズはキーの数に比べて比較的小さいことがわかります。たとえば、6 桁のキーがあれば、まったく異なるレコードが 1,000,000 件存在する可能性があります。

ここでは、キーのサイズは重要ではなく、アルゴリズムは線形品質であることがわかります O(n)

アルゴリズム

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

例

これは基数ソートを実装する C プログラムです。

ライブ デモンストレーション

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

出力

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

以上が基数ソート用の C プログラムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。