O(n) 복잡성에서 100개 미만의 숫자 정렬을 구현하는 C++ 프로그램

선형 시간으로 작은 숫자를 정렬하려면 카운팅 정렬 기술을 사용할 수 있습니다.

카운팅 정렬은 작은 숫자의 키에 따라 개체를 정렬하는 데 사용되는 안정적인 정렬 기술입니다. 키 값이 동일한 키의 수를 계산합니다. 이 정렬 기술은 서로 다른 키 간의 차이가 크지 않을 때 효율적이고 그렇지 않으면 공간 복잡성을 증가시킬 수 있습니다.

정렬 기법 계산의 복잡성

• 시간 복잡성 :오(n + r)

• 공간 복잡성 :오(n + r)

Input − A list of unsorted data: 2 5 6 2 3 10 3 6 7 8
Output − Array after Sorting: 2 2 3 3 5 6 6 7 8 10

알고리즘

countingSort(배열, 크기)

입력 − 데이터 배열 및 배열의 ​​총 개수

출력 - 정렬된 배열

Begin
   max = get maximum element from array.
   define count array of size [max+1]
   for i := 0 to max do
      count[i] = 0 //set all elements in the count array to 0
   done
   for i := 1 to size do
      increase count of each number which have found in the array
   done
   for i := 1 to max do
      count[i] = count[i] + count[i + 1] //find cumulative frequency
   done
   for i := size to 1 decrease by 1 do
      store the number in the output array
      decrease count[i]
   done
   return the output array
End

예시 코드

#include <iostream>
using namespace std;
void counting_sort(int array[], int n) {
   int i, j;
   int count[n];
   for (i = 0; i < n; i++)
      count[i] = 0;
   for (i = 0; i < n; i++)
      (count[array[i]])++;
   for (i = 0, j = 0; i < n; i++)
      for (; count[i] > 0; (count[i])--)
         array[j++] = i;
}
int main() {
   int array[100], i, num;
   cout << "Enter the size of array : ";
   cin >> num;
   cout << "Enter the " << num << " elements to be sorted:" << endl;
   for (i = 0; i < num; i++)
      cin >> array[i];
   cout << "\nThe array of elements before sorting : " <<endl;
   for (i = 0; i < num; i++)
      cout << array[i] << " ";
   cout << "\nThe array of elements after sorting : " << endl;
   counting_sort(array, num);
   for (i = 0; i < num; i++)
      cout << array[i] << " ";
   return 0;
}

출력

Enter the size of array : 8

Enter the 8 elements to be sorted:
54 89 23 20 18 88 65 31

The array of elements before sorting :
54 89 23 20 18 88 65 31

The array of elements after sorting :
54 89 23 20 18 88 65 31