빠른 정렬이 일치하지 않습니다.

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().
• 올바른 인덱스 -및 n-1을 사용하여 quickSort()으로 전화하십시오.

루프 배합도 깨끗하게 작동한다는 실험 결과가 나온다. 코드가 올바른 출력, 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; 
} 

:

이러한 변화로 이어질

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 
}