[QuickSort] Проблемы с рекурсией

Question

Когда я запускал свой код QuickSort и вводил числа. Не было никакого выхода. Я не знаю проблемы.

Вот мой код:

#include <stdio.h> 
#include <stdlib.h> 

void quickSort(int *pA, int left, int right) { 
    int i, j, t, temp; 
    temp = pA[left]; 
    i = left; 
    j = right; 
    while (i != j) { 
     while (i < j && pA[j] >= temp) 
      j--; 
     while (i < j && pA[i] <= temp) 
      i++; 
     if (i < j) { 
      t = pA[i]; 
      pA[i] = pA[j]; 
      pA[j] = t; 
     } 
    } 
    pA[left] = pA[i]; 
    pA[i] = temp; 
    quickSort(pA, left, i - 1); 
    quickSort(pA, i + 1, right); 
} 

int main() { 
    int i, n, a[100]; 
    printf("please input the total of numbers:"); 
    scanf("%d", &n); 
    for (i = 0; i < n; i++) { 
     printf("number %d is:", i + 1); 
     scanf("%d", &a[i]); 
    } 
    quickSort(&a, 0, n - 1); 
    for (i = 0; i < n; i++) { 
     printf("%d ", a[i]); 
    } 
    return 0; 
} 

Следующая был код работает картинка:

Answer 1

Вы должны добавить тест в вашей рекурсивной quickSort для него, чтобы остановить рекурсии! Например, сегмент из всего лишь 1 записи, очевидно, отсортирован.

Вот исправленный вариант:

#include <stdio.h> 

void quickSort(int *pA, int left, int right) { 
    int i, j, t, temp; 
    if (right - left < 1) 
     return; 
    temp = pA[left]; 
    i = left; 
    j = right; 
    while (i != j) { 
     while (i < j && pA[j] >= temp) 
      j--; 
     while (i < j && pA[i] <= temp) 
      i++; 
     if (i < j) { 
      t = pA[i]; 
      pA[i] = pA[j]; 
      pA[j] = t; 
     } 
    } 
    pA[left] = pA[i]; 
    pA[i] = temp; 
    quickSort(pA, left, i - 1); 
    quickSort(pA, i + 1, right); 
} 

int main(void) { 
    int i, n, a[100]; 
    printf("please input the total of numbers: "); 
    scanf("%d", &n); 
    for (i = 0; i < n; i++) { 
     printf("number %d is: ", i + 1); 
     scanf("%d", &a[i]); 
    } 
    quickSort(a, 0, n - 1); 
    for (i = 0; i < n; i++) { 
     printf("%d ", a[i]); 
    } 
    printf("\n"); 
    return 0; 
}