鳩の巣ソート

これは、非比較ソート手法の例です。アイテムの数と可能なキー値の範囲がほぼ同じである場合に使用されます。

このようなことを行うには、いくつかの穴を開ける必要があります。必要な穴の数は、数の範囲によって決まります。各穴にアイテムが挿入されます。最後に穴から削除され、並べ替えられた順序で配列に格納されます。

鳩の巣ソート手法の複雑さ

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

入力と出力

Input:
The unsorted list: 802 630 20 745 52 300 612 932 78 187
Output:
Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932

アルゴリズム

pigeonHoleSort(array, size)

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

出力- ソートされた配列

Begin
   find max and min from the array list
   holeRange := max – min +1
   define holeRange number of Lists

   for i := 0 to n-1 do
      hole[array[i]-min].append(array[i])
   done

   count := 0
   for j := 0 to holeRange-1 do
      while hole[j] is not empty do
         array[count] := get first node of hole[j] and delete it
         count := count +1
      done
   done
End

例

#include<iostream>
#include<list>
#include<cmath>
using namespace std;

void getMaxMin(int *arr, int n, int &maximum, int &minimum) {
   maximum = minimum = arr[0]; //initially max and min ar arr[0]

   for(int i = 1; i<n; i++) {
      if(arr[i] > maximum)
         maximum = arr[i]; //get maximum data
      if(arr[i] < minimum)
         minimum = arr[i]; //get minimum data
   }
}

void pegionHoleSort(int *arr, int n) {
   int max, min;
   getMaxMin(arr, n, max, min);
   int holeRange = max - min +1;
   list<int> hole[holeRange]; //create an array of holes

   for(int i = 0; i<n; i++) {
      hole[arr[i]-min].push_back(arr[i]);
   }

   int count = 0;
   for(int j = 0; j<holeRange; j++) {
      //delete from linked lists and store to array
      while(!hole[j].empty()) {
         arr[count] = *(hole[j].begin());
         hole[j].erase(hole[j].begin());
         count++;
      }
   }
}

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

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

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

   cout << "Data before Sorting: ";
   display(arr, n);
   pegionHoleSort(arr, n);
   cout << "Data after Sorting: ";
   display(arr, n);
}

出力

Enter the number of elements: 10
Enter elements:
802 630 20 745 52 300 612 932 78 187
Data before Sorting: 802 630 20 745 52 300 612 932 78 187
Data after Sorting: 20 52 78 187 300 612 630 745 802 932