ฉันมีโปรแกรม Quicksort ที่ใช้งานได้ดีจนกระทั่งฉันพยายามเรียงลำดับอาร์เรย์ที่มีตัวเลขซ้ำกัน โปรแกรมติดอยู่ในวงวนไม่สิ้นสุด ฉันเชื่อว่าสิ่งนี้เกิดขึ้นในบล็อก While(lower < upper)
ของโค้ด
void quickSort(int array[], int size){
if(size < 2) return;
int pivot, lower, upper, temp;
//Set the indeces for the first and last elements
lower = 0;
upper = size - 1;
//Select pivot element randomly
pivot = array[rand() % (size)];
while(lower < upper){
//Lower must be a number < than pivot and upper a number >= pivot
while(array[lower] < pivot){
lower++;
}
while(array[upper] > pivot){
upper--;
}
//Swap upper and lower
temp = array[lower];
array[lower] = array[upper];
array[upper] = temp;
}
//Repeat the past actions on the two partitions of the array recursively
quickSort(array, lower);
quickSort(&array[lower+1], size-lower-1);
}
while
ลูปในสุดทั้งสองลูปจะไม่ทำให้lower
และupper
มาบรรจบกัน อันหนึ่งควรเป็น< pivot
และอีกอันคือ>= pivot
- person Joe Z   schedule 03.12.2013