기수 정렬을 구현하는 C++ 프로그램

기수 정렬은 비비교 정렬 알고리즘입니다. 이 정렬 알고리즘은 동일한 위치와 값을 공유하는 숫자를 그룹화하여 정수 키에서 작동합니다. 기수는 숫자 체계의 기초입니다. 십진법에서 기수 또는 밑이 10이라는 것을 알고 있듯이 일부 십진법을 정렬하려면 숫자를 저장할 10개의 위치 상자가 필요합니다.

기수 정렬 기법의 복잡성

• 시간 복잡도:O(nk)

• 공간 복잡도:O(n+k)

Input − The unsorted list: 802 630 20 745 52 300 612 932 78 187
Output − Data after Sorting: 20 52 78 187 300 612 630 745 802 932

알고리즘

radixSort(배열, 크기, 최대 숫자)

입력 :데이터의 배열, 배열의 총 개수, 최대 개수의 자릿수.

출력 :정렬된 배열입니다.

Begin
   define 10 lists as pocket
   for i := 0 to max -1 do
      m = 10i+1
      p := 10i
      for j := 0 to n-1 do
      temp := array[j] mod m
      index := temp / p
      pocket[index].append(array[j])
   done
   count := 0
   for j := 0 to radix do
      while pocket[j] is not empty
         array[count] := get first node of pocket[j] and delete it
         count := count +1
      done
   done
End

예시 코드

#include<iostream>
#include<list>
#include<cmath>
using namespace std;
void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}
void radixSort(int *arr, int n, int max) {
   int i, j, m, p = 1, index, temp, count = 0;
   list<int> pocket[10];      //radix of decimal number is 10
   for(i = 0; i< max; i++) {
      m = pow(10, i+1);
      p = pow(10, i);
      for(j = 0; j<n; j++) {
         temp = arr[j]%m;
         index = temp/p;      //find index for pocket array
         pocket[index].push_back(arr[j]);
      }
      count = 0;
      for(j = 0; j<10; j++) {
         //delete from linked lists and store to array
         while(!pocket[j].empty()) {
            arr[count] = *(pocket[j].begin());
            pocket[j].erase(pocket[j].begin());
            count++;
         }
      }
   }
}
int main() {
   int n, max;
   cout << "Enter the number of elements: ";
   cin >> n;
   cout << "Enter the maximum digit of elements: ";
   cin >> max;
   int arr[n]; //create an array with given number of elements
   cout << "Enter elements:" << endl;
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "Data before Sorting: ";
   display(arr, n);
   radixSort(arr, n, max);
   cout << "Data after Sorting: ";
   display(arr, n);
}

출력

Enter the number of elements: 10
Enter the maximum digit of elements: 3
Enter elements:
802 630 20 745 52 300 612 932 78 187
Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932