Przypomnijmy sobie, na jakiej zasadzie działa sortowanie pozycyjne. Jest to rodzaj algorytmu sortowania, który używa wewnętrznego stabilnego algorytmustabilny algorytm sortowaniastabilnego algorytmu do sortowania według poszczególnych znaków. Sortujemy kolejno od znaków najmniej znaczących do znaków najbardziej znaczących. Zanim przejdziemy do implementacji algorytmu zapoznajmy się z poniższą specyfikacją:
Specyfikacja:
Dane:
daty – tablica łańcuchów znaków; każda z dat zapisana jest w formacie rrrr‑mm‑dd
Aby posortować daty pozycyjnie, należy zacząć od cyfry jedności dni, potem trzeba uwzględnić cyfry dziesiątek dni, a następnie sortować według kolejnych cyfr, aż do cyfry tysięcy w roku.
W przypadku sortowania dat możemy skorzystać z sortowania bąbelkowegosortowanie bąbelkowesortowania bąbelkowego. Jest to algorytm stabilny, który dodatkowo jest prosty w implementacji. Ponieważ wszystkie daty mają taką samą długość, nie będziemy musieli przejmować się sprawdzaniem, czy indeks sortowanego znaku mieści się w długości obecnie sprawdzanej daty.
Pamiętajmy, że zgodnie z zadaną specyfikacją daty będziemy zapisywali w następującym formacie:
Linia 1. rrrr minus mm minus dd.
rrrr-mm-dd
Kolejne segmenty oznaczają odpowiednio rok, miesiąc i dzień. Spójrzmy na kilka przykładowych dat:
Linia 1. 1410 minus 02 minus 23.
Linia 2. 2020 minus 12 minus 11.
Linia 3. 1999 minus 03 minus 05.
Linia 4. 1434 minus 04 minus 03.
Linia 5. 1773 minus 14 minus 13.
Teraz stwórzmy pętlę, w której posortujemy pozycyjnie daty. W tym celu wykorzystamy algorytm sortowania bąbelkowego.
Linia 1. static void sortowaniePozycyjne otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy daty zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. prawy ukośnik prawy ukośnik Sortujemy od cyfry jedności dnia do cyfry tysięcy roku.
Linia 3. for otwórz nawias okrągły int i znak równości 9 ś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 4. prawy ukośnik prawy ukośnik nie sortujemy myślników w zapisie dat.
Linia 5. if otwórz nawias okrągły i wykrzyknik znak równości 4 ampersant ampersant i wykrzyknik znak równości 7 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 6. sortowanieBabelkowe otwórz nawias okrągły daty przecinek i zamknij nawias okrągły średnik.
Linia 7. zamknij nawias klamrowy.
Linia 8. zamknij nawias klamrowy.
Linia 9. zamknij nawias klamrowy.
static void sortowaniePozycyjne(String[] daty) {
// Sortujemy od cyfry jedności dnia do cyfry tysięcy roku
for (int i = 9; i >= 0; i--) {
// nie sortujemy myślników w zapisie dat
if (i != 4 && i != 7) {
sortowanieBabelkowe(daty, i);
}
}
}
Sortujemy od najmniej znaczącej wartości, czyli od cyfry jedności dnia – dlatego w naszej pętli pojawia się zapis i--, który oznacza dekrementacjędekrementacjadekrementację zmiennej i.
Pamiętajmy o przekazaniu zmiennej i do funkcji sortowanieBabelkowe – łatwo o tym zapomnieć, ponieważ zazwyczaj funkcja ta przyjmuje tylko tablicę z danymi, które ma posortować.
Warunek (i != 4 && i != 7) został wprowadzony po to, aby zagwarantować, że program nie będzie sortował myślników, które znajdują się na pozycjach 4 i 7.
Algorytm sortowania bąbelkowego
Napiszmy funkcję realizującą algorytm sortowania bąbelkowegoPCfvfjgLksortowania bąbelkowego. Oprócz tablicy z danymi będzie ona dodatkowo przyjmowała pozycję, według której zostaną posortowane dane. Zaczniemy od stworzenia pomocniczej zmiennej temp oraz zmiennej logicznej zmienilaSie – posłuży ona do sprawdzania, czy w jednym „przejściu” sortowania została wykonana jakakolwiek zamiana.
Linia 1. static void sortowanieBabelkowe otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy daty przecinek int index zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. prawy ukośnik prawy ukośnik Pomocnicza zmienna.
Linia 3. String temp średnik.
Linia 4. boolean zmienilaSie znak równości false średnik.
Linia 6. zamknij nawias klamrowy.
Teraz deklarujemy dwie zagnieżdżone pętle for. Zewnętrzna będzie przechodziła po wszystkich elementach tablicy, a wewnętrzna po wszystkich oprócz ostatniego. Na początku każdego wykonania zewnętrznej pętli ustawiamy wartość zmiennej logicznej na false.
Linia 1. static void sortowanieBabelkowe otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy daty przecinek int index zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. prawy ukośnik prawy ukośnik Pomocnicza zmienna.
Linia 3. String temp średnik.
Linia 4. boolean zmienilaSie znak równości false średnik.
Linia 6. prawy ukośnik prawy ukośnik Sortujemy dane bąbelkowo.
Linia 7. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny daty kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy.
Linia 8. zmienilaSie znak równości false średnik.
Linia 9. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny daty kropka length minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy.
Linia 11. zamknij nawias klamrowy.
Linia 12. zamknij nawias klamrowy.
Linia 13. zamknij nawias klamrowy.
static void sortowanieBabelkowe(String[] daty, int index) {
// Pomocnicza zmienna
String temp;
boolean zmienilaSie = false;
// Sortujemy dane bąbelkowo
for(int i = 0; i < daty.length; i++) {
zmienilaSie = false;
for (int j = 0; j < daty.length - 1; j++) {
}
}
}
Dodajmy instrukcję warunkową, która sprawdzi, czy elementy powinny zostać zamienione miejscami. Jeżeli tak, wykorzystujemy wcześniej zadeklarowaną zmienną temp. Pamiętajmy o zmiennej index – porównujemy znaki na konkretnej pozycji dat, a nie całe daty. Jeżeli zamieniliśmy znaki miejscami, wartość zmiennej zmienilaSie powinna zostać ustawiona na true.
Na samym końcu zewnętrznej pętli dodamy instrukcję warunkową, która sprawdzi, czy nie została wykonana żadna zamiana. Jeżeli nie – nasza tablica jest posortowana, więc możemy wyjść z pętli, tym samym kończąc naszą funkcję.
Linia 1. static void sortowanieBabelkowe otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy daty przecinek int index zamknij nawias okrągły otwórz nawias klamrowy.
Linia 2. prawy ukośnik prawy ukośnik Pomocnicza zmienna.
Linia 3. String temp średnik.
Linia 4. boolean zmienilaSie znak równości false średnik.
Linia 6. prawy ukośnik prawy ukośnik Sortujemy dane bąbelkowo.
Linia 7. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny daty kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy.
Linia 8. zmienilaSie znak równości false średnik.
Linia 9. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny daty kropka length minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy.
Linia 10. if otwórz nawias okrągły daty otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły index zamknij nawias okrągły zamknij nawias ostrokątny otwórz nawias okrągły daty otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły index zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy.
Linia 11. temp znak równości daty otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik.
Linia 12. daty otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości daty otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik.
Linia 13. daty otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości temp średnik.
Linia 14. zmienilaSie znak równości true średnik.
Linia 15. zamknij nawias klamrowy.
Linia 16. zamknij nawias klamrowy.
Linia 17. if otwórz nawias okrągły wykrzyknik zmienilaSie zamknij nawias okrągły otwórz nawias klamrowy.
Linia 18. break średnik.
Linia 19. zamknij nawias klamrowy.
Linia 20. zamknij nawias klamrowy.
Linia 21. zamknij nawias klamrowy.
static void sortowanieBabelkowe(String[] daty, int index) {
// Pomocnicza zmienna
String temp;
boolean zmienilaSie = false;
// Sortujemy dane bąbelkowo
for(int i = 0; i < daty.length; i++) {
zmienilaSie = false;
for (int j = 0; j < daty.length - 1; j++) {
if (daty[j].charAt(index) > (daty[j+1].charAt(index))) {
temp = daty[j];
daty[j] = daty[j+1];
daty[j+1] = temp;
zmienilaSie = true;
}
}
if (!zmienilaSie) {
break;
}
}
}
Kompletny kod
Teraz spójrzmy na kompletny kod, który zademonstruje działanie algorytmu.
Linia 1. public class Main otwórz nawias klamrowy.
Linia 2. static void sortowaniePozycyjne otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy daty zamknij nawias okrągły otwórz nawias klamrowy.
Linia 3. prawy ukośnik prawy ukośnik Sortujemy od cyfry jedności dnia do cyfry tysięcy roku.
Linia 4. for otwórz nawias okrągły int i znak równości 9 ś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 5. prawy ukośnik prawy ukośnik nie sortujemy myślników w zapisie dat.
Linia 6. if otwórz nawias okrągły i wykrzyknik znak równości 4 ampersant ampersant i wykrzyknik znak równości 7 zamknij nawias okrągły otwórz nawias klamrowy.
Linia 7. sortowanieBabelkowe otwórz nawias okrągły daty przecinek i zamknij nawias okrągły średnik.
Linia 8. zamknij nawias klamrowy.
Linia 9. zamknij nawias klamrowy.
Linia 10. zamknij nawias klamrowy.
Linia 12. static void sortowanieBabelkowe otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy daty przecinek int index zamknij nawias okrągły otwórz nawias klamrowy.
Linia 13. prawy ukośnik prawy ukośnik Tymczasowa zmienna.
Linia 14. String temp średnik.
Linia 15. boolean zmienilaSie znak równości false średnik.
Linia 17. prawy ukośnik prawy ukośnik Sortujemy dane bąbelkowo.
Linia 18. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny daty kropka length średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy.
Linia 19. zmienilaSie znak równości false średnik.
Linia 20. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny daty kropka length minus 1 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy.
Linia 21. if otwórz nawias okrągły daty otwórz nawias kwadratowy j zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły index zamknij nawias okrągły zamknij nawias ostrokątny otwórz nawias okrągły daty otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy kropka charAt otwórz nawias okrągły index zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy.
Linia 22. temp znak równości daty otwórz nawias kwadratowy j zamknij nawias kwadratowy średnik.
Linia 23. daty otwórz nawias kwadratowy j zamknij nawias kwadratowy znak równości daty otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy średnik.
Linia 24. daty otwórz nawias kwadratowy j plus 1 zamknij nawias kwadratowy znak równości temp średnik.
Linia 25. zmienilaSie znak równości true średnik.
Linia 26. zamknij nawias klamrowy.
Linia 27. zamknij nawias klamrowy.
Linia 28. if otwórz nawias okrągły wykrzyknik zmienilaSie zamknij nawias okrągły otwórz nawias klamrowy.
Linia 29. break średnik.
Linia 30. zamknij nawias klamrowy.
Linia 31. 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 daty znak równości otwórz nawias klamrowy.
Linia 36. cudzysłów 1410 minus 02 minus 23 cudzysłów przecinek.
Linia 37. cudzysłów 2020 minus 12 minus 11 cudzysłów przecinek.
Linia 38. cudzysłów 1999 minus 03 minus 05 cudzysłów przecinek.
Linia 39. cudzysłów 1434 minus 04 minus 03 cudzysłów przecinek.
Linia 40. cudzysłów 1773 minus 14 minus 13 cudzysłów.
Linia 41. zamknij nawias klamrowy średnik.
Linia 43. sortowaniePozycyjne otwórz nawias okrągły daty zamknij nawias okrągły średnik.
Linia 44. for otwórz nawias okrągły String date dwukropek daty zamknij nawias okrągły.
Linia 45. System kropka out kropka println otwórz nawias okrągły date zamknij nawias okrągły średnik.
Linia 46. zamknij nawias klamrowy.
Linia 47. zamknij nawias klamrowy.
public class Main {
static void sortowaniePozycyjne(String[] daty) {
// Sortujemy od cyfry jedności dnia do cyfry tysięcy roku
for (int i = 9; i >= 0; i--) {
// nie sortujemy myślników w zapisie dat
if (i != 4 && i != 7) {
sortowanieBabelkowe(daty, i);
}
}
}
static void sortowanieBabelkowe(String[] daty, int index) {
// Tymczasowa zmienna
String temp;
boolean zmienilaSie = false;
// Sortujemy dane bąbelkowo
for(int i = 0; i < daty.length; i++) {
zmienilaSie = false;
for (int j = 0; j < daty.length - 1; j++) {
if (daty[j].charAt(index) > (daty[j+1].charAt(index))) {
temp = daty[j];
daty[j] = daty[j+1];
daty[j+1] = temp;
zmienilaSie = true;
}
}
if (!zmienilaSie) {
break;
}
}
}
public static void main(String[] args) {
String[] daty = {
"1410-02-23",
"2020-12-11",
"1999-03-05",
"1434-04-03",
"1773-14-13"
};
sortowaniePozycyjne(daty);
for (String date : daty)
System.out.println(date);
}
}
Wyjście naszego programu:
Linia 1. 1410 minus 02 minus 23.
Linia 2. 1434 minus 04 minus 03.
Linia 3. 1773 minus 14 minus 13.
Linia 4. 1999 minus 03 minus 05.
Linia 5. 2020 minus 12 minus 11.
sortowanie polegające na porównywaniu dwóch sąsiadujących elementów w kolejności od lewej do prawej i zamianie ich ze sobą, jeżeli znajdują się w nieprawidłowej kolejności
stabilny algorytm sortowania
stabilny algorytm sortowania
algorytm sortowania, który w przypadku elementów o równej wartości pozostawi je w takiej samej kolejności, w jakiej były pierwotnie; do stabilnych algorytmów sortowania należą m.in.: sortowanie bąbelkowe, sortowanie przez zliczanie, sortowanie przez wstawianie, sortowanie kubełkowe, sortowanie przez scalanie