그중 퀵소트와 관련해서 미궁에 빠졌네요.
책의 336페이지에 보면 퀵소트를 아래와 같이 구현해놓았어요.
void quicksort(element list[], int left, int right)
{
int pivot, i, j;
element temp;
if( left < right ) {
i = left, j = right + 1;
pivot = left[left].key;
do {
do {
i++;
} while (list[i].key < pivot);
do {
j--;
} while (list[j].key > pivot);
if( i < j )
SWAP(list[i], list[j], temp);
} while ( i < j );
SWAP(list[left],list[j],temp);
quicksort(list, left, j-1);
quicksort(list, j+1, right);
}
}
여기서 질문.
7~9줄에 i가 list배열의 index를 벗어나지 않는다는 걸 어떻게 보장하죠??
예를 들어 pivot 값이 배열에서 가장 큰 값이라고 가정하면
9라인의 while(list[i].key < pivot)은 언제나 true이므로
i는 계속해서 커지다가 list배열의 인덱스 바깥으로 튀어나가 에러를 만들지 않을까요??
책의 오른쪽 여백에 예전에 보면서 끼적거려놓은게 있는데 "pivot값이 최대값이면 어떻하지?"라고 되어있습니다. 그래서 어쩌라고 ㅡㅜ 과거의 내가 미래의 나에게 숙제를 던지는 아햏햏한 시츄에이션이어요.
Posted by 망고
