기수 정렬 - DS 튜토리얼

이번 포스팅에서는 Radix 정렬 알고리즘에 대해 알아보겠습니다. 기수 정렬은 정수에 사용되는 선형 정렬 알고리즘입니다. 기수 정렬에서는 최하위 숫자부터 시작하여 최상위 숫자까지 자릿수별 정렬이 수행됩니다.

기수 정렬 프로세스는 알파벳 순서에 따라 학생 이름을 정렬하는 것과 유사하게 작동합니다. 이 경우 영어의 알파벳 26개로 인해 26개의 기수가 형성된다. 첫 번째 패스에서는 학생의 이름이 이름 첫 글자의 오름차순에 따라 그룹화됩니다. 그 후, 두 번째 패스에서는 이름의 두 번째 문자의 오름차순에 따라 이름이 그룹화됩니다. 그리고 정렬된 목록을 찾을 때까지 프로세스가 계속됩니다.

javafx

이제 Radix 정렬 알고리즘을 살펴보겠습니다.

연산

 radixSort(arr) max = largest element in the given array d = number of digits in the largest element (or, max) Now, create d buckets of size 0 - 9 for i -&gt; 0 to d sort the array elements using counting sort (or any stable sort) according to the digits at the ith place

Radix 정렬 알고리즘의 작동

이제 Radix 정렬 알고리즘의 작동을 살펴보겠습니다.

기수 정렬에 사용되는 단계는 다음과 같습니다.

먼저, 가장 큰 요소를 찾아야 합니다(가정 최대 ) 주어진 배열에서. 가정하다 '엑스' 의 자릿수가 되다 최대 . 그만큼 '엑스' 모든 요소의 중요한 위치를 통과해야 하기 때문에 계산됩니다.
그 후, 중요한 장소를 하나씩 살펴보세요. 여기서는 안정적인 정렬 알고리즘을 사용하여 각 중요한 위치의 숫자를 정렬해야 합니다.

이제 예제를 사용하여 기수 정렬의 작동 방식을 자세히 살펴보겠습니다. 더 명확하게 이해하기 위해 정렬되지 않은 배열을 가져와서 기수 정렬을 사용하여 정렬해 보겠습니다. 설명이 더 명확하고 쉬워집니다.

주어진 배열에서 가장 큰 요소는 736 가지고 있는 삼 그 안에 숫자가 있습니다. 따라서 루프는 최대 3번까지 실행됩니다(즉, 수백 곳 ). 즉, 배열을 정렬하려면 세 번의 패스가 필요합니다.

이제 먼저 단위 자리 숫자를 기준으로 요소를 정렬합니다(예: 엑스 = 0 ). 여기서는 counting sort 알고리즘을 사용하여 요소를 정렬합니다.

패스 1:

첫 번째 단계에서는 목록이 0의 자리에 있는 숫자를 기준으로 정렬됩니다.

첫 번째 패스 후 배열 요소는 다음과 같습니다.

패스 2:

이 패스에서 목록은 다음 유효 숫자(예: 10의 숫자)를 기준으로 정렬됩니다.^일장소).

두 번째 패스 후 배열 요소는 -

패스 3:

이 패스에서 목록은 다음 유효 숫자(예: 100의 숫자)를 기준으로 정렬됩니다.^일장소).

세 번째 패스 이후 배열 요소는 다음과 같습니다.

이제 배열이 오름차순으로 정렬되었습니다.

파이썬의 상속 프로그램

기수 정렬 복잡성

이제 최상의 경우, 평균적인 경우, 최악의 경우에 대한 Radix 정렬의 시간 복잡도를 살펴보겠습니다. 기수 정렬의 공간 복잡도도 살펴보겠습니다.

1. 시간 복잡도

사례	시간 복잡도
최선의 경우	Ω(n+k)
평균 사례	θ(nk)
최악의 경우	오(nk)

Ω(n+k)

θ(nk)

오(nk)

기수 정렬은 비교 정렬 알고리즘보다 우수한 비비교 정렬 알고리즘입니다. 이는 복잡도가 O(n logn)인 비교 알고리즘보다 더 나은 선형 시간 복잡도를 갖습니다.

2. 공간 복잡성

공간 복잡도	O(n + k)
안정적인	예

기수 정렬의 공간 복잡도는 O(n + k)입니다.

기수 정렬 구현

이제 다양한 프로그래밍 언어로 작성된 Radix 정렬 프로그램을 살펴보겠습니다.

프로그램: C 언어로 기수 정렬을 구현하는 프로그램을 작성하세요.

 #include int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) { printf('%d ', a[i]); } printf('
'); int main() a[]="{181," 289, 390, 121, 145, 736, 514, 888, 122}; n="sizeof(a)" sizeof(a[0]); printf('before sorting array elements are - 
'); printarray(a,n); radixsort(a, n); printf('after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-8.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C++.</p> <pre> #include using namespace std; int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int output[n + 1]; int count[10] = {0}; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) cout< <a[i]<<' '; } int main() { a[]="{171," 279, 380, 111, 135, 726, 504, 878, 112}; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting array elements are - 
'; printarray(a,n); radixsort(a, n); cout<<'

after applying radix sort, the printarray(a, return 0; < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-9.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in C#.</p> <pre> using System; class RadixSort { static int getMax(int[] a, int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } static void countingSort(int[] a, int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements static void printArray(int[] a, int n) { for (int i = 0; i <n; ++i) console.write(a[i] + ' '); } static void main() { int[] a="{161," 269, 370, 101, 125, 716, 54, 868, 12}; int n="a.Length;" console.write('before sorting array elements are - 
'); printarray(a,n); radixsort(a, n); console.write('

after applying radix sort, the printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-10.webp" alt="Radix Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement Radix sort in Java.</p> <pre> class RadixSort { int getMax(int a[], int n) { int max = a[0]; for(int i = 1; i max) max = a[i]; } return max; //maximum element from the array } void countingSort(int a[], int n, int place) // function to implement counting sort { int[] output = new int[n+1]; int[] count = new int[10]; // Calculate count of elements for (int i = 0; i <n; i++) count[(a[i] place) % 10]++; calculate cumulative frequency for (int i="1;" <10; count[i] +="count[i" - 1]; place the elements in sorted order 1;>= 0; i--) { output[count[(a[i] / place) % 10] - 1] = a[i]; count[(a[i] / place) % 10]--; } for (int i = 0; i 0; place *= 10) countingSort(a, n, place); } // function to print array elements void printArray(int a[], int n) { for (int i = 0; i <n; ++i) system.out.print(a[i] + ' '); } public static void main(string args[]) { int a[]="{151," 259, 360, 91, 115, 706, 34, 858, 2}; n="a.length;" radixsort r1="new" radixsort(); system.out.print('before sorting array elements are - 
'); r1.printarray(a,n); r1.radixsort(a, n); system.out.print('

after applying radix sort, the r1.printarray(a, < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/06/radix-sort-algorithm-11.webp" alt="Radix Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></n;></n;></pre></n;></n;></pre></n;></n;></pre></n;></n;>

TechCodeview

기수 정렬 알고리즘

연산