Implementacja algorytmu - I_R_W14_M27_Java Metoda Quicksort

R13XFHOJPLQJ3

Implementacja algorytmu w języku Java

Algorytm sortowania szybkiego oparty jest na dwóch funkcjach. Są to:

Funkcja wywoływana rekurencyjnie – nazwiemy ją sortowanieSzybkie. Nie będzie ona zwracała żadnej wartości, jej nazwa zostanie poprzedzona słowem kluczowym void. Funkcja ta będzie przyjmowała trzy parametry:
- int tab[] – tablica zawierająca liczby całkowite do posortowania,
- int indeksPoczatkowy – indeks elementu początkowego fragmentu tablicy, od którego chcemy rozpocząć sortowanie tablicy,
- int indeksKoncowy – indeks końcowego elementu fragmentu tablicy, na którym chcemy zakończyć sortowanie tablicy.
Funkcja odpowiadająca za podział tablicy – wartością zwracaną przez funkcję będzie indeks miejsca podziału tablicy (indeks pivota). W naszym programie funkcja przyjmie nazwę podzielTablice. Parametry tej funkcji będą identyczne jak w przypadku funkcji sortowanieSzybkie.

Oto obie zadeklarowane funkcje:

void sortowanieSzybkie(int tab[], int indeksPoczatkowy, int indeksKoncowy) {

}

int podzielTablice(int tab[], int indeksPoczatkowy, int indeksKoncowy) {

}

Zacznijmy od wypełnienia bloku funkcji sortowanieSzybkie. W instrukcji warunkowej sprawdzamy, czy podana jako argument tablica składa się z więcej niż jednego elementu. Jeżeli tak, następuje wywołanie funkcji podziału tablicy – podzielTablice. Do zmiennej indeksPodzialu zostanie zapisany punkt podziału tablicy (określony przez funkcję podzielTablice).

Po wywołaniu funkcji podziału następują dwa wywołania rekurencyjne funkcji sortowanieSzybkie():

sortowanieSzybkie(tab, indeksPoczatkowy, indeksPodzialu - 1);
– dla pierwszej (lewej) części tablicy,
sortowanieSzybkie(tab, indeksPodzialu + 1, indeksKoncowy);
– dla drugiej (prawej) części tablicy.

Oto cały blok funkcji sortowanieSzybkie():

static void sortowanieSzybkie(int tab[], int indeksPoczatkowy, int indeksKoncowy)
{
	if(indeksPoczatkowy < indeksKoncowy) {
		int indeksPodzialu = podzielTablice(tab, indeksPoczatkowy, indeksKoncowy);
		sortowanieSzybkie(tab, indeksPoczatkowy, indeksPodzialu - 1);
		sortowanieSzybkie(tab, indeksPodzialu + 1, indeksKoncowy);
	}
}

Kolejnym krokiem będzie przygotowanie funkcji podzielTablice.

Tworzymy zmienną pivot, do której zapisujemy wartość ostatniego elementu z sortowanego zakresu tablicy.

Ważne!

Pamiętajmy, że ten element możemy wybrać na inne sposoby, np. poprzez wskazanie elementu środkowego. Wybór pivota wraz ze sposobem uporządkowania tablicy mają znaczący wpływ na czas działania algorytmu. Jeżeli za każdym razem wybierany będzie element o wartości największej lub najmniejszej w tablicy, podział tablicy będzie nierównomierny. Jedna część tablicy będzie zawierała jeden element, natomiast druga część – wszystkie pozostałe. Ten pesymistyczny przypadek możemy otrzymać, gdy np. wybierzemy (pivot) o wartości ostatniego lub pierwszego elementu już posortowanej tablicy. Uzyskujemy wtedy kwadratową złożoność czasową algorytmu $O (n^{2})$ i liniową złożoność pamięciową $O (n)$ , spowodowaną dużą głębokością drzewa wywołań rekurencyjnych. W przypadku optymistycznym, tzn. jeżeli tablica będzie dzielona za każdym razem na dwie równe części (element osiowy będzie medianą z sortowanego fragmentu tablicy), złożoność czasowa algorytmu wyniesie $O (n \cdot \log n)$ , natomiast pamięciowa – $O (\log n)$ .

Następnym krokiem jest utworzenie zmiennej indeksElementuMniejszegoOdPivota, której ustawiamy wartość o 1 mniejszą od tej zapisanej w zmiennej indeksPoczatkowy. Będzie to iterator, spełniający dwa ważne zadania. Po pierwsze będzie wskazywał, na którą pozycję mamy przenieść element, gdy okaże się on mniejszy od pivota. Po drugie pomoże ustalić, w którym miejscu znajdują się elementy mniejsze od pivota. Tę zmienną wykorzystamy przy kolejnych podziałach tablicy.

Tworzymy pętlę for. Dla czytelności iterator sterujący pętlą określimy jako indeksPoszukujacy. Jego zadaniem będzie przejście po wszystkich elementach tablicy tab, które znajdują się w zadanym zakresie.

Wewnątrz pętli tworzymy instrukcję warunkową. Jeżeli wartość elementu tab[indeksPoszukujacy] jest mniejsza od wartości pivot, przenosimy ją na lewą stronę. Zwiększamy indeksElementuMniejszegoOdPivota i zamieniamy miejscami element znajdujący się w tablicy tab[indeksElementuMniejszegoOdPivota] z elementem tab[indeksPoszukujacy]. Pamiętajmy, że operacja ta jest powtarzana dla każdej komórki w tablicy, której indeks znajduje się w przedziale <indeksPoczatkowy, indeksKoncowy>.

Po przejściu pętli porządkujemy pivota – zamieniamy go miejscami z elementem wskazywanym przez indeksElementuMniejszegoOdPivota + 1.

Funkcję kończymy, zwracając indeks wskazujący na miejsce podziału: indeksElementuMniejszegoOdPivota + 1.

Linia 1. static 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 2. otwórz nawias klamrowy. Linia 3. int pivot znak równości tab otwórz nawias kwadratowy indeksKoncowy zamknij nawias kwadratowy średnik. Linia 4. int indeksElementuMniejszegoOdPivota znak równości indeksPoczatkowy minus 1 średnik. Linia 6. for otwórz nawias okrągły int indeksPoszukujacy znak równości indeksPoczatkowy średnik indeksPoszukujacy otwórz nawias ostrokątny indeksKoncowy średnik indeksPoszukujacy plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły tab otwórz nawias kwadratowy indeksPoszukujacy zamknij nawias kwadratowy otwórz nawias ostrokątny pivot zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. indeksElementuMniejszegoOdPivota plus plus średnik. Linia 10. int temp znak równości tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota zamknij nawias kwadratowy średnik. Linia 11. tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy indeksPoszukujacy zamknij nawias kwadratowy średnik. Linia 12. tab otwórz nawias kwadratowy indeksPoszukujacy zamknij nawias kwadratowy znak równości temp średnik. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy. Linia 16. int temp znak równości tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota plus 1 zamknij nawias kwadratowy średnik. Linia 17. tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota plus 1 zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy indeksKoncowy zamknij nawias kwadratowy średnik. Linia 18. tab otwórz nawias kwadratowy indeksKoncowy zamknij nawias kwadratowy znak równości temp średnik. Linia 20. return indeksElementuMniejszegoOdPivota plus 1 średnik. Linia 21. zamknij nawias klamrowy.

static int podzielTablice(int tab[], int indeksPoczatkowy, int indeksKoncowy) 
{
	int pivot = tab[indeksKoncowy];
	int indeksElementuMniejszegoOdPivota = indeksPoczatkowy - 1;
        
	for(int indeksPoszukujacy = indeksPoczatkowy; indeksPoszukujacy < indeksKoncowy; indeksPoszukujacy++){
		if(tab[indeksPoszukujacy] < pivot){
			indeksElementuMniejszegoOdPivota++;

			int temp = tab[indeksElementuMniejszegoOdPivota];
			tab[indeksElementuMniejszegoOdPivota] = tab[indeksPoszukujacy];
			tab[indeksPoszukujacy] = temp;
		}
	}

	int temp = tab[indeksElementuMniejszegoOdPivota + 1];
	tab[indeksElementuMniejszegoOdPivota + 1] = tab[indeksKoncowy];
	tab[indeksKoncowy] = temp;

	return indeksElementuMniejszegoOdPivota + 1;
}

Przejdźmy teraz do głównej funkcji programu – main, w której utworzymy tablicę z liczbami całkowitymi, a następnie wywołamy funkcję sortowanieSzybkie w celu posortowania elementów. Wypiszemy też elementy tablicy przed sortowaniem i po sortowaniu, żeby zobaczyć, czy zostało ono wykonane poprawnie.

public static void main(String[] args) 
{
	int tab[] = {4, 5, 65, 7, 4, 0, 23, 34, 12, 1, 3, 4, 5};
	int ostatniElement = tab.length;
	
	for(int i = 0; i < ostatniElement; i++) {
		System.out.print(tab[i] + "  ");
	}
    
	System.out.println();
	
	sortowanieSzybkie(tab, 0, tab.length - 1);
	
	for(int i = 0; i < ostatniElement; i++) {
		System.out.print(tab[i] + "  ");
	}
}

Oto pełen kod programu:

Linia 1. public class SortowanieSzybkie. Linia 2. otwórz nawias klamrowy. Linia 4. static void sortowanieSzybkie 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 5. otwórz nawias klamrowy. Linia 6. if otwórz nawias okrągły indeksPoczatkowy otwórz nawias ostrokątny indeksKoncowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. int indeksPodzialu znak równości podzielTablice otwórz nawias okrągły tab przecinek indeksPoczatkowy przecinek indeksKoncowy zamknij nawias okrągły średnik. Linia 8. sortowanieSzybkie otwórz nawias okrągły tab przecinek indeksPoczatkowy przecinek indeksPodzialu minus 1 zamknij nawias okrągły średnik. Linia 9. sortowanieSzybkie otwórz nawias okrągły tab przecinek indeksPodzialu plus 1 przecinek indeksKoncowy zamknij nawias okrągły średnik. Linia 10. zamknij nawias klamrowy. Linia 11. zamknij nawias klamrowy. Linia 13. static 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 14. otwórz nawias klamrowy. Linia 15. int pivot znak równości tab otwórz nawias kwadratowy indeksKoncowy zamknij nawias kwadratowy średnik. Linia 16. int indeksElementuMniejszegoOdPivota znak równości indeksPoczatkowy minus 1 średnik. Linia 18. for otwórz nawias okrągły int indeksPoszukujacy znak równości indeksPoczatkowy średnik indeksPoszukujacy otwórz nawias ostrokątny indeksKoncowy średnik indeksPoszukujacy plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. if otwórz nawias okrągły tab otwórz nawias kwadratowy indeksPoszukujacy zamknij nawias kwadratowy otwórz nawias ostrokątny pivot zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. indeksElementuMniejszegoOdPivota plus plus średnik. Linia 22. int temp znak równości tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota zamknij nawias kwadratowy średnik. Linia 23. tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy indeksPoszukujacy zamknij nawias kwadratowy średnik. Linia 24. tab otwórz nawias kwadratowy indeksPoszukujacy zamknij nawias kwadratowy znak równości temp średnik. Linia 25. zamknij nawias klamrowy. Linia 26. zamknij nawias klamrowy. Linia 28. int temp znak równości tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota plus 1 zamknij nawias kwadratowy średnik. Linia 29. tab otwórz nawias kwadratowy indeksElementuMniejszegoOdPivota plus 1 zamknij nawias kwadratowy znak równości tab otwórz nawias kwadratowy indeksKoncowy zamknij nawias kwadratowy średnik. Linia 30. tab otwórz nawias kwadratowy indeksKoncowy zamknij nawias kwadratowy znak równości temp średnik. Linia 32. return indeksElementuMniejszegoOdPivota plus 1 średnik. 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. Linia 36. otwórz nawias klamrowy. Linia 37. int tab otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy 4 przecinek 5 przecinek 65 przecinek 7 przecinek 4 przecinek 0 przecinek 23 przecinek 34 przecinek 12 przecinek 1 przecinek 3 przecinek 4 przecinek 5 zamknij nawias klamrowy średnik. Linia 38. int ostatniElement znak równości tab kropka length średnik. Linia 40. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny ostatniElement średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 41. 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 42. zamknij nawias klamrowy. Linia 44. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 46. sortowanieSzybkie otwórz nawias okrągły tab przecinek 0 przecinek tab kropka length minus 1 zamknij nawias okrągły średnik. Linia 48. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny ostatniElement średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 49. 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 50. zamknij nawias klamrowy. Linia 51. zamknij nawias klamrowy. Linia 52. zamknij nawias klamrowy.

public class SortowanieSzybkie 
{
	
	static void sortowanieSzybkie(int tab[], int indeksPoczatkowy, int indeksKoncowy)
    {
		if(indeksPoczatkowy < indeksKoncowy) {
			int indeksPodzialu = podzielTablice(tab, indeksPoczatkowy, indeksKoncowy);
			sortowanieSzybkie(tab, indeksPoczatkowy, indeksPodzialu - 1);
			sortowanieSzybkie(tab, indeksPodzialu + 1, indeksKoncowy);
		}
	}
	
	static int podzielTablice(int tab[], int indeksPoczatkowy, int indeksKoncowy) 
	{
		int pivot = tab[indeksKoncowy];
		int indeksElementuMniejszegoOdPivota = indeksPoczatkowy - 1;
        
		for(int indeksPoszukujacy = indeksPoczatkowy; indeksPoszukujacy < indeksKoncowy; indeksPoszukujacy++){
			if(tab[indeksPoszukujacy] < pivot){
				indeksElementuMniejszegoOdPivota++;

				int temp = tab[indeksElementuMniejszegoOdPivota];
				tab[indeksElementuMniejszegoOdPivota] = tab[indeksPoszukujacy];
				tab[indeksPoszukujacy] = temp;
			}
		}

		int temp = tab[indeksElementuMniejszegoOdPivota + 1];
		tab[indeksElementuMniejszegoOdPivota + 1] = tab[indeksKoncowy];
		tab[indeksKoncowy] = temp;

		return indeksElementuMniejszegoOdPivota + 1;
	}

	public static void main(String[] args) 
    {
		int tab[] = {4, 5, 65, 7, 4, 0, 23, 34, 12, 1, 3, 4, 5};
		int ostatniElement = tab.length;
	
		for(int i = 0; i < ostatniElement; i++) {
			System.out.print(tab[i] + "  ");
		}
        
		System.out.println();
	
		sortowanieSzybkie(tab, 0, tab.length - 1);
	
		for(int i = 0; i < ostatniElement; i++) {
			System.out.print(tab[i] + "  ");
		}
	}
}

Czas działania algorytmu

Strefa wyzwań

Implementacja algorytmu w języku Java