Cプログラミング
 Computer >> コンピューター >  >> プログラミング >> Cプログラミング

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

並べ替えアルゴリズム は、リストのコンポーネントを特定の順序で配置するアルゴリズムです。最もよく使用される順序は、番号順と辞書式順序です。

基数 sortは、非比較のソートアルゴリズムです。基数ソートアルゴリズムは、ソートされていないリストに最も適したアルゴリズムです。

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

基数ソートアルゴリズムの動作について明確に理解するために、次の図を確認してみましょう。明らかに、パス/反復の数は、最大の個々の数のサイズに依存します。

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

上記の例では、プライマリ列が入力されています。残りの列は、有効数字の位置が連続してソートされた後のリストを示しています。

基数ソートO（m.n）の複雑さの分析

ただし、これら2つの値を見ると、キーの数に比べてキーのサイズは比較的小さくなっています。たとえば、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 ("\n");
   }
}
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 ("\n");
   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

  1. カクテルソート用のPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します。 問題の説明 −リストが与えられたので、与えられたリストに対してビットニックソートを実行し、リストを表示する必要があります シェーカーソート −ここでは、ソートはバブルソートのように行われ、反復は両方向で行われます。 アルゴリズム まず、配列が左から右にトラバースされます。トラバーサル中に、隣接するアイテムが比較され、条件に基づいて値が交換されます。これにより、最大数はアレイの最後になります。 これで、配列は反対方向にトラバースされ、条件に基づいて要素が交換されます。これにより、最小数が最初になります。 次に、以下

  2. 選択ソート用のPythonプログラム

    この記事では、Python3.xでの選択ソートとその実装について学習します。またはそれ以前。 選択ソート アルゴリズムでは、配列は、ソートされていない部分から最小要素を再帰的に見つけて、それを先頭に挿入することによってソートされます。特定の配列での選択ソートの実行中に、2つのサブ配列が形成されます。 すでにソートされているサブアレイ ソートされていないサブアレイ。 選択ソートを繰り返すたびに、ソートされていないサブアレイの最小要素がポップされ、ソートされたサブアレイに挿入されます。 アルゴリズムの視覚的表現を見てみましょう- それでは、アルゴリズムの実装を見てみましょう- 例