クイックソートの出力が一貫しない

Question

クイックソートの最悪のケースを経験したい。したがって、降順で配列を生成します。クイックソートでソートした後、配列の最初の要素がガベージになることがありますが、時には期待通りに0になることもあります。最初の要素は、すべての要素の順序がアップスライドゴミになると、2番目の要素は0になると、第3の要素は1などとなり ここに私のコード：ホーアのパーティションスキーム使用

void generateDescendingArray(int *arr, int n) { 

    for(int i = n - 1; i >= 0; i--) { 
     arr[n-i-1] = i; 
    } 
} 

void quickSort(int *A, int start, int end) { 
    if(end > start) { 
     int s = partition(A, start, end); //split position 
     quickSort(A, start, s - 1); //sort before the split 
     quickSort(A, s + 1, end); //sort after the split 
    } 
} 
int partition(int *A, int start, int end) { 

    int pivot = A[start]; 
    int i = start; 
    int j = end + 1; 

    do { 

     do { i++; 
     } while(pivot > A[i]); 

     do { j--; 
     } while(pivot < A[j]); 

     swap(&A[i], &A[j]); 

    } while(j > i); 
    swap(&A[i], &A[j]); //undo last swap when i >= j 
    swap(&A[start], &A[j]); 

    return j; 
} 
int main() { 
    int A[n]; 
    generateDescendingArray(A, n); 
    quickSort(A, 0, n); 

    return 0; 
} 

Answer 1

を診断したようコメントで、以下を行う必要があります。

• 防止iとjをチェックして、空のパーティション上のスキャンループする前にpartition()。
• 正しいインデックス（0およびn-1）を使用してquickSort()を呼び出します。

実験では、do { … } while (j > i);ループ処方もきれいに機能することが示唆されています。

これらの変更は、につながる：コードが正しい出力、AFAICS生成

#include <stdio.h> 

static inline void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; } 
static int partition(int *A, int start, int end); 

static 
void generateDescendingArray(int *arr, int n) { 

    for(int i = n - 1; i >= 0; i--) { 
     arr[n-i-1] = i; 
    } 
} 

static 
void quickSort(int *A, int start, int end) { 
    if(end > start) { 
     int s = partition(A, start, end); //split position 
     quickSort(A, start, s - 1); //sort before the split 
     quickSort(A, s + 1, end); //sort after the split 
    } 
} 

static 
int partition(int *A, int start, int end) { 

    int pivot = A[start]; 
    int i = start; 
    int j = end + 1; 

    while (i < j) 
    { 

     do { i++; 
     } while(pivot > A[i]); 

     do { j--; 
     } while(pivot < A[j]); 

     swap(&A[i], &A[j]); 

    } 
    swap(&A[i], &A[j]); //undo last swap when i >= j 
    swap(&A[start], &A[j]); 

    return j; 
} 

enum { NUM_PER_LINE = 10 }; 

static void print_data(const char *tag, const int *A, int num) 
{ 
    printf("%s (%d):\n", tag, num); 
    const char *pad = ""; 
    int i; 
    for (i = 0; i < num; i++) 
    { 
     printf("%s%d", pad, A[i]); 
     pad = " "; 
     if (i % NUM_PER_LINE == NUM_PER_LINE - 1) 
     { 
      putchar('\n'); 
      pad = ""; 
     } 
    } 
    if (i % NUM_PER_LINE != 0) 
     putchar('\n'); 
} 

int main(void) { 
    for (int n = 1; n < 24; n++) 
    { 
     int A[n]; 
     generateDescendingArray(A, n); 
     print_data("Unsorted", A, n); 
     quickSort(A, 0, n-1); 
     print_data("Sorted", A, n); 
    } 

    return 0; 
} 

：（J> I）ながら `ん{...}を使用しないでください

Unsorted (1): 
0 
Sorted (1): 
0 
Unsorted (2): 
1 0 
Sorted (2): 
0 1 
Unsorted (3): 
2 1 0 
Sorted (3): 
0 1 2 
Unsorted (4): 
3 2 1 0 
Sorted (4): 
0 1 2 3 
… 
Unsorted (21): 
20 19 18 17 16 15 14 13 12 11 
10 9 8 7 6 5 4 3 2 1 
0 
Sorted (21): 
0 1 2 3 4 5 6 7 8 9 
10 11 12 13 14 15 16 17 18 19 
20 
Unsorted (22): 
21 20 19 18 17 16 15 14 13 12 
11 10 9 8 7 6 5 4 3 2 
1 0 
Sorted (22): 
0 1 2 3 4 5 6 7 8 9 
10 11 12 13 14 15 16 17 18 19 
20 21 
Unsorted (23): 
22 21 20 19 18 17 16 15 14 13 
12 11 10 9 8 7 6 5 4 3 
2 1 0 
Sorted (23): 
0 1 2 3 4 5 6 7 8 9 
10 11 12 13 14 15 16 17 18 19 
20 21 22 

Answer 2

：

int partition(int *A, int start, int end) { 

    int i = start - 1; 
    int j = end + 1; 
    int pivot = start; 

    while(1) { 
     while (A[++i] < A[pivot]); 
     while (A[--j] > A[pivot]); 

     if (i >= j) { 
     return j; 
     } 
     // swap A[i] and A[j] 
    } 

    return j; 
} 

void quickSort(int *A, int start, int end) { 
    if(start < end) { 
     int s = partition(A, start, end); 
     quickSort(A, start, s); 
     quickSort(A, s + 1, end); 
    } 
} 

int main() { 
    ... 
    quickSort(A, 0, n - 1); // CHANGED to n - 1 because you already have + 1 in partition 
}