기수 정렬을 위한 C 프로그램

정렬 알고리즘 목록의 구성 요소를 특정 순서로 배치하는 알고리즘입니다. 가장 많이 사용되는 순서는 숫자순과 사전순입니다.

기수 sort는 비비교 정렬 알고리즘입니다. 기수 정렬 알고리즘은 정렬되지 않은 목록에서 가장 선호되는 알고리즘입니다.

동일한 자리 값의 개별 자릿수를 초기에 그룹화하여 요소를 정렬합니다. 기수 정렬의 개념은 최하위 자릿수(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 ("\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