鳩の巣ソート用のC++プログラム？

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

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

鳩の巣ソートは、カウントソートとも呼ばれ、要素の数（n）と可能なキー値の数（N）がほぼ同じである要素のリストをソートするのに適したソートアルゴリズムです。[1] O（n + N）時間が必要です。

Input: arr[]={7,4,2,6,3,1,5}
Output: 1 2 3 4 5 6 7

説明

• 配列内の最小要素と最大要素を見つけます。最小要素と最大要素は、それぞれ「最小」と「最大」になります。次に、範囲を「max-min-1」として見つけます。

• 範囲と同じサイズの「ピジョンホール」に対して、最初は空の配列を設定します。

• 配列の各要素をトラバースしてから、各要素をピジョンホールに配置します。要素arr[i]は、インデックスarr [i] –minで穴に入れられます。

• ループはピジョンホール配列全体で順番に開始され、空でない穴のすべての要素が元の配列に戻されます。

例

#include <iostream>
using namespace std;
#define MAX 7
void pigeonhole_sort(int, int, int *);
int main() {
   int i, min, max;
   int a[]={7,4,2,6,3,1,5};
   min = a[0];
   max = a[0];
   for (i = 1; i < MAX; i++) {
      if (a[i] < min) {
         min = a[i];
      }
      if (a[i] > max) {
         max = a[i];
      }
   }
   pigeonhole_sort(min, max, a);
   for (i = 0; i < MAX; i++) {
      cout<< a[i]<<"\t";
   }
}
void pigeonhole_sort(int mi, int ma, int * a) {
   int size, count = 0, i;
   int *current;
   current = a;
   size = ma - mi + 1;
   int holes[size];
   for (i = 0; i < size; i++) {
      holes[i] = 0;
   }
   for (i = 0; i < size; i++, current++) {
      holes[*current-mi] += 1;
   }
   for (count = 0, current = &a[0]; count < size; count++) {
      while (holes[count]--> 0) {
         *current++ = count + mi;
      }
   }
}

出力

1 2 3 4 5 6 7