インデックス付きアレイクイックソートデバッグ

Question

私はこの特別なクイックソートアルゴリズムよりも頑張りますが、どこに問題があるのか​​わかりません。私は何をしようとしているかを非常によく説明するフォーラムの例を見つけました。 （データ配列内の要素 を表す）の連続、 注文番号のインデックス配列を考えると、あなたはまだ に持って

は、データ値を比較します。あなたはちょうど のインデックスにアクセスしてください。 のインデックス値は交換しますが、 のデータ値は入れ替えません。

Unsorted data: 09 04 47 05 03 12 
Index array: 00 01 02 03 04 05 

After sort, 
Unsorted data: 09 04 47 05 03 12 
Index array: 04 01 03 00 05 02 

Print the values indexed by the index array, 
from beginning to end of the array: 

Index array [0] value [04] data array [04] = 03 
      [1]  01    [01] 04 
      [2]  03    [03] 05 
      [3]  00    [00] 09 
      [4]  05    [05] 12 
      [5]  02    [02] 47 

Output is the data, ordered at the output 

私は一つのことを追加します。コンパレータは、2つの異なる文字を同じ値で比較する場合、それぞれの次の文字を比較し、その結果を返すという例外を除いて、通常のコンパレータです。つまり、回転を比較することです。

int compare(unsigned char i, unsigned char j); 

私はそれが完璧に動作すると確信しているので、私は定義を投稿しません。バグはクイックソートの定義にあります。

void quicksort(unsigned char* a, unsigned char left, unsigned char right) { 
    unsigned char i = left; 
    unsigned char j = right; 
    unsigned char half = (left + right)/2; 
    while (i <= j) { 
     while ((compare(a[i], a[half]) == -1) && (i < right)) 
      i++; 
     while ((compare(a[j], a[half]) == 1) && (j > left)) 
      j--; 

     if (i <= j) { 
      unsigned char aux = a[i]; 
      a[i] = a[j]; 
      a[j] = aux; 
      i++;  //THERE 
      j--;  //THERE 
     } 

    } 

    if (left < j) 
     quicksort(a, left, j); 
    if (i < right) 
     quicksort(a, i, right); 

} 

時々私= 255及びj = 0、と私はなぜ、プログラムがためにそこに取得していない、とその値がオーバーフローを行きます。私はバグを何千回も見つけたので、どこが間違っているのか分かりません。
メモ： 1）私はC++の符号なしchar範囲を完全に認識しており、intに変更することはできません。 2）実際のデータ配列の宣言は実際には含まれません。 compare関数は、そのクラスの属性であるため、それにアクセスできます。

Answer 1

符号なしの文字に255より大きい数値または0より小さい数値を格納することはできません。符号なしの文字は、符号なしの1バイトで定義された範囲を格納できるため、8進数は8です。 2^8 = 256、0を含むので256 - 1で255を返します。（または16進数で0xFF）

intsまたはshortを使用してみてください。 （キーワードshort）