c - 繰り返し数字を並べ替える

Question

 int a[] = {0, 0, 0, 0, 0, 0, 1, 1, 2, 0, 0, 2, 1, 1, 0, 0, 0, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0, 0};

そのようなシリーズをソートするための最良のアプローチは何ですか? 最小限の複雑さが必要であることを覚えておいてください。

Answer 1

数値の上限が小さい場合は、カウント ソートを使用できます。各項目が配列に出現する回数をカウントし、配列を調べて、値ごとにカウントした数の項目を入力します。

たとえば、あなたのケースでは、17 個のゼロ、7 個の 1、および 4 個の 2 を数えます。最初の 17 項目を 0 に、次の 7 項目を 1 に、残りの 4 項目を 2 に設定して、並べ替えられた配列を取得します。

このアプローチには線形の複雑さがあります。

Answer 2

数値系列が実際に値 0 ～ 2 に制限されている場合、最善の方法はカウント スタイルの並べ替えを使用することです。

void CountedSortMaxThree(int* array, size_t length) { 
  int count0 = 0;
  int count1 = 0;
  int count2 = 0;

  for (int i = 0; i < length; i++) { 
    switch(array[i]) {
      case 0: count0++; break; 
      case 1: count1++; break;
      case 2: count2++; break;
    }
  }

  int index = 0;
  while (count0-- > 0) array[index++] = 0;
  while (count1-- > 0) array[index++] = 1;
  while (count2-- > 0) array[index++] = 2;
}

再利用可能にするには、最大値とハードコードされた数値に等しいバケットの配列を定義する必要があります

void CountedSort(int* array, int length, int max) { 
  int* buckets = malloc(sizeof(int) * max);
  for (int i = 0; i < length; i++) { 
    bucket[array[i]]++;
  }

  int index = 0;
  for (int i = 0; i < max; i++) {
    while (buckets[i]-- > 0) {
      array[index++] = i;
    }
  }
  free(buckets);
}

値の範囲が狭い場合にのみカウント ソートを使用する必要があることに注意してください。あなたの例では、範囲は 3 (0 から 2 を含む) であるため、並べ替えをカウントするのに適しています。範囲がはるかに大きい場合 (考えInt32.Maxてみてください)、かなり非効率になる巨大なバケット配列を割り当てることになります

Answer 3

Counting Sortこのようなシリーズの並べ替えに使用できます。

Answer 4

void sort012Dutch(int A[],int n)
{
int pos0=0,pos2=n-1,i=0;
    while(i<n)
{
    if(A[i]==0)
    {
        A[i]=A[pos0];
        A[pos0]=0;
        pos0++;
    }
    if(A[i]==2&&i<pos2)
    {
        A[i]=A[pos2];
        A[pos2]=2;
        pos2--;
        i--;//0 could be swapped
    }
    i++;
}
} 

pos0 は、0 が挿入される
配列内の次のインデックスを示します pos2 は、2 が挿入される配列内の次のインデックスを示します

Answer 5

機能を使用できますqsort。