Strefa wyzwań - I_R_W14_M27_C++ Metoda Quicksort

R13XFHOJPLQJ3

Już wiesz

jak przeanalizować pseudokod, który jest zapisem algorytmu sortowania szybkiego,
jaki jest czas działania algorytmu quick sort, w tym dla przypadku optymistycznego i pesymistycznego,
jak zastosować algorytm sortowania przykładowej tablicy za pomocą algorytmu quick sort,
jak zaimplementować algorytm quick sort w języku C++.

Ćwiczenie 1

R1NZUD5D443ND

Ćwiczenie 2

RQLF5LNME6KVO

Ćwiczenie 3

RM313ATL6E4AK

Ćwiczenie 4

Napisz program, który wykorzystując algorytm sortowania szybkiego, wypisze wartość minimalną oraz maksymalną z podanej tablicy. Przetestuj działanie programu dla tablicy tab[] = {9, 11, 0, -8, 11, 5, 20, 45, 0, 100}.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba elementów tablicy tab[]
tab[] – n-elementowa tablica liczb całkowitych

Wynik:

minimum i maksimum dla tablicy tab[]; liczby całkowite

Przykładowe wyjście:

-8 100

R15OHUkyCqL0a1

Przykładowe rozwiązanie zadania:

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 piwot 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 piwot 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 36. zamknij nawias klamrowy. Linia 39. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 40. otwórz nawias klamrowy. Linia 41. int tab otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 9 przecinek 11 przecinek 0 przecinek minus 8 przecinek 11 przecinek 5 przecinek 20 przecinek 45 przecinek 0 przecinek 100 zamknij nawias klamrowy średnik. Linia 42. 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 43. quicksort otwórz nawias okrągły tab przecinek 0 przecinek n minus 1 zamknij nawias okrągły średnik. Linia 45. cout otwórz nawias ostrokątny otwórz nawias ostrokątny tab otwórz nawias kwadratowy 0 zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny tab otwórz nawias kwadratowy n minus 1 zamknij nawias kwadratowy średnik. Linia 47. return 0 średnik. Linia 48. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

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

	int IndeksMniejszegoElementu = IndeksPoczatkowy - 1;

	for (int j = IndeksPoczatkowy; j < IndeksKoncowy; j++)
	{
		if (tab[j] < piwot)
		{
			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[] = {9, 11, 0, -8, 11, 5, 20, 45, 0, 100};
    int n = sizeof(tab)/sizeof(tab[0]);
	quicksort(tab,0,n - 1);

	cout << tab[0] << " "<<tab[n - 1];

	return 0;
}

Ćwiczenie 5

Napisz program, który przy użyciu algorytmu sortowania szybkiego uporządkuje zbiór podanych liter alfabetu łacińskiego w kolejności odwrotnej do alfabetycznej. Przetestuj działanie programu dla następującego zbioru liter tab[] = {a, f, e, o, b, l, q, y}.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba elementów tablicy tab[]
tab[] – n-elementowa tablica zawierająca małe litery alfabetu łacińskiego

Wynik:

tab[] – tablica znaków posortowana w kolejności odwrotnej do kolejności alfabetycznej; elementy oddzielone są pojedynczym znakiem spacji

Przykładowe wyjście:

y q o l f e b a

R1ZTv2R9ybARM1

Przykładowe rozwiązanie zadania:

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 char 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 piwot znak równości otwórz nawias okrągły int zamknij nawias okrągły 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 otwórz nawias okrągły int zamknij nawias okrągły tab otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias ostrokątny piwot 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 char 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 36. zamknij nawias klamrowy. Linia 38. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 39. otwórz nawias klamrowy. Linia 40. char tab otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy apostrof a apostrof przecinek apostrof f apostrof przecinek apostrof e apostrof przecinek apostrof o apostrof przecinek apostrof b apostrof przecinek apostrof l apostrof przecinek apostrof q apostrof przecinek apostrof y apostrof zamknij nawias klamrowy średnik. Linia 41. 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 42. quicksort otwórz nawias okrągły tab przecinek 0 przecinek n minus 1 zamknij nawias okrągły średnik. Linia 44. 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 45. 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 47. return 0 średnik. Linia 48. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

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

	int IndeksMniejszegoElementu = IndeksPoczatkowy - 1;

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

	return IndeksMniejszegoElementu + 1;
}


void quicksort(char 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()
{
	char tab[] = { 'a', 'f', 'e', 'o', 'b', 'l', 'q', 'y'};
    int n = sizeof(tab)/sizeof(tab[0]);
	quicksort(tab,0,n - 1);

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

	return 0;
}

Ćwiczenie 6

W ramach badania zapytano grupę respondentów o zarobki. Odpowiedzi umieszczono w tablicy. Użyj algorytmu sortowania szybkiego, aby znaleźć medianę zarobków w tej grupie. Program powinien wydrukować wynik na standardowe wyjście.

Ważne!

Mediana to wartość środkowa w uporządkowanym zbiorze danych, dzieląca go na dwie części. W przypadku, gdy liczba obserwacji jest nieparzysta, mediana to środkowa wartość. Natomiast w zbiorach o parzystej liczbie elementów, mediana obliczana jest jako średnia arytmetyczna dwóch środkowych wartości. Dzięki tym właściwościom, mediana jest niezwykle przydatna w różnych analizach statystycznych.

Przetestuj jego działanie dla tablicy zarobki[] = {8500.57, 6400.32, 2800.56, 3500.12, 12870.67, 3300.45, 7020.0, 3000.01, 8100.29}.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba elementów tablicy zarobki[]
zarobki[] – n-elementowa tablica liczb rzeczywistych

Wynik:

mediana posortowanej tablicy zarobki[]; liczba rzeczywista

Przykładowe wyjście

6400.32

RJ21vxXX4CCph

Przykładowe rozwiązanie zadania:

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 double 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 piwot 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 piwot 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 double 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 36. zamknij nawias klamrowy. Linia 38. int main otwórz nawias okrągły zamknij nawias okrągły. Linia 39. otwórz nawias klamrowy. Linia 40. double zarobki otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 8500 kropka 57 przecinek 6400 kropka 32 przecinek 2800 kropka 56 przecinek 3500 kropka 12 przecinek 12870 kropka 67 przecinek 3300 kropka 45 przecinek 7020 kropka 0 przecinek 3000 kropka 01 przecinek 8100 kropka 29 zamknij nawias klamrowy średnik. Linia 41. int n znak równości sizeof otwórz nawias okrągły zarobki zamknij nawias okrągły prawy ukośnik sizeof otwórz nawias okrągły zarobki otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 42. quicksort otwórz nawias okrągły zarobki przecinek 0 przecinek n minus 1 zamknij nawias okrągły średnik. Linia 44. cout otwórz nawias ostrokątny otwórz nawias ostrokątny zarobki otwórz nawias kwadratowy n prawy ukośnik 2 zamknij nawias kwadratowy otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 46. return 0 średnik. Linia 47. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

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

	int IndeksMniejszegoElementu = IndeksPoczatkowy - 1;

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

	return IndeksMniejszegoElementu + 1;
}


void quicksort(double 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()
{
    double zarobki[] = {8500.57, 6400.32, 2800.56, 3500.12, 12870.67, 3300.45, 7020.0, 3000.01, 8100.29};
    int n = sizeof(zarobki)/sizeof(zarobki[0]);
    quicksort(zarobki, 0, n - 1);

    cout << zarobki[n / 2] << endl;

    return 0;
}

Implementacja algorytmu podziału w C++

I_R_W14_M27_C++ Metoda Quicksort