 |
 |
|
|
[ Pobierz całość w formacie PDF ] Konkretyzuje ona jedyny abstrakcyjny element tej logiki metodę createListSorter() tworzącą instancję klasy reprezentującej algorytm sortujący. 164 Algorytmy. Od podstaw spróbuj sam Implementowanie algorytmu sortowania bąbelkowego klasa BubbleListSorter Implementacja klasy realizującej algorytm sortowania bąbelkowego musi spełniać trzy na- stępujące kryteria: musi implementować interfejs ListSorter, musi dopuszczać dowolny komparator określający uporządkowanie elementów, musi przejść pozytywnie testy opisane przed chwilą. Mając na uwadze powyższe wymogi, rozpocznijmy od zdefiniowania konstruktora: package com.wrox.algorithms.sorting; import com.wrox.algorithms.lists.List; public class BubblesortListSorter implements ListSorter { private final Comparator _comparator; /** * Konstruktor * parametr: komparator określaj cy uporz dkowanie elementrw */ public BubblesortListSorter(Comparator comparator) { assert comparator != null : "nie określono komparatora"; _comparator = comparator; } ... } Teraz przed nami najważniejsze implementacja samego algorytmu sortowania bąbelko- wego. Jak pamiętamy, algorytm ten wymaga wielu przejść przez sortowaną listę; w wyniku każdego przejścia kolejny element w pobliżu końca listy ustawiany jest na swej właściwej pozycji. Wynika stąd, że dla N-elementowej listy po wykonaniu N 1 kroków na swych do- celowych pozycjach znajdzie się N 1 końcowych elementów, a więc także i element po- czątkowy, ergo liczba kroków potrzebnych do posortowania dowolnej listy jest o jeden mniejsza od liczby elementów zawartych w tej liście. Kod odpowiedzialny za powtarzanie wspomnianych kroków nazwiemy pętlą zewnętrzną (outer loop). W każdym kroku porównywane są pary sąsiadujących elementów; jeżeli względna kolej- ność elementów pary nie jest zgodna z kryterium określonym przez komparator, elementy zamieniane są miejscami ten cykl nazwiemy pętlą wewnętrzną (inner loop). Ponieważ w każdym kroku kolejny element końcowy ląduje na swej pozycji docelowej, liczba ele- mentów porównywanych w kolejnych krokach systematycznie się zmniejsza: w pierwszym kroku musimy wykonać N 1 porównań, w drugim N 2 itd. Wyjaśnia to warunek kontynu- owania pętli wewnętrznej left public List sort(List list) { assert list != null : "nie określono listy wejściowej"; int size = list.size(); for (int pass = 1; pass Rozdział 6. Sortowanie proste algorytmy 165 for (int left = 0; left int right = left + 1; if (_comparator.compare(list.get(left), list.get(right)) > 0) { swap(list, left, right); } } } return list; } Jak przed chwilą wspomnieliśmy, jeśli kolejność sąsiadujących elementów nie jest zgodna z kryterium określonym przez komparator, elementy te zamieniane są miejscami. Musimy więc dysponować metodą zamieniającą miejscami wartości elementów o wskazanych in- deksach. private void swap(List list, int left, int right) { Object temp = list.get(left); list.set(left, list.get(right)); list.set(right, temp); } Po zaimplementowaniu i (pomyślnym) przetestowaniu klasy BubblesortListSorter można celowo sprowokować załamanie testu, na przykład zmieniając wzorcową listę w taki spo- sób, by nie spełniała kryterium sortowania. Prędzej czy pózniej trzeba jednak zająć się ko- lejnym algorytmem sortowania. Wyobraz sobie książki o różnej wysokości, przypadkowo ułożono na półce, jak przedstawia to rysunek 6.6. Właśnie spodziewasz się odwiedzin mamy i chcesz jej zaimponować swo- ich zamiłowaniem do porządku domowego, postanawiasz więc poukładać książki według malejącej wysokości od lewej do prawej. Rysunek 6.6. Półka z losowo ustawionymi książkami 166 Algorytmy. Od podstaw Sortowanie bąbelkowe raczej się do tego nie nada, bo przestawianie sąsiednich par byłoby stratą czasu zamiana miejscami dwóch książek trwa bowiem znacznie dłużej niż porów- nanie ich wysokości. Zdecydowanie lepszą metodą na uzyskanie żądanego ułożenia książek będzie sortowanie przez wybieranie, zwane także sortowaniem przez selekcję (selectionsort). Znajdz na półce najwyższą książkę i zdejmij ją z półki. Powinieneś ją ustawić jako pierw- szą od lewej; zamiast przesuwać w prawo być może dużą liczbę innych książek, po prostu zamień ją z tą, która aktualnie znajduje się najbardziej na lewo (nie unikniesz całkowicie przesuwania książek, bowiem zapewne różnią się one od siebie grubością, ten szczegół nie ma jednak znaczenia w sytuacji, gdy zamiast książek sortowane są elementy listy). Opisana zamiana książek, zamiast przesuwania całej ich grupy, pozbawia sortowanie pewnej wła- sności zwanej stabilnością; zajmiemy się nią w rozdziale 7., na razie jest ona bez znacze- nia. Układ książek po pierwszej zamianie przedstawiony jest na rysunku 6.7. Rysunek 6.7. Najwyższa książka znajduje się już na skrajnej lewej pozycji Jak łatwo się domyślić, w kolejnym kroku należy odszukać najwyższą z pozostałych ksią- żek i zamienić ją miejscami z tą, która aktualnie zajmuje pozycję drugą od lewej. Efekt tej zamiany przedstawiony jest na rysunku 6.8. Rysunek 6.8. Druga co do wysokości książka znajduje się na właściwej pozycji Rozdział 6. Sortowanie proste algorytmy 167 Kontynuując konsekwentnie to postępowanie, wybieramy z nieposortowanej jeszcze grupy [ Pobierz całość w formacie PDF ] |