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:
Linia 1. minus 8 100.
-8 100
R15OHUkyCqL0a1
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
Wybierz jedno nowe słowo poznane podczas dzisiejszej lekcji i ułóż z nim zdanie.
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;
}
21
Ćwiczenie 2
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:
Linia 1. y q o l f e b a.
y q o l f e b a
R1ZTv2R9ybARM1
Wymyśl pytanie na kartkówkę związane z tematem materiału.
Wymyśl pytanie na kartkówkę związane z tematem materiału.
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;
}
31
Ćwiczenie 3
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. Aby wyznaczyć medianę jakiegoś zbioru liczb, musimy najpierw wypisać te liczby w kolejności niemalejącej, a następnie wybrać liczbę środkową (w przypadku, gdy mamy nieparzystą liczbę liczb w zbiorze). Jeśli mamy parzystą liczbę liczb w zbiorze, to mediana jest równa średniej arytmetycznej dwóch środkowych liczb.
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[]