QuickSort в C++, проблема

Question

Я пытаюсь написать этот алгоритм для C++, но когда я пытаюсь запустить его, ничего не возникает. Я смотрел на все с точки зрения того, что не так, но я не могу его найти. Я не программировал через год, поэтому я возвращаюсь к вещам. Любая помощь будет оценена, спасибо.

#include <iostream> 

using namespace std; 

void quickSort(int A[], int p, int r); 
int partition(int A[], int p, int r); 

int main(void) 
{ 
    int elements = 8; 
    int number[8] = { 2, 8, 7, 1, 3, 5, 6, 4 }; 

    int first = 0; 
    int last = elements - 1; 

    quickSort(number, first, last); 

    cout << "Sorted elements: "; 

    for (int i = 0; i < elements; i++) 
    { 
     cout << number[i] << " "; 
    } 

    cout << endl; 

    return 0; 

} 

void quickSort(int A[], int p, int r) 
{ 
    if (p < r) 
    { 
     int q= 0; 
     q = partition(A, p, r); 
     quickSort(A, p, q - 1); 
     quickSort(A, q + 1, r); 
    } 
} 

int partition(int A[], int p, int r) 
{ 
    int temp; 

    int x = A[r]; 
    int i = p - 1; 
    for (int j = 0; j < r - 1; j++) 
    { 
     if (A[j] <= x) 
     { 
      i++; 
      temp = A[j]; 
      A[j] = A[i]; 
      A[i] = temp; 
     } 
    } 

    temp = A[r]; 
    A[r] = A[i + 1]; 
    A[i + 1] = temp; 

    return (i+1); 
} 

Answer 1

Ваше состояние Loop внутри функции распределения должно быть:

for (int j = p; j <= r-1; j++) 

Это должно исправить.

Answer 2

меня быстро проверили программу и для этого входа эта версия дает мне правильный вывод:

int partition(int A[], int p, int r) 
{ 
    int temp; 

    int x = A[r]; 
    int i = p - 1; 
    for (int j = p; j < r; j++) 
    { 
     if (A[j] <= x) 
     { 
      i++; 
      temp = A[j]; 
      A[j] = A[i]; 
      A[i] = temp; 
     } 
    } 

    temp = A[r]; 
    A[r] = A[i + 1]; 
    A[i + 1] = temp; 

    return (i+1); 
} 

Изменение находится в пределах цикла.

Answer 3

Вы код stucks в бесконечной рекурсии и потребляет память до вызова неопределенное поведение. Поэтому он может прекратить выполнение и ничего не печатать.

У вашей функции partition есть серьезные проблемы, в то время как я не могу узнать вашу логику, вы должны использовать отладчик, чтобы уловить проблему. Проверьте переменные i и j. Например, это быстрое решение сделало некоторый вывод, который является правильным:

for (int j = i+1; j < r ; j++) 
      ^^^ ^

Выходной:

Отсортированных элементы: 1 2 3 4 5 6 7 8

я не уверен, что будет работать для любого размера данных или нет. Live code.