快速排序輸出不一致

Question

我想體驗快速排序的最壞情況。因此，我按降序生成一個數組。按快速排序進行排序後，數組的第一個元素有時變成垃圾，而有時變爲0。當第一元件成爲垃圾的所有元素的順序向上滑動，第二元素變成0，第三元件變爲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()中循環之前。
• 撥打quickSort()並輸入正確的索引 - 0和n-1。

實驗表明do { … } while (j > i);環配方也乾淨地工作。

這些變化導致：

#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; 
} 

的代碼產生正確的輸出，AFAICS：

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 
}