Я написал код быстрой сортировки и логика кажется довольно правильной, но на консоли нет вывода

Question

Я написал код быстрой сортировки, и логика кажется довольно правильной, но на консоли нет вывода.

, когда работает только функция индекса, вывод корректен, а цикл вывода корректен, но когда функция quicSortдобавляется, то нет выхода.

#include <iostream>
using namespace std;
int index(int* a, int s, int e) {
  int i, j, start, piv, temp;
  start = s;

  piv = a[e];

  for (i = start; i <= e; i++) {
    if (a[i] <= piv) {
      temp = a[i];
      a[i] = a[start];
      a[start] = temp;
      start++;
    }
  }

  return start;
}

void quickSort(int* a, int s, int e) {
  int pivot;
  if (s < e) {
    pivot = index(a, s, e);
    quickSort(a, s, pivot - 1);
    quickSort(a, pivot + 1, e);
  }
}

int main() {
  int A[] = {2, 5, 8, 3, 6, 9, 1, 4};
  quickSort(A, 0, 7);

  for (int i = 0; i < 8; i++) {
    cout << A[i];
  }

  return 0;
}

на выходе должен быть отсортированный массив

Answer 1

Код нуждается в двух исправлениях.Изменения отмечены в комментариях:

#include <iostream>
using namespace std;
int index(int* a, int s, int e) {
  int i, start, piv;            // j, temp not used
  start = s;

  piv = a[e];

  for (i = start; i <= e; i++) {
    if (a[i] < piv) {           // fix (not <=)
      swap(a[i], a[start]);     // simplify
      start++;
    }
  }
  swap(a[start], a[e]);         // fix (swap pivot into place)

  return start;
}

void quickSort(int* a, int s, int e) {
  int pivot;
  if (s < e) {
    pivot = index(a, s, e);
    quickSort(a, s, pivot - 1);
    quickSort(a, pivot + 1, e);
  }
}

int main() {
  int A[] = {2, 5, 8, 3, 6, 9, 1, 4};
  quickSort(A, 0, 7);

  for (int i = 0; i < 8; i++) {
    cout << A[i] << " ";        // put space beteen numbers
  }
  cout << endl;

  return 0;
}

Answer 2

Я думаю, что вы запутались в пузырьковой сортировке при создании программы быстрой сортировки.

Идея быстрой сортировки состоит в том, чтобы разбить вектор на меньшие векторы, числа с числами, большими, чем точка, а другой, с числами, меньшими, чем точка.

Вы должны округлить свой код в структурах данных C ++, таких как векторы.

Один пример с c ++ 11:

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

vector<int> quicksort(vector<int> data) {
  if (data.size() == 1) return data;
  vector<int> small_numbers;
  vector<int> big_numbers;
  vector<int> ret;
  float pivot = accumulate(data.begin(), data.end(), 0.0) / data.size();

  for (int value : data) {
    if (value < pivot) {
      small_numbers.push_back(value);
    } else {
      big_numbers.push_back(value);
    }
  }
  if (small_numbers.empty()) return big_numbers;

  small_numbers = quicksort(small_numbers);
  big_numbers = quicksort(big_numbers);

  ret.insert(ret.end(), small_numbers.begin(), small_numbers.end());
  ret.insert(ret.end(), big_numbers.begin(), big_numbers.end());

  return ret;
}

int main() {
  vector<int> A({2, 5, 8, 3, 6, 9, 1, 4});

  A = quicksort(A);

  for (int value : A) cout << value << endl;

  return 0;
}

В этом примере вектор разбит на два вектора, а ось - это среднее значение значений вектора. Он вызывает функцию рекурсивно, пока не вызовет вектор размером 1 элемент.

Надеюсь, это подтолкнет вас к менее сложному способу быстрой сортировки.