이번 포스팅에서는 counting sort 알고리즘에 대해 알아보겠습니다. 카운팅 정렬은 특정 범위 사이의 키를 기반으로 하는 정렬 기술입니다. 소프트웨어 엔지니어를 위한 코딩이나 기술 인터뷰에서 정렬 알고리즘에 대한 질문이 많이 나옵니다. 따라서 주제에 대해 토론하는 것이 중요합니다.
이 정렬 기술은 요소를 비교하여 정렬을 수행하지 않습니다. 해싱과 같이 고유한 키 값을 갖는 개체를 세어 정렬을 수행합니다. 그런 다음 몇 가지 산술 연산을 수행하여 출력 시퀀스에서 각 개체의 인덱스 위치를 계산합니다. 카운팅 정렬은 범용 정렬 알고리즘으로 사용되지 않습니다.
카운팅 정렬은 범위가 정렬할 개체 수보다 크지 않을 때 효과적입니다. 음수 입력 값을 정렬하는 데 사용할 수 있습니다.
이제 카운팅 정렬 알고리즘을 살펴보겠습니다.
연산
countingSort(array, n) // 'n' is the size of array max = find maximum element in the given array create count array with size maximum + 1 Initialize count array with all 0's for i = 0 to n find the count of every unique element and store that count at ith position in the count array for j = 1 to max Now, find the cumulative sum and store it in count array for i = n to 1 Restore the array elements Decrease the count of every restored element by 1 end countingSort
카운팅 정렬 알고리즘의 작동
이제 계산 정렬 알고리즘의 작동을 살펴보겠습니다.
계산 정렬 알고리즘의 작동을 이해하기 위해 정렬되지 않은 배열을 살펴보겠습니다. 예제를 통해 계산 정렬을 이해하는 것이 더 쉬울 것입니다.
자바의 인터페이스
배열의 요소는 다음과 같습니다.
1. 주어진 배열에서 최대 요소를 찾습니다. 허락하다 최대 최대 요소가 됩니다.
2. 이제 길이 배열을 초기화합니다. 최대 + 1 요소가 모두 0개입니다. 이 배열은 주어진 배열의 요소 수를 저장하는 데 사용됩니다.
3. 이제 각 배열 요소의 개수를 count 배열의 해당 인덱스에 저장해야 합니다.
요소의 개수는 다음과 같이 저장됩니다. 배열 요소 '4'가 두 번 나타났다고 가정하면 요소 4의 개수는 2입니다. 따라서 4에 2가 저장됩니다.일카운트 배열의 위치. 배열에 요소가 없으면 0을 배치합니다. 즉, '3' 요소가 배열에 없다고 가정하면 0이 3에 저장됩니다.rd위치.
이제 누적 합계를 저장합니다. 세다 배열 요소. 정렬된 배열의 올바른 인덱스에 요소를 배치하는 데 도움이 됩니다.
마찬가지로 count 배열의 누적 개수는 -
4. 이제 원본 배열의 각 요소에 대한 인덱스를 찾습니다.
요소를 해당 위치에 배치한 후 개수를 1씩 줄입니다. 요소 2를 배치하기 전에는 해당 개수가 2였지만 올바른 위치에 배치한 후에는 요소 2의 새 개수가 1이 됩니다.
마찬가지로 정렬 후 배열 요소는 다음과 같습니다.
이제 배열이 완전히 정렬되었습니다.
정렬 복잡성 계산
이제 최상의 경우, 평균적인 경우, 최악의 경우 정렬의 시간 복잡도를 살펴보겠습니다. 계산 정렬의 공간 복잡도도 살펴보겠습니다.
1. 시간 복잡도
| 사례 | 시간 | 복잡성 |
|---|---|---|
| 최선의 경우 | O(n + k) | |
| 평균 사례 | O(n + k) | |
| 최악의 경우 | O(n + k) |
위의 모든 경우에서 계산 정렬의 시간 복잡도는 동일합니다. 알고리즘이 진행되기 때문이죠 n+k 요소가 배열에 배치되는 방식에 관계없이 횟수가 발생합니다.
계수 정렬은 요소 간 비교가 없기 때문에 비교 기반 정렬 기술보다 낫습니다. 그러나 정수가 매우 크면 해당 크기의 배열을 만들어야 하기 때문에 계산 정렬이 좋지 않습니다.
2. 공간 복잡성
| 공간 복잡도 | O(최대) |
| 안정적인 | 예 |
- 카운팅 정렬의 공간복잡도는 O(max)이다. 요소의 범위가 클수록 공간 복잡도도 커집니다.
카운팅 정렬 구현
이제 다양한 프로그래밍 언어로 정렬을 계산하는 프로그램을 살펴보겠습니다.
프로그램: 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 countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 16 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; printf('%d ', a[i]); main() a[]="{" 11, 30, 24, 7, 31, }; n="sizeof(a)/sizeof(a[0]);" printf('before sorting are -
'); printarr(a, n); countsort(a, printf('
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-12.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting 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 countSort(int a[], int n) // function to perform counting sort { int output[n+1]; int max = getMax(a, n); int count[max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 11 i++) { a[i]="output[i];" store the sorted elements into main array } void printarr(int a[], int n) * function to print i; for (i="0;" i < n; cout< <a[i]<<' '; main() a[]="{" 31, 11, 42, 7, 30, }; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting are -
'; printarr(a, n); countsort(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-13.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in C#.</p> <pre> using System; class CountingSort { 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 countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 3 i++) { a[i]="output[i];" store the sorted elements into main array } static void printarr(int[] a, int n) * function to print i; for (i="0;" i < n; console.write(a[i] + ' '); main() int[] a="{" 43, 31, 2, 7, 10, 1, 5, 6, }; n="a.Length;" console.write('before sorting are -
'); printarr(a,n); countsort(a,n); console.write('
after pre> <p> <strong>Output</strong> </p> <p>After the execution of above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-14.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in Java.</p> <pre> class CountingSort { 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 countSort(int[] a, int n) // function to perform counting sort { int[] output = new int [n+1]; int max = getMax(a, n); //int max = 42; int[] count = new int [max+1]; //create count array with size [max+1] for (int i = 0; i <= max; ++i) { count[i]="0;" initialize count array with all zeros } for (int i="0;" < n; i++) store the of each element count[a[i]]++; for(int i<="max;" +="count[i-1];" find cumulative frequency * this loop will index original in array, and place elements output array* - 1;>= 0; i--) { output[count[a[i]] - 1] = a[i]; count[a[i]]--; // decrease count for same numbers } for(int i = 0; i<n; 41 i++) { a[i]="output[i];" store the sorted elements into main array } * function to print void printarray(int a[], int n) i; for (i="0;" i < n; system.out.print(a[i] + ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" countingsort c1="new" countingsort(); system.out.println('
before sorting are - c1.printarray(a, n); c1.countsort(a,n); system.out.println('
after system.out.println(); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-15.webp" alt="Counting Sort"> <p> <strong>Program:</strong> Write a program to implement counting sort in PHP.</p> <pre> <?php function getMax($a, $n) { $max = $a[0]; for($i = 1; $i $max) $max = $a[$i]; } return $max; //maximum element from the array } function countSort(&$a, $n) // function to perform counting sort { $LeftArray = array($n + 1); $max = getMax($a, $n); $count = array($max + 1); //create count array with size [max+1] for ($i = 0; $i <= $max; ++$i) { $count[$i] = 0; // Initialize count array with all zeros } for ($i = 0; $i < $n; $i++) // Store the count of each element { $count[$a[$i]]++; } for($i = 1; $i= 0; $i--) { $output[$count[$a[$i]] - 1] = $a[$i]; $count[$a[$i]]--; // decrease count for same numbers } for($i = 0; $i<$n; $i++) { $a[$i] = $output[$i]; //store the sorted elements into main array } } /* Function to print the array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 9, 28, 22, 5, 29, 14, 37, 28, 9 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); countSort($a,$n); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/93/counting-sort-algorithm-16.webp" alt="Counting Sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed counting sort complexity, working, and implementation in different programming languages.</p> <hr></n;></=></pre></n;></=></pre></n;></=></pre></n;></=> 산출
이것이 기사의 전부입니다. 이 기사가 귀하에게 도움이 되고 유익한 정보가 되기를 바랍니다.
이 글은 알고리즘에만 국한된 것이 아닙니다. 또한 다양한 프로그래밍 언어에서의 정렬 복잡성 계산, 작업 및 구현에 대해서도 논의했습니다.