Przeczytaj

Algorytm sortowania szybkiego – implementacja w języku C++

Aby skonstruować algorytm sortowania szybkiego, możemy napisać dwie funkcje, w tym jedną wywoływaną rekurencyjniezasada „dziel i zwyciężaj”rekurencyjnie. Wykonujemy w tym celu następujące kroki:

Tworzymy nagłówek funkcji, w którym zapisujemy typ zwracanej wartości (w tym przypadku funkcja nic nie zwraca, zatem podajemy typ void), nazwę funkcji quicksort, oraz w okrągłych nawiasach podajemy argumenty, jakie funkcja przyjmuje.
Zapisujemy warunek sprawdzany w funkcji. Sprawdzamy, czy IndeksPoczatkowy jest mniejszy od IndeksKoncowy. Gdyby tak nie było, rozmiar tablicy byłby ujemny bądź równy 0, zatem nie byłoby możliwe operowanie na nieistniejącej tablicy.
W przypadku, gdy tablica istnieje, deklarujemy zmienną a równą zwracanej wartości przez funkcję PodzielTablice(). Następnie rekurencyjnie wywołujemy funkcję quicksort dla dwóch oddzielnych części tablicy: pierwszy raz dla części od początku tablicy do wartości zmiennej a pomniejszonej o 1, zaś drugi dla części tablicy od wartości zmiennej a powiększonej o 1 do końca tablicy.

Po wykonaniu tych kroków uzyskujemy kod, który prezentuje się następująco:

void quicksort(int tab[],int IndeksPoczatkowy, int IndeksKoncowy)
{

	if (IndeksPoczatkowy < IndeksKoncowy)
	{
		int a = PodzielTablice(tab, IndeksPoczatkowy, IndeksKoncowy);

		quicksort(tab, IndeksPoczatkowy, a - 1);
		quicksort(tab, a + 1, IndeksKoncowy);
	}
}

Następnie tworzymy funkcję PodzielTablice(), która będzie odpowiedzialna za posortowanie tablicy w taki sposób, aby liczba pivot była na środku, liczby od niej mniejsze po jej lewej stronie, a większe – po prawej. W tym celu musimy wykonać następujące kroki:

Tworzymy nagłówek funkcji, w którym zapisujemy typ zwracanej zmiennej (int), nazwę funkcji, a następnie w nawiasach okrągłych jej argumenty:

int tab[] – tablica, na której będziemy wykonywać operacje int IndeksPoczatkowy, int IndeksKoncowy

int PodzielTablice(int tab[], int IndeksPoczatkowy, int IndeksKoncowy)
{ }

Deklarujemy zmienną int pivot równą liczbie zapisanej pod indeksem końcowym w tablicy tab[].

int PodzielTablice(int tab[], int IndeksPoczatkowy, int IndeksKoncowy)
{
	int pivot = tab[IndeksKoncowy];
}

Deklarujemy zmienną int IndeksMniejszegoElementu równą IndeksPoczatkowy - 1.

int PodzielTablice(int tab[], int IndeksPoczatkowy, int IndeksKoncowy)
{
	int pivot = tab[IndeksKoncowy];
    
	int IndeksMniejszegoElementu = IndeksPoczatkowy - 1;
}

Tworzymy pętlę for wykonującą się o jeden raz mniej, niż wynosi różnica indeksów: końcowy minus początkowy.

int PodzielTablice(int tab[], int IndeksPoczatkowy, int IndeksKoncowy)
{
	int pivot = tab[IndeksKoncowy];

	int IndeksMniejszegoElementu = IndeksPoczatkowy - 1;

	for (int j = IndeksPoczatkowy; j < IndeksKoncowy; j++)
	{
		
	}
}

W pętli sprawdzamy warunek, czy aktualnie badana liczba jest mniejsza od liczby pivot.

int PodzielTablice(int tab[], int IndeksPoczatkowy, int IndeksKoncowy)
{
	int pivot = tab[IndeksKoncowy];

	int IndeksMniejszegoElementu = IndeksPoczatkowy - 1;

	for (int j = IndeksPoczatkowy; j < IndeksKoncowy; j++)
	{
		if (tab[j] < pivot)
		{
			
		}
	}
}

Jeśli tak jest, zwiększamy IndeksMniejszegoElementu o jeden oraz zamieniamy miejscami liczby pod indeksami o wartościach IndeksuMniejszegoElementu oraz obecnie sprawdzanego elementu, czyli j.

int PodzielTablice(int tab[], int IndeksPoczatkowy, int IndeksKoncowy)
{
	int pivot = tab[IndeksKoncowy];

	int IndeksMniejszegoElementu = IndeksPoczatkowy - 1;

	for (int j = IndeksPoczatkowy; j < IndeksKoncowy; j++)
	{
		if (tab[j] < pivot)
		{
			IndeksMniejszegoElementu++;
			swap(tab[IndeksMniejszegoElementu], tab[j]);
		}
	}
}

Po wyjściu z pętli zamieniamy miejscami elementy o indeksach IndeksMniejszegoElementu + 1 oraz IndeksKoncowy (czyli liczbę pivot).

int PodzielTablice(int tab[], int IndeksPoczatkowy, int IndeksKoncowy)
{
	int pivot = tab[IndeksKoncowy];

	int IndeksMniejszegoElementu = IndeksPoczatkowy - 1;

	for (int j = IndeksPoczatkowy; j < IndeksKoncowy; j++)
	{
		if (tab[j] < pivot)
		{
			IndeksMniejszegoElementu++;
			swap(tab[IndeksMniejszegoElementu], tab[j]);
		}
	}
	swap(tab[IndeksMniejszegoElementu + 1], tab[IndeksKoncowy]);
}

Ważne!

Zamiast zastosowania funkcji swap(), która zamienia wartości dwóch obiektów będących argumentami, można to zrealizować z wykorzystaniem zmiennej pomocniczej. Warto o tym pamiętać, ponieważ często na egzaminie maturalnym korzystanie z takich funkcji jest zakazane.

Spróbuj wprowadzić w kodzie poprawkę tak, by funkcja była zbędna.

Na końcu zwracamy IndeksMniejszegoElementu + 1

Po poprawnym wykonaniu przedstawionych kroków uzyskujemy następujący kod:

int PodzielTablice(int tab[], int IndeksPoczatkowy, int IndeksKoncowy)
{
	int pivot = tab[IndeksKoncowy];

	int IndeksMniejszegoElementu = IndeksPoczatkowy - 1;

	for (int j = IndeksPoczatkowy; j < IndeksKoncowy; j++)
	{
		if (tab[j] < pivot)
		{
			IndeksMniejszegoElementu++;
			swap(tab[IndeksMniejszegoElementu], tab[j]);
		}
	}
	swap(tab[IndeksMniejszegoElementu + 1], tab[IndeksKoncowy]);

	return IndeksMniejszegoElementu + 1;
}

Zapoznajmy się całym kodem programu, który ma posortować niemalejąco tablicę danych tab zawierającą n liczb naturalnych.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba elementów tablicy tab
tab – n-elementowa tablica liczb naturalnych

Wynik:

tab – n-elementowa tablica liczb naturalnych posortowana niemalejąco

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. int PodzielTablice otwórz nawias okrągły int tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int IndeksPoczatkowy przecinek int IndeksKoncowy zamknij nawias okrągły. Linia 6. otwórz nawias klamrowy. Linia 7. int pivot znak równości tab otwórz nawias kwadratowy IndeksKoncowy zamknij nawias kwadratowy średnik. Linia 9. int IndeksMniejszegoElementu znak równości IndeksPoczatkowy minus 1 średnik. Linia 11. for otwórz nawias okrągły int j znak równości IndeksPoczatkowy średnik j otwórz nawias ostrokątny IndeksKoncowy średnik j plus plus zamknij nawias okrągły. Linia 12. otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły tab otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias ostrokątny pivot zamknij nawias okrągły. Linia 14. otwórz nawias klamrowy. Linia 15. IndeksMniejszegoElementu plus plus średnik. Linia 16. swap otwórz nawias okrągły tab otwórz nawias kwadratowy IndeksMniejszegoElementu zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 17. zamknij nawias klamrowy. Linia 18. zamknij nawias klamrowy. Linia 19. swap otwórz nawias okrągły tab otwórz nawias kwadratowy IndeksMniejszegoElementu plus 1 zamknij nawias kwadratowy przecinek tab otwórz nawias kwadratowy IndeksKoncowy zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 21. return IndeksMniejszegoElementu plus 1 średnik. Linia 22. zamknij nawias klamrowy. Linia 25. void quicksort otwórz nawias okrągły int tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int IndeksPoczatkowy przecinek int IndeksKoncowy zamknij nawias okrągły. Linia 26. otwórz nawias klamrowy. Linia 28. if otwórz nawias okrągły IndeksPoczatkowy otwórz nawias ostrokątny IndeksKoncowy zamknij nawias okrągły. Linia 29. otwórz nawias klamrowy. Linia 30. int a znak równości PodzielTablice otwórz nawias okrągły tab przecinek IndeksPoczatkowy przecinek IndeksKoncowy zamknij nawias okrągły średnik. Linia 32. quicksort otwórz nawias okrągły tab przecinek IndeksPoczatkowy przecinek a minus 1 zamknij nawias okrągły średnik. Linia 33. quicksort otwórz nawias okrągły tab przecinek a plus 1 przecinek IndeksKoncowy zamknij nawias okrągły średnik. Linia 34. zamknij nawias klamrowy. Linia 35. zamknij nawias klamrowy. Linia 37. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 38. otwórz nawias klamrowy. Linia 39. int tab otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 27 przecinek 5 przecinek 2023 przecinek 15 przecinek 1 przecinek 1994 przecinek 9 przecinek 12 przecinek 1987 zamknij nawias klamrowy średnik. Linia 40. int n znak równości sizeof otwórz nawias okrągły tab zamknij nawias okrągły prawy ukośnik sizeof otwórz nawias okrągły tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 41. quicksort otwórz nawias okrągły tab przecinek 0 przecinek n minus 1 zamknij nawias okrągły średnik. Linia 43. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły. Linia 44. cout otwórz nawias ostrokątny otwórz nawias ostrokątny tab otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 46. return 0 średnik. Linia 47. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

int PodzielTablice(int tab[], int IndeksPoczatkowy, int IndeksKoncowy)
{
	int pivot = tab[IndeksKoncowy];

	int IndeksMniejszegoElementu = IndeksPoczatkowy - 1;

	for (int j = IndeksPoczatkowy; j < IndeksKoncowy; j++)
	{
		if (tab[j] < pivot)
		{
			IndeksMniejszegoElementu++;
			swap(tab[IndeksMniejszegoElementu], tab[j]);
		}
	}
	swap(tab[IndeksMniejszegoElementu + 1], tab[IndeksKoncowy]);

	return IndeksMniejszegoElementu + 1;
}


void quicksort(int tab[],int IndeksPoczatkowy, int IndeksKoncowy)
{

	if (IndeksPoczatkowy < IndeksKoncowy)
	{
		int a = PodzielTablice(tab, IndeksPoczatkowy, IndeksKoncowy);

		quicksort(tab, IndeksPoczatkowy, a - 1);
		quicksort(tab, a + 1, IndeksKoncowy);
	}
}

int main()
{
	int tab[] = {27, 5, 2023, 15, 1, 1994, 9, 12, 1987};
    int n = sizeof(tab)/sizeof(tab[0]);
	quicksort(tab,0,n - 1);

	for (int i = 0; i < n; i++)
		cout << tab[i] << " ";

	return 0;
}

Słownik

pivot

element osiowy – element tablicy wybrany wedle ustalonego schematu; jest to element odpowiadający za sposób dzielenia tablicy

rekurencja

proces polegający na wywoływaniu funkcji przez siebie samą do momentu rozwiązania określonego problemu

wywołanie rekurencyjne

sytuacja, w której funkcja wywołuje samą siebie

zasada „dziel i zwyciężaj”

zasada często stosowana przez programistów przy tworzeniu algorytmów opartych o rekurencję, polegająca na tym, że jeden trudny, złożony problem dzielony jest na kilka mniejszych, prostszych do rozwiązania

złożoność czasowa

ilość czasu potrzebnego do wykonania zadania, wyrażona jako funkcja ilości danych

złożoność obliczeniowa

złożoność czasowa i złożoność pamięciowa; ilość zasobów komputerowych potrzebnych do wykonania zadania

Film samouczek

Sprawdź się

Algorytm sortowania szybkiego – implementacja w języku C++

Słownik