Strefa wyzwań - I_R_W14_M27_Java 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 Java.

Ćwiczenie 1

R1R1S1ECZ9M27

Ćwiczenie 2

R1VXOFXS4A6Q3

Ćwiczenie 3

RHEBTZT63CHEO

Ćwiczenie 4

Napisz program, który za pomocą algorytmu sortowania szybkiego posortuje n-elementowy zbiór znaków zbior. Swoje rozwiązanie sprawdź dla zadanego zbioru: zbior = ['a', 'f', 'z', 'b', 'd', 't'] oraz n = 6.

Specyfikacja:

Dane:

n – liczba naturalna, liczba elementów w zbiorze zbior
zbior[] – n-elementowy zbiór znaków, małe litery alfabetu łacińskiego

Wynik:

Program wyświetla najpierw nieposortowane elementy zbioru (oddzielone spacją), a następnie (w nowej linii) elementy zbioru posortowane alfabetycznie.

RrpQcprWfyMqh

Twoje zadanie: Program ma wypisać elementy nieposortowanego zbioru zbior (kolejne elementy oddzielone spacją), a następnie w nowej linii elementy zbioru zbior po sortowaniu (kolejne elementy oddzielone spacją).

Linia 1. public class SortowanieSzybkie otwórz nawias klamrowy. Linia 2. static void sortuj otwórz nawias okrągły char tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int p przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. prawy ukośnik prawy ukośnik tu dodaj swoje rozwiązanie. Linia 4. zamknij nawias klamrowy. Linia 6. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. 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 z apostrof przecinek apostrof b apostrof przecinek apostrof d apostrof przecinek apostrof t apostrof zamknij nawias klamrowy średnik. Linia 8. int n znak równości 6 średnik. Linia 10. 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 otwórz nawias klamrowy. Linia 11. System kropka out kropka print otwórz nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 12. zamknij nawias klamrowy. Linia 13. System kropka out kropka println otwórz nawias okrągły cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 15. sortuj otwórz nawias okrągły tab przecinek 0 przecinek n minus 1 zamknij nawias okrągły średnik. Linia 17. 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 otwórz nawias klamrowy. Linia 18. System kropka out kropka print otwórz nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 19. zamknij nawias klamrowy. Linia 20. zamknij nawias klamrowy. Linia 21. zamknij nawias klamrowy. Linia 22. at at at. Linia 23. language znak równości java11. Linia 24. at at at. Linia 25. Program ma wypisać elementy nieposortowanego zbioru otwórz nawias ostrokątny code zamknij nawias ostrokątny zbior otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny otwórz nawias okrągły kolejne elementy oddzielone spacją zamknij nawias okrągły przecinek a następnie w nowej linii elementy zbioru otwórz nawias ostrokątny code zamknij nawias ostrokątny zbior otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny po sortowaniu otwórz nawias okrągły kolejne elementy oddzielone spacją zamknij nawias okrągły kropka. Linia 26. at at at. Linia 27. at at at. Linia 28. at at at. Linia 29. kratka wykrzyknik prawy ukośnik usr prawy ukośnik bin prawy ukośnik python3 kropka 7. Linia 30. import sys. Linia 32. podkreślnik podkreślnik TF znak równości open otwórz nawias okrągły 3 przecinek apostrof w apostrof zamknij nawias okrągły. Linia 35. def podkreślnik pt otwórz nawias okrągły t zamknij nawias okrągły dwukropek. Linia 36. print otwórz nawias okrągły str otwórz nawias okrągły t zamknij nawias okrągły przecinek file znak równości podkreślnik podkreślnik TF zamknij nawias okrągły. Linia 39. expected podkreślnik output znak równości cudzysłów cudzysłów cudzysłów. Linia 40. a f z b d t. Linia 41. a b d f t z. Linia 42. cudzysłów cudzysłów cudzysłów. Linia 43. input znak równości sys kropka stdin kropka read otwórz nawias okrągły zamknij nawias okrągły kropka strip otwórz nawias okrągły zamknij nawias okrągły. Linia 44. if input znak równości znak równości expected podkreślnik output kropka strip otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 45. podkreślnik pt otwórz nawias okrągły 0 zamknij nawias okrągły.

public class SortowanieSzybkie {
	static void sortuj(char tab[], int p, int k) {
		//tu dodaj swoje rozwiązanie
	}
    
	public static void main(String[] args) {
		char tab[] = {'a', 'f', 'z', 'b', 'd', 't'};
        int n = 6;
		
		for (int i = 0; i < n; i++) {
			System.out.print(tab[i] + "  ");
		}
        System.out.println("");
		
		sortuj(tab, 0, n - 1);
		
		for (int i = 0; i < n; i++) {
			System.out.print(tab[i] + "  ");
		}
	}
}
@@@
language=java11
@@@
Program ma wypisać elementy nieposortowanego zbioru <code>zbior</code> (kolejne elementy oddzielone spacją), a następnie w nowej linii elementy zbioru <code>zbior</code> po sortowaniu (kolejne elementy oddzielone spacją).
@@@
@@@
@@@
#!/usr/bin/python3.7
import sys

__TF = open(3, 'w')


def _pt(t):
    print(str(t), file=__TF)


expected_output = """
a  f  z  b  d  t  
a  b  d  f  t  z  
"""
input = sys.stdin.read().strip()
if input == expected_output.strip():
    _pt(0)

Przykładowe rozwiązanie zadania:

Linia 1. public class SortowanieSzybkie otwórz nawias klamrowy. Linia 3. static void sortuj otwórz nawias okrągły char tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int p przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. if otwórz nawias okrągły p otwórz nawias ostrokątny k zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. int q znak równości podzialTablicy otwórz nawias okrągły tab przecinek p przecinek k zamknij nawias okrągły średnik. Linia 6. sortuj otwórz nawias okrągły tab przecinek p przecinek q zamknij nawias okrągły średnik. Linia 7. sortuj otwórz nawias okrągły tab przecinek q plus 1 przecinek k zamknij nawias okrągły średnik. Linia 8. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. static int podzialTablicy otwórz nawias okrągły char tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int p przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. int pivot znak równości tab otwórz nawias kwadratowy k zamknij nawias kwadratowy średnik. Linia 13. int i znak równości p minus 1 średnik. Linia 14. int j znak równości k plus 1 średnik. Linia 16. while otwórz nawias okrągły true zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. do otwórz nawias klamrowy. Linia 18. i plus plus średnik. Linia 19. zamknij nawias klamrowy while otwórz nawias okrągły i otwórz nawias ostrokątny znak równości k ampersant ampersant tab otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny pivot zamknij nawias okrągły średnik. Linia 21. do otwórz nawias klamrowy. Linia 22. j minus minus średnik. Linia 23. zamknij nawias klamrowy while otwórz nawias okrągły j zamknij nawias ostrokątny znak równości p ampersant ampersant tab otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias ostrokątny pivot zamknij nawias okrągły średnik. Linia 25. if otwórz nawias okrągły i otwórz nawias ostrokątny znak równości j zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. char temp znak równości tab otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 27. tab otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 28. tab otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości temp średnik. Linia 29. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 30. return j średnik. Linia 31. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy. Linia 33. zamknij nawias klamrowy. Linia 35. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. 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 z apostrof przecinek apostrof b apostrof przecinek apostrof d apostrof przecinek apostrof t apostrof zamknij nawias klamrowy średnik. Linia 37. int n znak równości 6 średnik. Linia 39. 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 otwórz nawias klamrowy. Linia 40. System kropka out kropka print otwórz nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 41. zamknij nawias klamrowy. Linia 43. System kropka out kropka println otwórz nawias okrągły cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 45. sortuj otwórz nawias okrągły tab przecinek 0 przecinek n minus 1 zamknij nawias okrągły średnik. Linia 47. 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 otwórz nawias klamrowy. Linia 48. System kropka out kropka print otwórz nawias okrągły tab otwórz nawias kwadratowy i zamknij nawias kwadratowy plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 49. zamknij nawias klamrowy. Linia 50. zamknij nawias klamrowy. Linia 51. zamknij nawias klamrowy.

public class SortowanieSzybkie {
	
	static void sortuj(char tab[], int p, int k) {
		if (p < k) {
			int q = podzialTablicy(tab, p, k);
			sortuj(tab, p, q);
			sortuj(tab, q + 1, k);
		}
	}
	
	static int podzialTablicy(char tab[], int p, int k) {
		int pivot = tab[k];
		int i = p - 1;
		int j = k + 1;
		 
		while (true) {
			do {
				i++;
			} while (i <= k && tab[i] < pivot);
			 
			do {
				j--;
			} while (j >= p && tab[j] > pivot);
			 
			if (i <= j) {
				char temp = tab[j];
				tab[j] = tab[i];
				tab[i] = temp;
			} else {
				return j;
			}
		}
	}

	public static void main(String[] args) {
		char tab[] = {'a', 'f', 'z', 'b', 'd', 't'};
		int n = 6;
		
		for(int i = 0; i < n; i++) {
			System.out.print(tab[i] + "  ");
		}
		
		System.out.println("");
		
		sortuj(tab, 0, n - 1);
		
		for(int i = 0; i < n; i++) {
			System.out.print(tab[i] + "  ");
		}
	}
}

Ćwiczenie 5

Przedstawiony kod jest implementacją algorytmu sortowania szybkiego w języku Java. Dla trzech zadanych n-elementowych tablic tab1, tab2, tab3 napisz kod odpowiadający za obliczenie głębokości drzewa wywołań rekurencyjnych funkcji sortuj(). Program na standardowe wyjście ma wypisać trzy głębokości drzew wywołań funkcji sortuj(), przy sortowaniu tablic tab1, tab2, tab3, każda wartość w nowej linii. Swój program przetestuj dla n = 16 i trzech tablic:

tablica z losowym rozkładem elementów tab1 = {12, 1, 3, 15, 14, 2, 11, 4, 6, 5, 13, 10, 7, 9, 16, 8}
tablica posortowana rosnąco tab2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
tablica posortowana malejąco tab3 = {16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}

Specyfikacja:

Dane:

n – liczba naturalna, liczba elementów w tablicach tab1, tab2 i tab3
tab1[], tab2[], tab3[] – tablice liczb naturalnych

Wynik:

Program na standardowym wyjściu wypisuje trzy głębokości drzew wywołań rekurencyjnych funkcji sortuj(), przy sortowaniu trzech n-elementowych tablic tab1, tab2, tab3.

R1XIdUmr4ZqRp

Twoje zadanie: Program wypisuje trzy głębokości drzew wywołań rekurencyjnych funkcji sortuj() uzyskane w trakcie sortowania trzech n‑elementowych tablic tab1, tab2, tab3.

Linia 1. public class SortowanieSzybkie otwórz nawias klamrowy. Linia 3. static int sortuj otwórz nawias okrągły int tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int p przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. if otwórz nawias okrągły p otwórz nawias ostrokątny k zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. int q znak równości podzialTablicy otwórz nawias okrągły tab przecinek p przecinek k zamknij nawias okrągły średnik. Linia 6. sortuj otwórz nawias okrągły tab przecinek p przecinek q zamknij nawias okrągły średnik. Linia 7. sortuj otwórz nawias okrągły tab przecinek q plus 1 przecinek k zamknij nawias okrągły średnik. Linia 8. zamknij nawias klamrowy. Linia 10. return 0 średnik. Linia 11. zamknij nawias klamrowy. Linia 13. static int podzialTablicy otwórz nawias okrągły int tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int p przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. int pivot znak równości tab otwórz nawias kwadratowy k zamknij nawias kwadratowy średnik. Linia 15. int i znak równości p minus 1 średnik. Linia 16. int j znak równości k plus 1 średnik. Linia 18. while otwórz nawias okrągły true zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. do otwórz nawias klamrowy. Linia 20. i plus plus średnik. Linia 21. zamknij nawias klamrowy while otwórz nawias okrągły i otwórz nawias ostrokątny znak równości k ampersant ampersant tab otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny pivot zamknij nawias okrągły średnik. Linia 23. do otwórz nawias klamrowy. Linia 24. j minus minus średnik. Linia 25. zamknij nawias klamrowy while otwórz nawias okrągły j zamknij nawias ostrokątny znak równości p ampersant ampersant tab otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias ostrokątny pivot zamknij nawias okrągły średnik. Linia 27. if otwórz nawias okrągły i otwórz nawias ostrokątny znak równości j zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. int temp znak równości tab otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 29. tab otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 30. tab otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości temp średnik. Linia 31. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 32. return j średnik. Linia 33. zamknij nawias klamrowy. Linia 34. zamknij nawias klamrowy. Linia 35. zamknij nawias klamrowy. Linia 37. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. int tab1 otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 12 przecinek 1 przecinek 3 przecinek 15 przecinek 14 przecinek 2 przecinek 11 przecinek 4 przecinek 6 przecinek 5 przecinek 13 przecinek 10 przecinek 7 przecinek 9 przecinek 16 przecinek 8 zamknij nawias klamrowy średnik. Linia 39. int tab2 otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 6 przecinek 7 przecinek 8 przecinek 9 przecinek 10 przecinek 11 przecinek 12 przecinek 13 przecinek 14 przecinek 15 przecinek 16 zamknij nawias klamrowy średnik. Linia 40. int tab3 otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 16 przecinek 15 przecinek 14 przecinek 13 przecinek 12 przecinek 11 przecinek 10 przecinek 9 przecinek 8 przecinek 7 przecinek 6 przecinek 5 przecinek 4 przecinek 3 przecinek 2 przecinek 1 zamknij nawias klamrowy średnik. Linia 41. int n znak równości 16 średnik. Linia 42. sortuj otwórz nawias okrągły tab1 przecinek 0 przecinek n minus 1 zamknij nawias okrągły średnik. Linia 43. sortuj otwórz nawias okrągły tab2 przecinek 0 przecinek n minus 1 zamknij nawias okrągły średnik. Linia 44. sortuj otwórz nawias okrągły tab3 przecinek 0 przecinek n minus 1 zamknij nawias okrągły średnik. Linia 45. zamknij nawias klamrowy. Linia 46. zamknij nawias klamrowy. Linia 47. at at at. Linia 48. language znak równości java11. Linia 49. at at at. Linia 50. Program wypisuje trzy głębokości drzew wywołań rekurencyjnych funkcji otwórz nawias ostrokątny code zamknij nawias ostrokątny sortuj otwórz nawias okrągły zamknij nawias okrągły otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny uzyskane w trakcie sortowania trzech otwórz nawias ostrokątny code zamknij nawias ostrokątny n otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny minus elementowych tablic otwórz nawias ostrokątny code zamknij nawias ostrokątny tab1 otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny przecinek otwórz nawias ostrokątny code zamknij nawias ostrokątny tab2 otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny przecinek otwórz nawias ostrokątny code zamknij nawias ostrokątny tab3 otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 51. at at at. Linia 52. at at at. Linia 53. at at at. Linia 54. kratka wykrzyknik prawy ukośnik usr prawy ukośnik bin prawy ukośnik python3 kropka 7. Linia 55. import sys. Linia 57. podkreślnik podkreślnik TF znak równości open otwórz nawias okrągły 3 przecinek apostrof w apostrof zamknij nawias okrągły. Linia 60. def podkreślnik pt otwórz nawias okrągły t zamknij nawias okrągły dwukropek. Linia 61. print otwórz nawias okrągły str otwórz nawias okrągły t zamknij nawias okrągły przecinek file znak równości podkreślnik podkreślnik TF zamknij nawias okrągły. Linia 64. expected podkreślnik output znak równości cudzysłów cudzysłów cudzysłów. Linia 65. 6. Linia 66. 16. Linia 67. 16. Linia 68. cudzysłów cudzysłów cudzysłów. Linia 69. input znak równości sys kropka stdin kropka read otwórz nawias okrągły zamknij nawias okrągły kropka strip otwórz nawias okrągły zamknij nawias okrągły. Linia 70. if input znak równości znak równości expected podkreślnik output kropka strip otwórz nawias okrągły zamknij nawias okrągły dwukropek. Linia 71. podkreślnik pt otwórz nawias okrągły 0 zamknij nawias okrągły.

public class SortowanieSzybkie {
	
	static int sortuj(int tab[], int p, int k) {
		if (p < k) {
			int q = podzialTablicy(tab, p, k);
			sortuj(tab, p, q);
			sortuj(tab, q + 1, k);
		}

		return 0;
	}
	
	static int podzialTablicy(int tab[], int p, int k) {
		 int pivot = tab[k];
		 int i = p - 1;
		 int j = k + 1;
		 
		 while (true) {
			 do {
				 i++;
			 } while (i <= k && tab[i] < pivot);
			 
			 do {
				 j--;
			 } while (j >= p && tab[j] > pivot);
			 
			 if (i <= j) {
				 int temp = tab[j];
				 tab[j] = tab[i];
				 tab[i] = temp;
			 } else {
				 return j;
			 }
		 }
	}

	public static void main(String[] args) {
		int tab1[] = {12, 1, 3, 15, 14, 2, 11, 4, 6, 5, 13, 10, 7, 9, 16, 8};
		int tab2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
		int tab3[] = {16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
		int n = 16;
		sortuj(tab1, 0, n - 1);
		sortuj(tab2, 0, n - 1);
		sortuj(tab3, 0, n - 1);
	}
}
@@@
language=java11
@@@
Program wypisuje trzy głębokości drzew wywołań rekurencyjnych funkcji <code>sortuj()</code> uzyskane w trakcie sortowania trzech <code>n</code>-elementowych tablic <code>tab1</code>, <code>tab2</code>, <code>tab3</code>
@@@
@@@
@@@
#!/usr/bin/python3.7
import sys

__TF = open(3, 'w')


def _pt(t):
    print(str(t), file=__TF)


expected_output = """
6
16
16
"""
input = sys.stdin.read().strip()
if input == expected_output.strip():
    _pt(0)

Przykładowe rozwiązanie zadania:

Linia 1. public class SortowanieSzybkie otwórz nawias klamrowy. Linia 3. static int aktualnaGlebokosc znak równości 0 średnik. Linia 4. static int najwiekszaGlebokosc znak równości 0 średnik. Linia 6. static int sortuj otwórz nawias okrągły int tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int p przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. aktualnaGlebokosc plus plus średnik. Linia 10. if otwórz nawias okrągły p otwórz nawias ostrokątny k zamknij nawias okrągły otwórz nawias klamrowy. Linia 11. int q znak równości podzialTablicy otwórz nawias okrągły tab przecinek p przecinek k zamknij nawias okrągły średnik. Linia 12. sortuj otwórz nawias okrągły tab przecinek p przecinek q zamknij nawias okrągły średnik. Linia 13. if otwórz nawias okrągły aktualnaGlebokosc zamknij nawias ostrokątny najwiekszaGlebokosc zamknij nawias okrągły najwiekszaGlebokosc znak równości aktualnaGlebokosc średnik. Linia 14. aktualnaGlebokosc minus minus średnik. Linia 15. sortuj otwórz nawias okrągły tab przecinek q plus 1 przecinek k zamknij nawias okrągły średnik. Linia 16. if otwórz nawias okrągły aktualnaGlebokosc zamknij nawias ostrokątny najwiekszaGlebokosc zamknij nawias okrągły najwiekszaGlebokosc znak równości aktualnaGlebokosc średnik. Linia 17. aktualnaGlebokosc minus minus średnik. Linia 18. zamknij nawias klamrowy. Linia 20. return najwiekszaGlebokosc średnik. Linia 21. zamknij nawias klamrowy. Linia 23. static int podzialTablicy otwórz nawias okrągły int tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int p przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. int pivot znak równości tab otwórz nawias kwadratowy k zamknij nawias kwadratowy średnik. Linia 25. int i znak równości p minus 1 średnik. Linia 26. int j znak równości k plus 1 średnik. Linia 28. while otwórz nawias okrągły true zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. do otwórz nawias klamrowy. Linia 30. i plus plus średnik. Linia 31. zamknij nawias klamrowy while otwórz nawias okrągły i otwórz nawias ostrokątny znak równości k ampersant ampersant tab otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny pivot zamknij nawias okrągły średnik. Linia 33. do otwórz nawias klamrowy. Linia 34. j minus minus średnik. Linia 35. zamknij nawias klamrowy while otwórz nawias okrągły j zamknij nawias ostrokątny znak równości p ampersant ampersant tab otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias ostrokątny pivot zamknij nawias okrągły średnik. Linia 37. if otwórz nawias okrągły i otwórz nawias ostrokątny znak równości j zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. int temp znak równości tab otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 39. tab otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 40. tab otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości temp średnik. Linia 41. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 42. return j średnik. Linia 43. zamknij nawias klamrowy. Linia 44. zamknij nawias klamrowy. Linia 45. zamknij nawias klamrowy. Linia 48. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 49. int tab1 otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 12 przecinek 1 przecinek 3 przecinek 15 przecinek 14 przecinek 2 przecinek 11 przecinek 4 przecinek 6 przecinek 5 przecinek 13 przecinek 10 przecinek 7 przecinek 9 przecinek 16 przecinek 8 zamknij nawias klamrowy średnik. Linia 50. int tab2 otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 1 przecinek 2 przecinek 3 przecinek 4 przecinek 5 przecinek 6 przecinek 7 przecinek 8 przecinek 9 przecinek 10 przecinek 11 przecinek 12 przecinek 13 przecinek 14 przecinek 15 przecinek 16 zamknij nawias klamrowy średnik. Linia 51. int tab3 otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 16 przecinek 15 przecinek 14 przecinek 13 przecinek 12 przecinek 11 przecinek 10 przecinek 9 przecinek 8 przecinek 7 przecinek 6 przecinek 5 przecinek 4 przecinek 3 przecinek 2 przecinek 1 zamknij nawias klamrowy średnik. Linia 52. int n znak równości 16 średnik. Linia 53. System kropka out kropka println otwórz nawias okrągły sortuj otwórz nawias okrągły tab1 przecinek 0 przecinek n minus 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 54. aktualnaGlebokosc znak równości 0 średnik. Linia 55. najwiekszaGlebokosc znak równości 0 średnik. Linia 56. System kropka out kropka println otwórz nawias okrągły sortuj otwórz nawias okrągły tab2 przecinek 0 przecinek n minus 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 57. aktualnaGlebokosc znak równości 0 średnik. Linia 58. najwiekszaGlebokosc znak równości 0 średnik. Linia 59. System kropka out kropka print otwórz nawias okrągły sortuj otwórz nawias okrągły tab3 przecinek 0 przecinek n minus 1 zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 60. zamknij nawias klamrowy. Linia 61. zamknij nawias klamrowy.

public class SortowanieSzybkie {

	static int aktualnaGlebokosc = 0;
	static int najwiekszaGlebokosc = 0;

	static int sortuj(int tab[], int p, int k) {

		aktualnaGlebokosc++;

		if (p < k) {
			int q = podzialTablicy(tab, p, k);
			sortuj(tab, p, q);
			if (aktualnaGlebokosc > najwiekszaGlebokosc) najwiekszaGlebokosc = aktualnaGlebokosc;
			aktualnaGlebokosc--;
			sortuj(tab, q + 1, k);
			if (aktualnaGlebokosc > najwiekszaGlebokosc) najwiekszaGlebokosc = aktualnaGlebokosc;
			aktualnaGlebokosc--;
		}
        
		return najwiekszaGlebokosc;
    }

	static int podzialTablicy(int tab[], int p, int k) {
		int pivot = tab[k];
		int i = p - 1;
		int j = k + 1;

		while (true) {
			do {
				i++;
			} while (i <= k && tab[i] < pivot);

			do {
				j--;
			} while (j >= p && tab[j] > pivot);

			if (i <= j) {
				int temp = tab[j];
				tab[j] = tab[i];
				tab[i] = temp;
			} else {
				return j;
			}
		}
	}


	public static void main(String[] args) {
		int tab1[] = {12, 1, 3, 15, 14, 2, 11, 4, 6, 5, 13, 10, 7, 9, 16, 8};
		int tab2[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
		int tab3[] = {16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
		int n = 16;
		System.out.println(sortuj(tab1, 0, n - 1));
		aktualnaGlebokosc = 0;
		najwiekszaGlebokosc = 0;
		System.out.println(sortuj(tab2, 0, n - 1));
		aktualnaGlebokosc = 0;
		najwiekszaGlebokosc = 0;
		System.out.print(sortuj(tab3, 0, n - 1));
	}
}

Ćwiczenie 6

Zapytano kilka osób o miesięczne zarobki, a ich odpowiedzi zebrano w n-elementowej tabeli zarobki. Użyj algorytmu sortowania szybkiego, aby znaleźć medianę (wartość środkową) zarobków w tej grupie.

Swoje rozwiązanie przetestuj dla następujących odpowiedzi ankietowanych: zarobki = {8500, 6400, 2800, 3500, 12870, 3300, 7020, 3000, 8100} oraz dla n = 9.

Specyfikacja:

Dane:

n – liczba naturalna, liczba ankietowanych
zarobki[] – tablica liczb naturalnych, przechowująca zarobki ankietowanych

Wynik:

Program wyświetla medianę (wartość środkowa, rzeczywista) zarobków w grupie

RTZTJJS5bNa5s

Twoje zadanie: Program powinien wyświetlić jedną liczbę – medianę wartości zbioru.

public class Main {

    public static void main(String[] args) {
        int zarobki[] = {8500, 6400, 2800, 3500, 12870, 3300, 7020, 3000, 8100};
        int n = 9;
        double mediana;

    }
}

@@@
language=java11
@@@
Program powinien wyświetlić jedną liczbę – medianę wartości zbioru.
@@@
@@@
@@@
#!/usr/bin/python3.7
import sys

__TF = open(3, 'w')


def _pt(t):
    print(str(t), file=__TF)


expected_output = """
6400.0
"""
input = sys.stdin.read().strip()
if input == expected_output.strip():
    _pt(0)

Przykładowe rozwiązanie zadania:

Linia 1. public class Main otwórz nawias klamrowy. Linia 3. static void sortuj otwórz nawias okrągły int tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int p przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 4. if otwórz nawias okrągły p otwórz nawias ostrokątny k zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. int q znak równości podzialTablicy otwórz nawias okrągły tab przecinek p przecinek k zamknij nawias okrągły średnik. Linia 6. sortuj otwórz nawias okrągły tab przecinek p przecinek q zamknij nawias okrągły średnik. Linia 7. sortuj otwórz nawias okrągły tab przecinek q plus 1 przecinek k zamknij nawias okrągły średnik. Linia 8. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. static int podzialTablicy otwórz nawias okrągły int tab otwórz nawias kwadratowy zamknij nawias kwadratowy przecinek int p przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. int pivot znak równości tab otwórz nawias kwadratowy k zamknij nawias kwadratowy średnik. Linia 13. int i znak równości p minus 1 średnik. Linia 14. int j znak równości k plus 1 średnik. Linia 16. while otwórz nawias okrągły true zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. do otwórz nawias klamrowy. Linia 18. i plus plus średnik. Linia 19. zamknij nawias klamrowy while otwórz nawias okrągły i otwórz nawias ostrokątny znak równości k ampersant ampersant tab otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny pivot zamknij nawias okrągły średnik. Linia 21. do otwórz nawias klamrowy. Linia 22. j minus minus średnik. Linia 23. zamknij nawias klamrowy while otwórz nawias okrągły j zamknij nawias ostrokątny znak równości p ampersant ampersant tab otwórz nawias kwadratowy j zamknij nawias kwadratowy zamknij nawias ostrokątny pivot zamknij nawias okrągły średnik. Linia 25. if otwórz nawias okrągły i otwórz nawias ostrokątny znak równości j zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. int temp znak równości tab otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 27. tab otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 28. tab otwórz nawias kwadratowy i zamknij nawias kwadratowy znak równości temp średnik. Linia 29. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 30. return j średnik. Linia 31. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy. Linia 33. zamknij nawias klamrowy. Linia 35. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. int zarobki otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 8500 przecinek 6400 przecinek 2800 przecinek 3500 przecinek 12870 przecinek 3300 przecinek 7020 przecinek 3000 przecinek 8100 zamknij nawias klamrowy średnik. Linia 37. int n znak równości 9 średnik. Linia 38. double mediana średnik. Linia 40. sortuj otwórz nawias okrągły zarobki przecinek 0 przecinek n minus 1 zamknij nawias okrągły średnik. Linia 42. prawy ukośnik prawy ukośnik gdy n nieparzyste. Linia 43. if otwórz nawias okrągły n procent 2 znak równości znak równości 1 zamknij nawias okrągły. Linia 44. mediana znak równości zarobki otwórz nawias kwadratowy n prawy ukośnik 2 zamknij nawias kwadratowy średnik. Linia 45. prawy ukośnik prawy ukośnik gdy n parzyste. Linia 46. else. Linia 47. mediana znak równości otwórz nawias okrągły otwórz nawias okrągły double zamknij nawias okrągły zarobki otwórz nawias kwadratowy n prawy ukośnik 2 zamknij nawias kwadratowy plus otwórz nawias okrągły double zamknij nawias okrągły zarobki otwórz nawias kwadratowy n prawy ukośnik 2 minus 1 zamknij nawias kwadratowy zamknij nawias okrągły prawy ukośnik 2 średnik. Linia 49. System kropka out kropka print otwórz nawias okrągły mediana zamknij nawias okrągły średnik. Linia 50. zamknij nawias klamrowy. Linia 51. zamknij nawias klamrowy.

public class Main {

	static void sortuj(int tab[], int p, int k) {
		if (p < k) {
			int q = podzialTablicy(tab, p, k);
			sortuj(tab, p, q);
			sortuj(tab, q + 1, k);
		}
	}

	static int podzialTablicy(int tab[], int p, int k) {
		int pivot = tab[k];
		int i = p - 1;
		int j = k + 1;

		while (true) {
			do {
				i++;
			} while (i <= k && tab[i] < pivot);

			do {
				j--;
			} while (j >= p && tab[j] > pivot);

			if (i <= j) {
				int temp = tab[j];
				tab[j] = tab[i];
				tab[i] = temp;
			} else {
				return j;
			}
		}
	}

	public static void main(String[] args) {
		int zarobki[] = {8500, 6400, 2800, 3500, 12870, 3300, 7020, 3000, 8100};
		int n = 9;
		double mediana;

		sortuj(zarobki, 0, n - 1);

		// gdy n nieparzyste
		if(n%2 == 1)
			mediana = zarobki[n/2];
		//gdy n parzyste
		else
			mediana = ((double)zarobki[n/2] + (double)zarobki[n/2 - 1]) / 2;
		    
		System.out.print(mediana);
	}
}

Implementacja algorytmu

I_R_W14_M27_Java Metoda Quicksort