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が含まれていないパーティションを再帰的に呼び出すと、は0を返しません。

代わりに、ソートするセグメントのサイズ（つまり、high - low）に基づいて再帰を解除する必要があります。 1より小さい場合は、要素が2つ未満のセグメントが既にソートされた順序であることが確かであるため、停止することができます。