1. Proste sortowanie i wyszukiwanie
Wielokrotnie zetkniemy się z potrzebą uporządkowania informacji, ułożenia
danych w określonej kolejności. W uporządkowanych zestawach informacji łatwiej
jest odnajdywać dane, zresztą samo uporządkowanie może być niezbędną cechą
jakiegoś zbioru danych. Najprostsze przykłady:
Ułożenie danych w określonej kolejności oznacza jakiś ich porządek. Zwykle przy takim układaniu
będziemy posługiwać się tutaj rosnącymi (lub malejącymi) wartościami jakiejś
cechy danych. Np. lista 10 zawodników, którzy zdobyli największą liczbę punktów
powinna być uporządkowana według liczby punktów - od największej do najmniejszej
(wtedy będziemy mogli stwierdzić kto wygrał zawody i jakie miejsca zajęli
poszczególni zawodnicy) ![]()
Zadanie: przed lekturą dalszego tekstu proszę spróbować samodzielnie
napisać metodę void selectionSort(int[] a), sortującą w porządku niemalejącym
tablicę przekazaną jako argument>
Możliwe rozwiązanie: public void selectionSort(int[] a) { // toInd - oznacza ostatni indeks nieposortowanej części tablicy // na początku jest to ostatni indeks tablicy // w kolejnych krokach toInd będzie zmniejszany o 1 // bo zmniejszają się rozmiary nieposortowanej częsci tablicy // Gdy toInd osiągnie wartość 0 - "nieposortowany" będzie pierwszy // element. Ale nie mamy go już gdzie przestawić, faktycznie znajduje się // on na własciwym miejscu. // Zatem nie musimy dokonywać żadnego przestawienia. // Tablica jest posortowana. Kończymy pętle. for (int toInd=a.length-1; toInd>0; toInd--) { int indMax = 0; // indeks maksymalnego elementu // w nieposortowanej części tablicy // szukamy tego indeksu, przeglądając nieposortowaną część tablicy for (int k=1; k <= toInd; k++) if (a[indMax] < a[k]) indMax = k; // Przestawiamy elementy: // maksymalny element idzie na ostatnią pozycję w nieposortowanej // części tablicy; a liczba spod tego indeksu jest zapisywana // w miejscu okupowanym poprzednio przez max element int temp = a[toInd]; a[toInd] = a[indMax]; a[indMax] = temp; } }
Do przetestowania napisanej metody możemy użyć następującej klasy: import java.util.*; public class SelSort { public SelSort(int n, int m) { Random rand = new Random(); int[] a = new int[n]; for (int i=0; i < n; i++) { a[i] = rand.nextInt(m+1); System.out.print(" " + a[i]); } selectionSort(a); System.out.print('\n'); for (int i=0; i < n; i++) System.out.print(" " + a[i]); } public void selectionSort(int[] a) { // ... } public static void main(String[] args) { new SelSort(Integer.parseInt(args[0]), Integer.parseInt(args[1])); } } Jako argumenty wywołania podajemy rozmiar tablicy oraz maksymalną liczbę,
jaka może znaleźć się w tablicy (powiedzmy max). Wartości elementów tablicy
zostaną utworzone przez generator liczb pseudolosowych (0 <= a[i] <=
max). Następnie wywołana zostanie metoda selectionSort.
5 72 58 39 75 18 92 79 35 63
5 18 35 39 58 63 72 75 79 92
Algorytm sortowania przez wybór należy do najwolniejszych algorytmów sortowania. Jednak w nauce programowania opanowanie różnych algorytmow sortowania
jest bardzo istotne, bowiem wyrabia umiejętność myślenia i rozwiązywania
problemów programistycznych oraz umożliwia późniejszą adaptację standardowych algorytmów
sortowania do specyficznych sytuacji
W praktycznym programowiu nikt nie pisze algorytmow sortowania - korzysta się zwykle z gotowego oprogramownia. Również Java dostarcza oprogramowanych algorytmów w postaci gotowych metod. Poznamy je bliżej przy okazji omawiania kolekcji w drugim semestrze. Teraz może warto powiedzieć tylko, że w pakiecie java.util istnieje klasa Arrays, w której zdefiniowano metody sort , umożliwiające sortowanie m.in. tablic liczb całkowitych i rzeczywistych. Dla ciekawości możemy sprawdzić jaka jest różnica czasowa zastosowania algorytmu selection sort oraz tego, który poslużył do sformułowania metod sort w klasie Arrays (jest to zmodyfikowany algorytm quicksort; studenci poznają go na zajęciach z przedmiotu "Algorytmy i struktury danych"). import java.util.*; class QTimer { private final long start; public QTimer() { start = System.currentTimeMillis(); } public long getElapsed() { return System.currentTimeMillis() - start; } } public class SelSort1 { static public void selectionSort(int[] a) { // ... jak na poprzednim wydruku } public static void main(String[] args) { int n = Integer.parseInt(args[0]); Random rand = new Random(); int[] a = new int[n]; int[] b = new int[n]; for (int i=0; i < n; i++) { a[i] = rand.nextInt(n*10); b[i] = a[i]; } System.out.println("Liczba elementów tablicy " + n); QTimer qt = new QTimer(); selectionSort(a); System.out.println("Czas selection sort: " + qt.getElapsed()); qt = new QTimer(); Arrays.sort(b); System.out.println("Czas quicksort: " + qt.getElapsed()); } }
Przykładowo, dla losowo wygenerowanych tablic 50000 liczb całkowitych moglibyśmy uzyskać następujący wynik:
Liczba elementów tablicy 50000
Czas selection sort: 43830 Czas quicksort: 110
Widzimy więc, że dobry algorytm sortowania może być - przy dużej liczbie
elementów tablicy - nawet kilkaset razy szybszy niż bardzo proste, ale wolne
sortowanie przez wybór. Zadanie: napisać metodę sortującą tablicę łańcuchów znakowych w porządku niemalejącym. Przed lekturą dalszego tekstu - proszę wykonać to zadanie samodzielnie Oczywiście - powinniśmy skorzystać z metody compareTo z klasy String. public class SortString { static public void selectionSort(String[] s) { for (int toInd=s.length-1; toInd>0; toInd--) { int indMax = 0; for (int k=1; k <= toInd; k++) if (s[indMax].compareTo(s[k]) < 0) indMax = k; String temp = s[toInd]; s[toInd] = s[indMax]; s[indMax] = temp; } } public static void show(String[] s) { System.out.print('\n'); for (int i=0; i < s.length; i++) System.out.print(" " + s[i]); } public static void main(String[] args) { String[] s = {"A", "Z", "C", "B", "1", "3", "2", "A", "C" }; show(s); selectionSort(s); show(s); } }
Wydruk programu:
A Z C B 1 3 2 A C
1 2 3 A A B C C Z
Często też w programowaniu będziemy stykać się z problemem odnalezienia konkretnego elementu tablicy. public class Search { public static int linearSearch(int[] tab, int v) { for (int i=0; i < tab.length; i++) if (tab[i] == v) return i; return -1; } } Taki sposób wyszukiwania nazywany jest wyszukiwaniem liniowym. Wyszukiwanie liniowe polega na przeglądaniu kolejnych elementów tablicy i porównywaniu ich z poszukiwaną wartością
Wyszukiwanie liniowe może okazać się bardzo wolne. Jeśli np. szukany element
znajduje się w tablicy na ostatniej pozycji, to liczba wykonanych iteracji
i porównań będzie równa liczbie elementów tablicy, co przy bardzo dużych
tablicach prowadzi do długiego działania programu. ![]()
Gdybyśmy natomiast szukali liczby 4, to sekwencja kroków byłaby następująca: ![]()
Zwróćmy uwagę, że w każdym kroku binarnego wyszukiwania porównujemy poszukiwaną
wartość z wartością elementu znajdującego się na pozycji "dzielącej" tablicę
na kolejne połówki (element ten na rysunkach zaznaczany jest na żółto, pokazano
też jego indeks). public class Search { // v - poszukiwana wartość w tablicy tab static public int binarySearch(int[] tab, int v) { int low = 0; // lewy skrajny indeks "aktualnej" połówki int high = tab.length - 1; // prawy skrajny indeks "aktualnej" połowki // dopóki możemy dzielić tablicę while (low <= high) { int mid = (low + high) / 2; // indeks środkowego elementu // zakresu low..high if (v < tab[mid]) // jeżeli wartość jest w lewej połówce: high = mid - 1; // zmodyfikować skrajny prawy indeks else if (v > tab[mid]) // w przeciwnym razie jeżeli w prawej połówce: low = mid + 1; // zmodyfikować skrajny lewy indeks else return mid; // w przeciwnym razie: zanleziony! } return -1; // w tablicy nie znaleziono wartości v } Binarne wyszukiwanie jest szybkim algorytmem odnajdywania informacji
w posortowanych tablicach. W każdym jego kroku zakres rozpatrywanych elementów
tablicy zmniejsza się o połowę
Należy wyraźnie podkreślić, że binarne wyszukiwanie wymaga posortowanych
danych. Często jednak opłaca się najpierw posortować dane, by później móc
szybko odnajdywać wśród nich potrzebną informację. public class Travel { private String dest; private double price; public Travel(String s, double p) { dest = s; price = p; } public String getDest() { return dest; } public double getPrice() { return price; } }
Stworzymy następnie klasę TravelSearcher, której obiekty będą zawierać tablicę
wycieczek. Z tablicy tej można będzie za pomocą metody search uzyskiwać referencję
do obiektu-wycieczki, której cel podano jako argument. public class TravelSearcher { private Travel[] travel; public TravelSearcher(Travel[] t) { travel = new Travel[t.length]; for (int i=0; i < t.length; i++) travel[i] = t[i]; sortByDest(); } public Travel search(String dest) { int low = 0; int high = travel.length - 1; while (low <= high) { int mid = (low + high) / 2; int compRes = dest.compareToIgnoreCase(travel[mid].getDest()); if (compRes < 0) high = mid - 1; else if (compRes > 0) low = mid + 1; else return travel[mid]; } return null; } public Travel[] getTravels() { return travel; } private void sortByDest() { for (int to=travel.length-1; to>0; to--) { int i = 0; for (int k=1; k <= to; k++) if (travel[i].getDest().compareTo(travel[k].getDest()) < 0) i = k; Travel temp = travel[to]; travel[to] = travel[i]; travel[i] = temp; } } }
Komentarze:
I wreszcie klasa testująca (z niewielką przykładową liczbą wycieczek,
ale można ją zwiększyć wczytując np. wycieczki z jakiegoś pliku). ![]() ![]() import javax.swing.*; public class Test { public static void main(String[] args) { String[] dest = { "Bali", "Cypr", "Ibiza", "Kenia", "Kuba" }; double[] price = { 5000, 2500, 2800, 4500, 6000 }; Travel[] t = new Travel[dest.length]; for (int i = 0; i < t.length; i++) t[i] = new Travel(dest[i], price[i]); TravelSearcher ts = new TravelSearcher(t); String d; while((d=JOptionPane.showInputDialog("Podaj cel podróży:")) != null) { Travel trav = ts.search(d); String msg; if (trav == null) msg = "Nie znaleziono takiej podróży"; else msg = trav.getDest() + " - cena: " + trav.getPrice(); JOptionPane.showMessageDialog(null, msg); } System.exit(0); } } Zauważmy jeszcze, że dla tablic referencji do obiektów klasy Travel
musieliśmy zdefiniować specjalne, tylko dla nich ważne, metody sortowania
i wyszukiwania.
|