ソートのカウント

カウントソートは安定したソート手法であり、少数のキーに従ってオブジェクトをソートするために使用されます。キー値が同じキーの数をカウントします。この並べ替え手法は、異なるキー間の差がそれほど大きくない場合に効果的です。そうでない場合は、スペースが複雑になる可能性があります。

ソート手法のカウントの複雑さ

• 時間計算量：O（n + r）
• スペースの複雑さ：O（n + r）

入力と出力

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

アルゴリズム

counting sort(array, size)

入力 ：データの配列、および配列内の総数

出力 ：ソートされた配列

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>
#include<algorithm>
using namespace std;

void display(int *array, int size) {
   for(int i = 1; i<=size; i++)
      cout << array[i] << " ";
   cout << endl;
}

int getMax(int array[], int size) {
   int max = array[1];
   for(int i = 2; i<=size; i++) {
      if(array[i] > max)
         max = array[i];
   }

   return max; //the max element from the array
}

void countSort(int *array, int size) {
   int output[size+1];
   int max = getMax(array, size);
   int count[max+1]; //create count array (max+1 number of elements)

   for(int i = 0; i<=max; i++)
      count[i] = 0; //initialize count array to all zero
   for(int i = 1; i <=size; i++)
      count[array[i]]++; //increase number count in count array.
   for(int i = 1; i<=max; i++)
      count[i] += count[i-1]; //find cumulative frequency

   for(int i = size; i>=1; i--) {
      output[count[array[i]]] = array[i];
      count[array[i]] -= 1; //decrease count for same numbers
   }

   for(int i = 1; i<=size; i++) {
      array[i] = output[i]; //store output array to main array
   }
}

int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n+1]; //create an array with given number of elements
   cout << "Enter elements:" << endl;

   for(int i = 1; i<=n; i++) {
      cin >> arr[i];
   }

   cout << "Array before Sorting: ";
   display(arr, n);
   countSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

出力

Enter the number of elements: 10
Enter elements:
2 5 6 2 3 10 3 6 7 8
Array before Sorting: 2 5 6 2 3 10 3 6 7 8
Array after Sorting: 2 2 3 3 5 6 6 7 8 10