Quicksort w konsoli C++

Question

Witam,

po wielu trudach zrozumiałem działanie algorytmu sortowania szybkiego, jednak nie potrafię dostrzec błędu w moim kodzie:

#include <iostream>
#include <time.h>

using namespace std;

void quicksort(int *tablica, int poczatek, int koniec) {
	int pivot = tablica[(poczatek - koniec) / 2];
	int i, j, x;
	i = poczatek;
	j = koniec;
	do {
		while (tablica[i] < pivot) i++;
		while (tablica[j] > pivot)  j--;
		if (i <= j) {
			x = tablica[i];
			tablica[i] = tablica[j];
			tablica[j] = x;
		}
		} while (i <= j);
		if (j > poczatek) quicksort(tablica, poczatek, j);
		if (i < koniec) quicksort(tablica, i, koniec);
	}

int main() {
	srand(time(NULL));
	int ile;
	cout << "Ile liczb:";
	cin >> ile;
	int* tablica = new int[ile];
	cout << "\n Przed sortowaniem: ";
	for (int i(0); i < ile; i++) {
		tablica[i] = rand() % 100;
		cout << endl << tablica[i];
	}
	quicksort(tablica, 0, ile - 1);
	cout << endl << "Po sortowaniu:";
	for (int i(0); i < ile; i++) {
	
		cout << endl << tablica[i];
	}
	return 0;
}

Konsola wypisuje liczby z pierwszego for'a, następnie program zawiesza się. Wiele wskazuje na to, że dzieje się to w linijce wywołującej funkcję quicksort().

Answer 1

Masz źle wyliczany pivot. Poza tym potrzebne jest także dodatkowe przesunięcie indeksów i , j .

void quicksort(int* tablica, int poczatek, int koniec) {  
  
  int i = poczatek;
  int j = koniec;
  int pivot = tablica[(i + j)/2];  

  while (i <= j) {
    while (tablica[i] < pivot) i++;
    while (tablica[j] > pivot) j--;
    if (i <= j) {
      int x = tablica[i];
      tablica[i] = tablica[j];
      tablica[j] = x;
      ++i;
      --j;
    }
  }

  if (j > poczatek) quicksort(tablica, poczatek, j);
  if (i < koniec) quicksort(tablica, i, koniec);
}