QuickSort Бесконечная петля в C?

Question

Я сталкиваюсь с проблемой бесконечного цикла в моем алгоритме быстрой сортировки, эта вещь происходит в правом разделе подэлемента, поэтому, если я разделяю только левый дополнительный массив, он отлично работает, как этот код.

#include <stdio.h> 
int list[] = {8, 1, 3, 4, 2, 10, 4, 6}; 
//int list[] = {2, 1, 10, 4, 5, 11, 12, 6}; 
//int list[] = {1, 2, 4, 5, 6, 11, 12, 10}; 
int main(int argc, char **argv) 
{ 

    printf("Unsorted list is: "); 
    printArray(list); 
    quickSort(list, 0, 7); 
    //partition(list, 5, 7); 
    printf("Sorted list is: "); 
    printArray(list); 

    return 0; 
} 

void printArray(int list[]){ 
    int i; 
    for(i = 0; i < 8; i++){ 
     printf(" %d ", list[i]); 
    } 
    printf("\n\n"); 
} 

void quickSort(int list[], int low, int high){ 

    int pIndex = partition(list, low, high); 

    if(pIndex <= 0){ 
     return; 
    } 

    //quick sort left sub array 
    quickSort(list, low, pIndex-1); 

    //quick sort right sub array 
// quickSort(list, pIndex+1, high); 

    printf("pIndex is %d\n", pIndex); 
} 

int partition(int list[], int low, int high){ 
    int pivot = list[high]; 


    int i; 
    int j = high - 1; 
// int j = high; 


    while(1){ 
     //less than pivot 
     for(i = 0; list[i] < pivot; i++){ 
      printf("for %d (index %dth) < %d\n", list[i], i, pivot); 
      //do nothing 
     } 
     printf("less than stop at index %d which is %d\n", i, list[i]); 

     //more than pivot 
     for(j = j; j > 0 && pivot < list[j]; j--){ 
      printf("for %d < %d (index %dth)\n", pivot, list[j], j); 
     } 
     printf("greater than stop at index %d which is %d\n", j, list[j]); 

     if(i >= j){ 
     printf("low index %d >= %d then swap pivot\n", i, j); 
     printf("swap index %dth which is %d, with index pivot %d which is %d\n", i, list[i], high, list[high]); 
     swap(list, i, high); 

     printf("Temporary list is: "); 
     printArray(list); 

     printf("then return last position index pivot %d which is %d\n", i, list[i]); 
     return i; 
     break; 
     } 

     //tukarPosisi, sehingga yang kecil di sebelah kiri, yang besar di sebelah kanan. 
     printf("swap index %dth which is %d, with index %dth, which is %d\n", i, list[i], j, list[j]); 
     swap(list, i, j); 

     printf("Temporary list is: "); 
     printArray(list); 


    } 
} 

void swap(int list[], int i, int j){ 
    //variabel sementara untuk menampung i 
    int temporary = list[i]; 

    //tukar posisi, sehingga yg kecil di kiri, yg besar di kanan. 
    list[i] = list[j]; 
    list[j] = temporary; 
} 

У меня уже есть много отладки, но до сих пор не могу понять, почему это происходит. Так где же логика неправильная и как ее исправить?

Любая помощь будет оценена

Answer 1

У вас есть несколько проблем с вашим кодом, в основном, влияющих на его эффективность, а не его правильность. Некоторые из них были вызваны в комментариях. Самая большая проблема, однако, - это условие завершения для вашей рекурсии, как вы могли бы ожидать, учитывая характер неправильного поведения.

В частности, ваши рекурсии нижнего предела, когда partition() возвращает значение меньше или равно нулю, но эта функция всегда возвращает конечную позицию, выбранную для поворота. Если вы рекурсируете только левую часть ваших разделов, то вы наверняка получите нулевой результат в конце концов, но когда вы перечислите любой раздел, который не включает элемент 0, partition() никогда не вернется 0.

Вместо этого вы должны отказаться от рекурсии на основе размера сегмента, подлежащего сортировке (то есть high - low). Если он меньше 1, вы можете остановиться, потому что сегмент с менее чем двумя элементами определенно будет уже в отсортированном порядке.