Chương trình C ++ để thực hiện sắp xếp các số ít hơn 100 trong độ phức tạp O (n)

Để sắp xếp một số số nhỏ theo thời gian tuyến tính, chúng ta có thể sử dụng kỹ thuật sắp xếp đếm.

Sắp xếp đếm là một kỹ thuật sắp xếp ổn định, được sử dụng để sắp xếp các đối tượng theo các khóa là số nhỏ. Nó đếm số lượng khóa có giá trị chính giống nhau. Kỹ thuật sắp xếp này hiệu quả khi sự khác biệt giữa các khóa khác nhau không quá lớn, nếu không, nó có thể làm tăng độ phức tạp của không gian.

Độ phức tạp của Kỹ thuật sắp xếp đếm

• Độ phức tạp về thời gian :O (n + r)

• Độ phức tạp của không gian :O (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

Thuật toán

countSort (mảng, kích thước)

Đầu vào - Một mảng dữ liệu và tổng số trong mảng

Đầu ra - Mảng được sắp xếp

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

Mã mẫu

#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;
}

Đầu ra

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