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

정렬 알고리즘은 목록의 구성 요소를 특정 순서로 정렬하는 알고리즘입니다. 가장 일반적으로 사용되는 순서는 숫자 순서와 사전 순서입니다.

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

처음에 동일한 자리값의 개별 숫자를 그룹화하여 요소를 정렬합니다. 기수 정렬의 개념은 최하위 숫자(LSD)에서 최상위 숫자(MSD)까지 비트 단위로 증가/감소 순서로 정렬하는 것입니다. 기수 정렬은 매우 큰 이름 목록을 알파벳순으로 정렬할 때 여러 번 사용되는 작은 방법입니다. 구체적으로, 이름 목록은 초기에 각 이름의 첫 글자에 따라 정렬되었습니다. 즉, 이름은 26개 범주로 구성되었습니다.

기수 정렬 알고리즘이 어떻게 작동하는지 명확하게 이해하기 위해 아래 그림을 검토해 보겠습니다. 분명히 패스/반복 횟수는 가장 높은 개별 숫자의 크기에 따라 달라집니다.

위 예에서는 입력이 기본 열입니다. 나머지 열은 다음과 같습니다. 중요성이 높아지는 숫자 위치를 순차적으로 정렬한 목록입니다.

기수 정렬 O(m.n)의 복잡성 분석.

그러나 이 두 값을 보면 키 개수에 비해 키의 크기가 상대적으로 작습니다. 예를 들어, 6자리 키가 있다면 완전히 다른 레코드가 1,000,000개 있을 수 있습니다.

여기서 키의 크기는 중요하지 않으며 알고리즘은 선형 질량 O(n)

algorithm

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

Example

이것은 기수 정렬을 구현하는 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;
}

Output

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!