C++ - 連想配列では、値でソートした後にキーで検索できません。

Question

以下のコードでは、アルファベットの文字とそれらに関連付けられた任意の値を含む連想配列があります。私は値の降順に基づいてそれらを並べ替えるためのクイックソート機能を実装しました。私は特定のキー（文字）を検索するバイナリ検索機能を持っています。私はソートの前にバイナリ検索がうまく動作しますが、ソートした後は、それを使っていくつかの文字しか見つけられません。私自身で処理しようとすると、quickSort（）を実行する前と後に配列をループし、ソートされていてもそれらの値がまだ存在することを確認しているようです。私は間違って何をしていますか？

#include <iostream> 
#include <array> 

using namespace std; 

int binarySearch(int arr[][2], int value, int left, int right) 
{ 
    while (left <= right) 
    { 
     int middle = (left + right)/2; 
     if (arr[middle][0] == value) 
      return middle; 
     else if (arr[middle][0] > value) 
      right = middle - 1; 
     else 
      left = middle + 1; 
    } 
    return -1; 
} 

void quickSort(int arr[][2], int left, int right) 
{ 
    int i = left, j = right; 
    int tmp1, tmp2; 
    int pivot = arr[(left + right)/2][1]; 

    /* partition */ 
    while (i <= j) 
    { 
     while (arr[i][1] > pivot) 
      i++; 
     while (arr[j][1] < pivot) 
      j--; 
     if (i <= j) 
     { 
      tmp1 = arr[i][0]; 
      tmp2 = arr[i][1]; 

      arr[i][0] = arr[j][0]; 
      arr[i][1] = arr[j][1]; 

      arr[j][0] = tmp1; 
      arr[j][1] = tmp2; 

      i++; 

      j--; 
     } 
    }; 

    /* recursion */ 
    if (left < j) 
     quickSort(arr, left, j); 
    if (i < right) 
     quickSort(arr, i, right); 

} 

int main() 
{ 
    const int alphLength = 26; 
    int assocArr[alphLength][2] = { {'A', 5}, {'B', 2}, {'C', 4}, {'D', 3}, {'E', 1}, {'F', 0}, {'G', 0}, {'H', 0}, {'I', 0}, 
     {'J', 0}, {'K', 0}, {'L', 0}, {'M', 0}, {'N', 0}, {'O', 0}, {'P', 75}, {'Q', 0}, {'R', 0}, 
     {'S', 0}, {'T', 0}, {'U', 0}, {'V', 0}, {'W', 0}, {'X', 50}, {'Y', 0}, {'Z', 100} }; 

char a; 
char searchLetter = 'Z'; 

for (int i = 0; i < alphLength; i++) 
{ 
    a = assocArr[i][0]; 
    cout << "index " << i << ": " << a << endl; 
} 

cout << "found " << searchLetter << " before quickSort() at " << binarySearch(assocArr, searchLetter, 0, alphLength-1) << endl; 

quickSort(assocArr, 0, alphLength-1); 

for (int i = 0; i < alphLength; i++) 
{ 
    a = assocArr[i][0]; 
    cout << "index " << i << ": " << a << endl; 
} 

cout << "found " << searchLetter << " after quickSort() at " << binarySearch(assocArr, searchLetter, 0, alphLength-1) << endl; 

} 

Answer 1

バイナリ検索は、ソートされた配列でのみ機能し、検索で比較するのと同じ基準でソートする必要があります。あなたの配列は文字の昇順でソートされ、バイナリ検索は文字の昇順で検索されるので、これは動作します。値でソートすると、文字をスクランブルします。バイナリ検索を再度昇順に実行すると、配列は昇順で並べ替えられないため、動作しません。