Przeczytaj

W poprzedniej sekcji zaprezentowano, na czym polega sortowanie pozycyjne oraz jak przebiega jego implementacja w języku Java. W tej sekcji pokażemy, że nie zawsze algorytmem pomocniczym jest sortowanie przez zliczanie. Zaimplementujemy algorytm sortowania pozycyjnego, używając pomocniczo sortowania bąbelkowego. Pamiętajmy jednak, że możemy wykorzystać dowolny stabilny algorytm sortujący, np. sortowanie przez wstawianie lub sortowanie przez scalanie.

Algorytm sortowania pozycyjnego w języku Java

Zacznijmy od stworzenia funkcji, która będzie przechowywała tablicę zawierającą łańcuchy znaków – będą to przykładowe słowa.

// funkcja sortowania pozycyjnego
static void sortowaniePozycyjneSlow(String[] slowa) {

}

Ponieważ sortowane słowa mogą być różnej długości, zanim przystąpimy do właściwej implementacji algorytmu, znajdziemy najdłuższe słowo. W tym celu zapiszemy długość pierwszego słowa do zmiennej maxDlugosc. Następnie w pętli będziemy porównywali długości kolejnych słów ze zmienną maxDlugosc. Jeżeli sprawdzane słowo okaże się dłuższe, zmienimy wartość zmiennej maxDlugosc na długość obecnie sprawdzanego słowa. Pamiętajmy, że interesuje nas tylko długość najdłuższego słowa, a nie to, które słowo jest najdłuższe – dlatego wystarczy tylko jedna zmienna.

// funkcja sortowania pozycyjnego
static void sortowaniePozycyjneSlow(String[] slowa) {
	// znajdujemy najdłuższe słowo w tablicy
	int maxDlugosc = slowa[0].length();
    for (int i = 1; i < slowa.length - 1; i++) {
		if(slowa[i].length() > maxDlugosc) {
			maxDlugosc = slowa[i].length();
		}
	}
}

Teraz możemy napisać właściwy algorytm sortowania pozycyjnego. W pętli for będziemy wywoływać funkcję sortującą – w tym przypadku będzie to funkcja sortowanieBabelkowe. Funkcja ta będzie zawierać pomocniczy stabilny algorytm sortowania. Wykonywanie pętli rozpocznie się od znaku o indeksie maxDlugosc - 1, a zakończy na indeksie 0.

// funkcja sortowania pozycyjnego
static void sortowaniePozycyjneSlow(String[] slowa) {
	// znajdujemy najdłuższe słowo w tablicy
	int maxDlugosc = slowa[0].length();
    for (int i = 1; i < slowa.length - 1; i++) {
		if(slowa[i].length() > maxDlugosc) {
			maxDlugosc = slowa[i].length();
		}
	}

	// sortujemy dla każdej kolejnej pozycji
	for(int i = maxDlugosc - 1; i >= 0; i--) {
		sortowanieBabelkowe(slowa, i);
	}
}

Przykładowy algorytm pomocniczy – sortowanie bąbelkowe

Po przygotowaniu pierwszej funkcji – wskazującej, po którym znaku będziemy układać elementy w tym wywołaniu, wybieramy stabilny algorytm sortowania i przechodzimy do implementacji algorytmu sortowania wewnętrznego. Funkcja realizująca ten algorytm będzie przyjmować dwa argumenty: jednowymiarową tablicę znaków slowa oraz liczbę całkowitą indeksZnaku. Pamiętajmy, że algorytm w niej zawarty musi być stabilnystabilny algorytm sortowaniastabilny.

Algorytmem sortowania, który spełnia nasze wymagania jest między innymi sortowanie bąbelkowe.

Opis tego algorytmu możesz znaleźć w odpowiednim e‑materiale. W tej sekcji potrzebujemy wprowadzić jedynie odpowiednią modyfikację, która zapobiegnie wyświetlaniu błędów w sytuacji, gdy sortowane słowa są różnej długości.

static void sortowanieBabelkowe(String[] slowa, int indeksZnaku) {
    
}

Zapiszmy w zmiennej n długość tablicy slowa.

static void sortowanieBabelkowe(String[] slowa, int indeksZnaku) {
    int n = slowa.length;
}

Stwórzmy również dwie pętle. Pierwsza z nich w każdym swoim obiegu umieści na odpowiednim miejscu jeden z elementów. Druga pętla, wewnętrzna, będzie odpowiedzialna za porównywanie elementów i ich zamianę.

static void sortowanieBabelkowe(String[] slowa, int indeksZnaku) {
    int n = slowa.length;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++) {

        }
}

Teraz wprowadzamy instrukcję warunkową, której nie ma w oryginalnym algorytmie. Sprawdzamy, czy słowa które porównujemy, mają na pozycji indeksZnaku jakikolwiek znak. Jeżeli nie mają (ponieważ np. są za krótkie), to porównywanie ich liter o danym indeksie jest bezcelowe.

static void sortowanieBabelkowe(String[] slowa, int indeksZnaku) {
    int n = slowa.length;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++) {
            if (slowa[j].length() > indeksZnaku && slowa[j + 1].length() > indeksZnaku) {

                }
            }
        }
}

Zapisujemy instrukcje, które wykonają się, jeśli zostanie spełniony warunek zapisany w linii 5. Zadaniem tych instrukcji jest zamiana miejscami porównywanych elementów.

static void sortowanieBabelkowe(String[] slowa, int indeksZnaku) {
    int n = slowa.length;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++) {
            if (slowa[j].length() > indeksZnaku && slowa[j + 1].length() > indeksZnaku) {
                if (slowa[j].charAt(indeksZnaku) > slowa[j + 1].charAt(indeksZnaku)) {
                    String pom = slowa[j];
                    slowa[j] = slowa[j + 1];
                    slowa[j + 1] = pom;
                }
            }
        }
}

Mamy gotowy stabilny algorytm sortowania oraz algorytm sortowania pozycyjnego. Możemy teraz wywołać program dla przykładowych danych:

public static void main(String[] args) {
	String[] slowa = {
		"ziemniak",
		"kartofel",
		"pyra",
		"pomidor",
		"melon",
		"marchewka",
		"papryka",
		"arbuz",
		"ananas",
		"cebula",
		"czosnek"
	};

	sortowaniePozycyjneSlow(slowa);
	for(int i = 0; i < slowa.length; i++)
		System.out.println(slowa[i]);
}

Na wyjściu otrzymamy zatem:

ananas
arbuz
cebula
czosnek
kartofel
marchewka
melon
papryka
pomidor
pyra
ziemniak

Cały kod programu:

Linia 1. import java kropka util kropka Arrays średnik. Linia 3. public class SortowaniePozycyjneSlow otwórz nawias klamrowy. Linia 5. static void sortowaniePozycyjneSlow otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy slowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. int maxDlugosc znak równości slowa otwórz nawias kwadratowy 0 zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 7. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny slowa kropka length minus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. if otwórz nawias okrągły slowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny maxDlugosc zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. maxDlugosc znak równości slowa otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 10. zamknij nawias klamrowy. Linia 11. zamknij nawias klamrowy. Linia 13. for otwórz nawias okrągły int i znak równości maxDlugosc minus 1 średnik i zamknij nawias ostrokątny znak równości 0 średnik i minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. sortowanieBabelkowe otwórz nawias okrągły slowa przecinek i zamknij nawias okrągły średnik. Linia 15. zamknij nawias klamrowy. Linia 17. zamknij nawias klamrowy. Linia 19. static void sortowanieBabelkowe otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy slowa przecinek int indeksZnaku zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. int n znak równości slowa kropka length średnik. Linia 21. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n minus 1 średnik i plus plus zamknij nawias okrągły. Linia 22. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny n minus i minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. if otwórz nawias okrągły slowa otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny indeksZnaku ampersant ampersant slowa otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy kropka length otwórz nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny indeksZnaku zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. if otwórz nawias okrągły slowa otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły indeksZnaku zamknij nawias okrągły zamknij nawias ostrokątny slowa otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły indeksZnaku zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 25. String pom znak równości slowa otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik. Linia 26. slowa otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości slowa otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik. Linia 27. slowa otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości pom średnik. Linia 28. zamknij nawias klamrowy. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 32. zamknij nawias klamrowy. Linia 34. 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 35. String otwórz nawias kwadratowy zamknij nawias kwadratowy slowa znak równości otwórz nawias klamrowy. Linia 36. cudzysłów ziemniak cudzysłów przecinek. Linia 37. cudzysłów kartofel cudzysłów przecinek. Linia 38. cudzysłów pyra cudzysłów przecinek. Linia 39. cudzysłów pomidor cudzysłów przecinek. Linia 40. cudzysłów melon cudzysłów przecinek. Linia 41. cudzysłów marchewka cudzysłów przecinek. Linia 42. cudzysłów papryka cudzysłów przecinek. Linia 43. cudzysłów arbuz cudzysłów przecinek. Linia 44. cudzysłów ananas cudzysłów przecinek. Linia 45. cudzysłów cebula cudzysłów przecinek. Linia 46. cudzysłów czosnek cudzysłów. Linia 47. zamknij nawias klamrowy średnik. Linia 49. sortowaniePozycyjneSlow otwórz nawias okrągły slowa zamknij nawias okrągły średnik. Linia 50. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny slowa kropka length średnik i plus plus zamknij nawias okrągły. Linia 51. System kropka out kropka println otwórz nawias okrągły slowa otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 52. zamknij nawias klamrowy. Linia 53. zamknij nawias klamrowy.

import java.util.Arrays;

public class SortowaniePozycyjneSlow {

    static void sortowaniePozycyjneSlow(String[] slowa) {
        int maxDlugosc = slowa[0].length();
        for (int i = 1; i < slowa.length - 1; i++) {
            if(slowa[i].length() > maxDlugosc) {
                maxDlugosc = slowa[i].length();
            }
        }    

        for (int i = maxDlugosc - 1; i >= 0; i--) {
            sortowanieBabelkowe(slowa, i);
        }
        
    }    

    static void sortowanieBabelkowe(String[] slowa, int indeksZnaku) {
        int n = slowa.length;
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < n - i - 1; j++) {
                if (slowa[j].length() > indeksZnaku && slowa[j + 1].length() > indeksZnaku) {
                    if (slowa[j].charAt(indeksZnaku) > slowa[j + 1].charAt(indeksZnaku)) {
                        String pom = slowa[j];
                        slowa[j] = slowa[j + 1];
                        slowa[j + 1] = pom;
                    }
                }
            }

    }

    public static void main(String[] args) {
        String[] slowa = {
                "ziemniak",
                "kartofel",
                "pyra",
                "pomidor",
                "melon",
                "marchewka",
                "papryka",
                "arbuz",
                "ananas",
                "cebula",
                "czosnek"
        };

        sortowaniePozycyjneSlow(slowa);
        for (int i = 0; i < slowa.length; i++)
            System.out.println(slowa[i]);
    }
}

Słownik

porządek leksykograficzny

sposób porządkowania elementów zbioru, analogiczny do kolejności alfabetycznej

stabilny algorytm sortowania

algorytm, który dla dwóch równych elementów w zbiorze danych wejściowych zachowuje ich kolejność

Film samouczek

Sprawdź się

Algorytm sortowania pozycyjnego w języku Java

Przykładowy algorytm pomocniczy – sortowanie bąbelkowe

Słownik