Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00339 005541 13607043 na godz. na dobę w sumie
Java. Zaawansowane zastosowania - ebook/pdf
Java. Zaawansowane zastosowania - ebook/pdf
Autor: Liczba stron: 320
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-246-9429-7 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> java - programowanie
Porównaj ceny (książka, ebook (-20%), audiobook).

Twój przewodnik w głąb języka Java!

Czy wiesz, jaki język programowania wybierany jest jako podstawa najbardziej skomplikowanych i zaawansowanych projektów IT? Tak, to Java! Sprawdza się doskonale wszędzie tam, gdzie wymagane są najwyższa wydajność, pełne bezpieczeństwo oraz realizacja skomplikowanych reguł biznesowych. Jeżeli chcesz zapoznać się z nietypowym i sprytnym wykorzystaniem tego języka, to trafiłeś na doskonałą książkę.

W trakcie lektury będziesz mieć niepowtarzalną okazję, by przygotować zaawansowane algorytmy oraz zaimplementować je z użyciem języka Java. Ponadto dogłębnie poznasz listy, stosy i kolejki oraz dowiesz się, jak efektywnie na nich operować. W kolejnych rozdziałach zaznajomisz się z technikami sortowania danych oraz generowania liczb losowych. Co jeszcze? Operacje na plikach, drzewa binarne oraz haszowanie to tylko niektóre z poruszanych tu tematów. Książka jest doskonałą lekturą dla wszystkich programistów języka Java, chcących wycisnąć z niego jeszcze więcej!

Dzięki tej książce:

Poznaj zaawansowane możliwości języka Java!

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

Tytuł oryginału: Advanced Topics in Java: Core Concepts in Data Structures Tłumaczenie: Piotr Rajca ISBN: 978-83-246-9426-6 Original edition copyright © 2014 by Noel Kalicharan. All rights reserved. Polish edition copyright © 2014 by HELION SA. All rights reserved. All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from the Publisher. Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną, fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym powoduje naruszenie praw autorskich niniejszej publikacji. Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi bądź towarowymi ich właścicieli. Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody wynikłe z wykorzystania informacji zawartych w książce. Wydawnictwo HELION ul. Kościuszki 1c, 44-100 GLIWICE tel. 32 231 22 19, 32 230 98 63 e-mail: helion@helion.pl WWW: http://helion.pl (księgarnia internetowa, katalog książek) Drogi Czytelniku! Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres http://helion.pl/user/opinie/javazz Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję. Printed in Poland. • Kup książkę • Poleć książkę • Oceń książkę • Księgarnia internetowa • Lubię to! » Nasza społeczność Spis tre(cid:258)ci Rozdzia(cid:239) 1. O autorach ...............................................................................................................9 Recenzenci techniczni ............................................................................................11 Wprowadzenie ......................................................................................................13 Sortowanie, przeszukiwanie i scalanie ..................................................................15 1.1. Sortowanie tablic: sortowanie przez wybieranie ...................................................................... 15 1.2. Sortowanie tablic: sortowanie przez wstawianie ...................................................................... 19 1.3. Wstawianie elementu w odpowiednim miejscu ...................................................................... 26 1.4. Sortowanie tablicy łańcuchów znaków ..................................................................................... 27 1.5. Sortowanie tablic równoległych ................................................................................................. 29 1.6. Wyszukiwanie binarne ................................................................................................................ 30 1.7. Przeszukiwanie tablicy łańcuchów znaków .............................................................................. 32 1.8. Przykład: zliczanie wystąpień wyrazów ..................................................................................... 34 1.9. Scalanie posortowanych list ........................................................................................................ 37 Ćwiczenia .............................................................................................................................................. 40 Rozdzia(cid:239) 2. Wprowadzenie do obiektów .................................................................................43 2.1. Obiekty ........................................................................................................................................... 44 2.2. Definiowanie klas i tworzenie obiektów ................................................................................... 44 2.3. Konstruktory ................................................................................................................................. 48 2.4. Hermetyzacja danych, metody akcesorów i mutatorów ......................................................... 51 2.5. Wyświetlanie danych obiektów .................................................................................................. 55 2.6. Klasa Part ....................................................................................................................................... 57 2.7. Jakie nazwy nadawać plikom źródłowym? ............................................................................... 59 2.8. Stosowanie obiektów .................................................................................................................... 60 2.9. Wskaźnik null ............................................................................................................................... 63 2.10. Przekazywanie obiektu jako argumentu ................................................................................. 64 2.11. Tablice obiektów ......................................................................................................................... 65 2.12. Przeszukiwanie tablicy obiektów ............................................................................................. 67 2.13. Sortowanie tablicy obiektów ..................................................................................................... 70 2.14. Zastosowanie klasy do grupowania danych: licznik występowania słów .......................... 71 2.15. Zwracanie więcej niż jednej wartości: głosowanie ................................................................. 74 Ćwiczenia .............................................................................................................................................. 80 Kup książkęPoleć książkę SPIS TRE(cid:165)CI Rozdzia(cid:239) 3. Rozdzia(cid:239) 4. Listy powi(cid:200)zane .....................................................................................................83 3.1. Definiowanie list powiązanych ................................................................................................... 83 3.2. Proste operacje na listach powiązanych .................................................................................... 85 3.3. Tworzenie listy powiązanej: dodawanie elementów na końcu listy ...................................... 88 3.4. Wstawianie elementów do list powiązanych ............................................................................ 91 3.5. Tworzenie listy powiązanej: dodawanie elementu na początku listy ................................... 93 3.6. Usuwanie elementów z list powiązanych .................................................................................. 94 3.7. Tworzenie posortowanej listy powiązanej ................................................................................ 95 3.8. Klasa listy powiązanej .................................................................................................................. 99 3.9. Jak zorganizować pliki źródłowe Javy? .................................................................................... 104 3.10. Rozszerzanie klasy LinkedList ................................................................................................ 106 3.11. Przykład: palindromy .............................................................................................................. 107 3.12. Zapisywanie listy powiązanej .................................................................................................. 111 3.13. Tablice a listy powiązane ......................................................................................................... 111 3.14. Przechowywanie list powiązanych przy użyciu tablic ......................................................... 112 3.15. Scalanie dwóch posortowanych list powiązanych ............................................................... 113 3.16. Listy cykliczne i dwukierunkowe ........................................................................................... 116 Ćwiczenia ............................................................................................................................................ 120 Stosy i kolejki ......................................................................................................123 4.1. Abstrakcyjne typy danych ......................................................................................................... 123 4.2. Stosy .............................................................................................................................................. 124 4.3. Ogólny typ Stack ......................................................................................................................... 130 4.4. Konwertowanie wyrażenia z zapisu wrostkowego na przyrostkowy .................................. 134 4.5. Kolejki .......................................................................................................................................... 142 Ćwiczenia ............................................................................................................................................ 151 Rozdzia(cid:239) 5. Rekurencja ...........................................................................................................153 5.1. Definicje rekurencyjne ............................................................................................................... 153 5.2. Pisanie funkcji rekurencyjnych w języku Java ....................................................................... 154 5.3. Konwersja liczby dziesiątkowej na dwójkową przy użyciu rekurencji ............................... 156 5.4. Wyświetlanie listy powiązanej w odwrotnej kolejności ........................................................ 159 5.5. Problem wież Hanoi ................................................................................................................... 160 5.6. Funkcja podnosząca liczbę do potęgi ...................................................................................... 162 5.7. Sortowanie przez scalanie .......................................................................................................... 163 5.8. Zliczanie organizmów ................................................................................................................ 166 5.9. Odnajdywanie drogi przez labirynt ......................................................................................... 170 Ćwiczenia ............................................................................................................................................ 174 Liczby losowe, gry i symulacje ............................................................................177 6.1. Liczby losowe .............................................................................................................................. 177 6.2. Liczby losowe i pseudolosowe .................................................................................................. 178 6.3. Komputerowe generowanie liczb losowych ........................................................................... 179 6.4. Zgadywanka ................................................................................................................................. 180 6.5. Ćwiczenia z dodawania .............................................................................................................. 181 6.6. Gra Nim ....................................................................................................................................... 182 6.7. Rozkłady nierównomierne ........................................................................................................ 186 6.8. Symulowanie realnych problemów .......................................................................................... 189 6.9. Symulacja kolejki ........................................................................................................................ 190 6.10. Szacowanie wartości liczbowych przy użyciu liczb losowych ............................................ 193 Ćwiczenia ............................................................................................................................................ 196 Rozdzia(cid:239) 6. 6 Kup książkęPoleć książkę SPIS TRE(cid:165)CI Rozdzia(cid:239) 7. Praca z plikami ....................................................................................................199 7.1. Operacje wejścia-wyjścia w Javie .............................................................................................. 199 7.2. Pliki tekstowe i binarne ............................................................................................................. 200 7.3. Wewnętrzne i zewnętrzne nazwy plików ................................................................................ 200 7.4. Przykład: porównywanie dwóch plików ................................................................................. 201 7.5. Konstrukcja try…catch .............................................................................................................. 202 7.6. Operacje wejścia-wyjścia na plikach binarnych ..................................................................... 205 7.7. Pliki o dostępie swobodnym ..................................................................................................... 209 7.8. Pliki indeksowane ....................................................................................................................... 213 7.9. Aktualizacja pliku o dostępie swobodnym ............................................................................. 221 Ćwiczenia ............................................................................................................................................ 224 Rozdzia(cid:239) 8. Wprowadzenie do zagadnie(cid:241) drzew binarnych ...................................................225 8.1. Drzewa ......................................................................................................................................... 225 8.2. Drzewa binarne ........................................................................................................................... 227 8.3. Przechodzenie drzew binarnych .............................................................................................. 228 8.4. Sposoby reprezentacji drzew binarnych ................................................................................. 231 8.5. Budowanie drzewa binarnego .................................................................................................. 233 8.6. Binarne drzewa poszukiwań ..................................................................................................... 237 8.7. Budowanie binarnego drzewa poszukiwań ............................................................................ 240 8.8. Budowanie drzew binarnych ze wskaźnikami rodzica ......................................................... 244 8.9. Przechodzenie drzewa poziomami .......................................................................................... 249 8.10. Użyteczne funkcje operujące na drzewach binarnych ........................................................ 254 8.11. Usuwanie wierzchołków z binarnego drzewa poszukiwań ................................................ 255 8.12. Tablice jako sposób reprezentacji drzew binarnych ........................................................... 257 Ćwiczenia ............................................................................................................................................ 260 Zaawansowane metody sortowania ....................................................................263 9.1. Sortowanie przez kopcowanie .................................................................................................. 263 9.2. Budowanie kopca przy użyciu metody siftUp ........................................................................ 269 9.3. Analiza algorytmu sortowania przez kopcowanie ................................................................. 272 9.4. Kopce i kolejki priorytetowe ..................................................................................................... 273 9.5. Sortowanie listy elementów przy użyciu sortowania szybkiego .......................................... 274 9.6. Sortowanie Shella (z użyciem malejących odstępów) ........................................................... 284 Ćwiczenia ............................................................................................................................................ 288 Rozdzia(cid:239) 10. Haszowanie .........................................................................................................291 10.1. Podstawy haszowania .............................................................................................................. 291 10.2. Rozwiązanie problemu wyszukiwania i wstawiania przy użyciu haszowania ................. 292 10.3. Rozwiązywanie kolizji .............................................................................................................. 297 10.4. Przykład: licznik występowania słów .................................................................................... 307 Ćwiczenia ............................................................................................................................................ 310 Skorowidz ............................................................................................................313 Rozdzia(cid:239) 9. 7 Kup książkęPoleć książkę SPIS TRE(cid:165)CI 8 Kup książkęPoleć książkę R O Z D Z I A (cid:146) 9 (cid:132) (cid:132) (cid:132) Zaawansowane metody sortowania W tym rozdziale wyjaśnimy takie zagadnienia jak: (cid:120) sterta oraz algorytm sortowania przez kopcowanie przy użyciu metody siftDown, (cid:120) tworzenia kopca za pomocą metody siftUp, (cid:120) analiza wydajności algorytmu sortowania przez kopcowanie, (cid:120) użycie kopca w celu implementacji kolejki priorytetowej, (cid:120) sortowanie listy elementów z wykorzystaniem algorytmu sortowania szybkiego, (cid:120) odnajdywanie k-tego najmniejszego elementu listy, (cid:120) sortowanie listy elementów z zastosowaniem algorytmu sortowania Shella (z użyciem malejących odstępów). W rozdziale 1. przedstawiono dwie proste metody sortowania (sortowanie przez wybieranie oraz przez wstawianie), pozwalające na sortowanie listy elementów. W tym rozdziale dokładnie przeanalizujemy kilka innych, bardziej wydajnych metod sortowania — sortowanie przez kopcowanie (ang. heapsort), sortowanie szybkie (ang. quicksort) oraz sortowanie Shella (ang. shellsort). 9.1. Sortowanie przez kopcowanie Sortowanie przez kopcowanie (ang. heapsort) to algorytm sortowania, który interpretuje elementy w tablicy jako prawie kompletne drzewo binarne. Przeanalizujmy następującą tablicę, którą należy posortować w kolejności rosnącej. Taką tablicę możemy potraktować jako prawie kompletne drzewo binarne składające się z 12 wierzchołków, które zostało przedstawione na rysunku 9.1. Załóżmy, że teraz postawimy wymóg, by wartości w każdym z wierzchołków były większe lub równe wartościom w lewym i prawym poddrzewie; zakładamy przy tym, że nie są one puste. Krótko mówiąc, zobaczymy, w jaki sposób można przeorganizować wierzchołki tak, by każdy z nich spełniał tę właściwość. Zanim to zrobimy, nadamy takiej strukturze danych nazwę kopca. Kup książkęPoleć książkę JAVA. ZAAWANSOWANE ZASTOSOWANIA Rysunek 9.1. Zawartość tablicy przedstawiona w formie drzewa binarnego Kopcem nazywamy prawie kompletne drzewo binarne, takie że wartość korzenia tego drzewa jest większa lub równa wartościom jego lewego i prawego dziecka, a prawe i lewe poddrzewo także są kopcami. Natychmiastową konsekwencją takiej definicji jest to, że największa wartość w drzewie znajduje się w jego korzeniu. Taki kopiec jest nazywamy kopcem maksymalnym (ang. max-heap). W podobny sposób możemy zdefiniować kopiec minimalny — wystarczy zamienić relację większości na relację mniejszości. A zatem w kopcu minimalnym jego korzeń zawiera wartość najmniejszą. Spróbujmy teraz zmodyfikować drzewo binarne z rysunku 9.1, by stało się kopcem maksymalnym. 9.1.1. Konwersja drzewa binarnego w kopiec maksymalny Najpierw należy zauważyć, że wszystkie liście są kopcami, gdyż nie mają żadnych dzieci. Zaczynając od ostatniego wierzchołka, który nie jest liściem (w naszym przykładzie jest to wierzchołek numer 6), przekształcimy drzewo, którego jest on korzeniem, w kopiec maksymalny. Jeśli wartość wierzchołka jest większa od wartości jego dzieci, nie musimy nic robić. Tak właśnie jest w przypadku wierzchołka 6., gdyż 84 jest większe od 32. Następnie przechodzimy do wierzchołka o numerze 5. W jego przypadku wartość 48 jest mniejsza od wartości przynajmniej jednego dziecka (w właściwie, od obu dzieci, gdyż ich wartości wynoszą odpowiednio 56 i 69). Najpierw znajdujemy większe dziecko (69) i zamieniamy jego zawartość z zawartością wierzchołka 5. W efekcie liczba 69 zostaje zapisana w wierzchołku 5., a liczba 48 w wierzchołku 11. Następnie przechodzimy do wierzchołka 4. Większe z jego dzieci, 79, zostaje przeniesione do wierzchołka 4., a 65 do wierzchołka 9. Po zakończeniu tego etapu prac drzewo ma postać przedstawioną na rysunku 9.2. Rysunek 9.2. Drzewo po przetworzeniu wierzchołków 6., 5. oraz wierzchołka numer 4 264 Kup książkęPoleć książkę ROZDZIA(cid:146) 9. (cid:132) ZAAWANSOWANE METODY SORTOWANIA Teraz przechodzimy do wierzchołka 3. W jego przypadku konieczne jest przeniesienie liczby 43. Większą z wartości dzieci tego wierzchołka jest 84, zatem zamieniamy wartości w wierzchołkach 3. i 6. Aktualna wartość wierzchołka 6. (43) jest większa od wartości jego dziecka (32), więc nie musimy robić nic więcej. Trzeba jednak zwrócić uwagę, że gdyby wartością wierzchołka 6. była liczba (przykładowo) 28, musielibyśmy zamienić ją miejscami z liczbą 32. Po przejściu do wierzchołka 2. okazuje się, że konieczne jest zamienienie umieszczonej w nim liczby 28 z wartością większego z dzieci, czyli liczbą 79. Kiedy to zrobimy, liczba 25 umieszczona w wierzchołku 4. będzie mniejsza od liczby 65 w jego prawym dziecku, czy wierzchołku numer 9. Zatem także te dwie liczby należy zamienić miejscami. I w końcu, po przejściu do wierzchołka 1. zamieniamy jego zawartość, 37, z zawartością większego z jego dzieci, czyli z liczbą 84. Następnie jest ona dalej zamieniana z (nowym) większym dzieckiem zawierającym liczbę 73. W ten sposób drzewo staje się kopcem, a jego ostateczną postać przedstawiono na rysunku 9.3. Rysunek 9.3. Ostateczna postać drzewa, które już jest kopcem 9.1.2. Proces sortowania Warto zwrócić uwagę, że po przekształceniu w kopiec korzeń drzewa zawiera największą z jego wartości, 84. Skoro wartości zapisane w tablicy tworzą kopiec, zatem teraz możemy je posortować w kolejności rosnącej. Oto sposób, w jaki należy to zrobić. (cid:120) Musimy zapisać ostatni element, czyli 32, w jakimś tymczasowym miejscu i przenieść liczbę 84 na ostatnie miejsce (do wierzchołka numer 12), zwalniając tym samym wierzchołek numer 1. Teraz musimy wyobrazić sobie, że liczba 32 znajduje się w wierzchołku 1. i przenieść ją tak, by elementy tablicy z zakresu od 1 do 11 tworzyły kopiec. Można to zrobić w następujący sposób. (cid:120) 32 jest zamieniane z większym z jego dzieci, czyli liczbą 79, która zostaje przeniesiona do wierzchołka 1. Liczba 32 jest dalej zamieniana z jej (nowym) większym dzieckiem, którym jest liczba 69; co sprawia, że liczba 32 trafia do wierzchołka 2. W końcu liczba 32 zostaje zamieniona z liczbą 56, co sprawia, że drzewo przyjmuje postać przedstawioną na rysunku 9.4. Rysunek 9.4. Postać drzewa po umieszczeniu wartości 84 w odpowiednim miejscu i zreorganizowaniu drzewa 265 Kup książkęPoleć książkę JAVA. ZAAWANSOWANE ZASTOSOWANIA Na tym etapie sortowania druga największa liczba, 79, znajduje się w wierzchołku 1. Umieszczamy ją zatem w wierzchołku 11., a liczba 48 zostaje „przesiana w dół” z wierzchołka 1., tak by wierzchołki od 1. do 10. tworzyły kopiec. Teraz trzecią co do wielkości liczbą umieszczoną w drzewie jest 73, liczba ta znajduje się w jego korzeniu. W kolejnym etapie sortowania umieszczamy ją w wierzchołku 10. itd. Taki proces jest kontynuowany, aż do momentu posortowania całej tablicy. Po początkowym utworzeniu kopca proces jego sortowania można opisać, posługując się pseudokodem, w następujący sposób. for k = n downto 2 do item = num[k] // pobieramy aktualnie ostatni element num[k] = num[1] // przenosimy wierzchołek kopca do jego ostatniego wierzchołka siftDown(item, num, 1, k-1) // odtwarzamy właściwości kopca w zakresie od 1 do k–1 endfor Przy czym metoda siftDown(item, num, 1, k-1) przyjmuje, że spełnione są następujące założenia: (cid:120) element num[1] jest pusty, (cid:120) elementy num[2] do num[k-1] tworzą kopiec. Zaczynamy od pozycji numer 1: wartość item jest wstawiana w taki sposób, że num[1] do num[k-1] tworzą kopiec. W opisanym powyżej procesie sortowania podczas każdej iteracji pętli wartość z aktualnie ostatniej pozycji (k) jest zapisywana w zmiennej item. Wartość z wierzchołka 1. jest przenoszona na pozycję k, wierzchołek 1. zostanie opróżniony (i dostępny), a wszystkie wierzchołki z zakresu od 2 do k-1 spełniają warunek kopca. Wywołanie siftDown(item, num, 1, k-1) doda wartość w zmiennej item do tablicy w taki sposób, że elementy num[1] do num[k-1] będą tworzyć kopiec. Dzięki temu zapewnimy, że kolejna największa wartość w kopcu znajdzie się w wierzchołku 1. Bardzo użyteczną cechą metody siftDown (kiedy już ją napiszemy) będzie to, że przy jej użyciu będziemy w stanie utworzyć początkowy kopiec z przekazanej tablicy. Przypomnijmy sobie proces tworzenia kopca opisany w punkcie 9.1.1. Dla każdego wierzchołka (dajmy na to h) „przesiewamy wartość w dół”, tak by utworzyć kopiec o korzeniu w wierzchołku h. Aby zastosować metodę siftDown w obecnej sytuacji, musimy uogólnić ją w następujący sposób: void siftDown(int key, int num[], int root, int last) Metoda ta zakłada, że spełnione są następujące warunki: (cid:120) element num[root] jest pusty, (cid:120) indeks last wskazuje ostatni element tablicy num, (cid:120) element num[root*2], jeśli istnieje (root*2 ≤ last), jest korzeniem kopca, (cid:120) element num[root*2+1], jeśli istnieje (root*2+1 ≤ last), jest korzeniem kopca. Zaczynamy od elementu o indeksie root: wartość key jest wstawiana do tablicy num w taki sposób, że num[root] będzie korzeniem kopca. następującym pseudokodem. Dysponując tablicą wartości num[1] do num[n], możemy utworzyć kopiec, postępując w sposób opisany for h = n/2 downto 1 do // n/2 jest ostatnim wierzchołkiem, który nie jest liściem siftDown(num[h], num, h, n); Teraz zajmiemy się napisaniem metody siftDown. Przeanalizujmy kopiec przedstawiony na rysunku 9.5. 266 Kup książkęPoleć książkę ROZDZIA(cid:146) 9. (cid:132) ZAAWANSOWANE METODY SORTOWANIA Rysunek 9.5. Kopiec, z wyjątkiem wierzchołków o numerach 1 i 2 Wszystkie wierzchołki, z wyjątkiem 1. i 2., spełniają warunki kopca, czyli są większe od swoich dzieci lub im równe. Załóżmy, że chcemy sprawić, by wierzchołek 2. stał się korzeniem kopca. Aktualnie umieszczona w nim liczba 25 jest mniejsza od jego dzieci (którymi są liczby 79 i 69). Chcemy zatem napisać metodę siftDown tak, by poniższe wywołanie doprowadziło do utworzenia kopca: siftDown(26, num, 2, 12) W powyższym wywołaniu 25 jest wartością parametru key, num jest tablicą, 2 jest indeksem korzenia, a 12 indeksem ostatniego przetwarzanego elementu tablicy. Po zakończeniu wywołania każdy z wierzchołków, od 2. do 12., będzie korzeniem kopca, a następujące wywołanie sprawi, że cała tablica będzie kopcem: siftDown(37, num, 1, 12) Zarys działania metody siftDown można opisać w następujący sposób. znajdujemy wi(cid:218)ksze z dzieci wierzcho(cid:239)ka num[root]; //załóżmy, że jest to wierzchołek m if (key = num[m]) gotowe; zapisujemy key w num[root] //wartość key jest mniejsza od większego z dzieci zapisujemy num[m] w num[root] // wybieramy większe z dzieci ustawiamy root na m Ten proces jest powtarzamy tak długo, jak długo wartość wierzchołka root jest większa od wartości jego dzieci bądź też wierzchołek ten nie będzie mieć dzieci. Poniżej przedstawiono kod metody siftDown. public static void siftDown(int key, int[] num, int root, int last) { int bigger = 2 * root; while (bigger = last) { //dopóki jest co najmniej jedno dziecko if (bigger last) //istnieje także prawe dziecko; znajdujemy większe if (num[bigger+1] num[bigger]) bigger++; // bigger zawiera indeks większego dziecka if (key = num[bigger]) break; //wartość key jest mniejsza; wybieramy num[bigger] num[root] = num[bigger]; root = bigger; bigger = 2 * root; } num[root] = key; } //koniec siftDown Teraz możemy już napisać kod metody heapSort; oto on. public static void heapSort(int[] num, int n) { //sortujemy zakres tablicy od num[1] do num[n] //przekształcamy tablicę w kopiec 267 Kup książkęPoleć książkę JAVA. ZAAWANSOWANE ZASTOSOWANIA for (int k = n / 2; k = 1; k--) siftDown(num[k], num, k, n); for (int k = n; k 1; k--) { int item = num[k]; //pobieramy aktualnie ostatni element num[k] = num[1]; //przenosimy wierzchołek kopca do ostatniego elementu siftDown(item, num, 1, k-1); //odtwarzamy warunek kopca w zakresie od 1 do k–1 } } //koniec heapSort Działanie metody heapSort możemy sprawdzić przy użyciu programu P9.1. Program P9.1 import java.io.*; public class HeapSortTest { public static void main(String[] args) throws IOException { int[] num = {0, 37, 25, 43, 65, 48, 84, 73, 18, 79, 56, 69, 32}; int n = 12; heapSort(num, n); for (int h = 1; h = n; h++) System.out.printf( d , num[h]); System.out.printf( \n ); } public static void heapSort(int[] num, int n) { //sortujemy zakres tablicy od num[1] do num[n] //przekształcamy tablicę w kopiec for (int k = n / 2; k = 1; k--) siftDown(num[k], num, k, n); for (int k = n; k 1; k--) { int item = num[k]; //pobieramy aktualnie ostatni element num[k] = num[1]; //przenosimy wierzchołek kopca do ostatniego elementu siftDown(item, num, 1, k-1); //odtwarzamy warunek kopca w zakresie od 1 do k–1 } } //koniec heapSort public static void siftDown(int key, int[] num, int root, int last) { int bigger = 2 * root; while (bigger = last) { //dopóki jest co najmniej jedno dziecko if (bigger last) //istnieje także prawe dziecko; znajdujemy większe if (num[bigger+1] num[bigger]) bigger++; // bigger zawiera indeks większego dziecka if (key = num[bigger]) break; //wartość key jest mniejsza; wybieramy num[bigger] num[root] = num[bigger]; root = bigger; bigger = 2 * root; } num[root] = key; } //koniec siftDown } //koniec klasy HeapSortTest Po uruchomieniu program P9.1 wygeneruje następujące wyniki (elementy num[1] do num[12] zostaną posortowane). 18 25 32 37 43 48 56 65 69 73 79 84 268 Kup książkęPoleć książkę ROZDZIA(cid:146) 9. (cid:132) ZAAWANSOWANE METODY SORTOWANIA Uwaga programistyczna: w przedstawionej postaci metoda heapSort sortuje tablicę, przy założeniu, że n elementów zostało zapisanych w niej, zaczynając od indeksu 1 do n. Gdyby wartości miały być zapisywane w komórkach o indeksach od 0 do n-1, konieczne byłoby wprowadzenie stosownych zmian, odpowiadających następującym obserwacjom. (cid:120) Korzeniem drzewa jest element num[0]. (cid:120) Lewym dzieckiem wierzchołka h jest wierzchołek 2h+1, jeśli 2h+1 n. (cid:120) Prawym dzieckiem wierzchołka h jest wierzchołek 2h+2, jeśli 2h+2 n. (cid:120) Rodzicem wierzchołka h jest wierzchołek (h-1)/2 (przy czym jest to dzielenie całkowite). (cid:120) Ostatnim wierzchołkiem, który nie jest liściem, jest wierzchołek (n-2)/2 (przy czym jest to dzielenie całkowite). Wszystkie te obserwacje można zweryfikować, analizując drzewo (n = 12) przedstawione na rysunku 9.6. Rysunek 9.6. Drzewo binarne zapisane w tablicy zaczyna się od elementu o indeksie 0 Zachęcamy do napisania metody heapSort w taki sposób, by sortowała tablicę w zakresie num[0..n-1]. W ramach podpowiedzi należy zwrócić uwagę, że jedyną zmianą, jaką trzeba w tym celu wprowadzić w kodzie metody siftDown, jest sposób obliczania wartości zmiennej bigger — zamiast 2 * root należy użyć wyrażenia 2 * root + 1. 9.2. Budowanie kopca przy u(cid:285)yciu metody siftUp Przeanalizujmy problem dodawania nowego wierzchołka do istniejącego kopca. Konkretnie rzecz biorąc, załóżmy, że elementy tablicy num[1] do num[n] zawierają kopiec. Chcemy dodać do niego nową liczbę newKey, w taki sposób, by num[1] do num[n+1] tworzyły kopiec zawierający wartość newKey. Zakładamy przy tym, że tablica zawierająca kopiec jest na tyle duża, by można w niej umieścić nowy klucz. Załóżmy np., że dysponujemy kopcem przedstawionym na rysunku 9.7 i chcemy dodać do niego liczbę 40. Po dodaniu kolejnej liczby tablica będzie zawierać 13 elementów. Przyjmujemy, że liczba 40 została początkowo umieszczona w komórce num[13] (jednak na razie jeszcze jej nie zapisujemy w komórce) i porównujemy ją z rodzicem, czyli liczbą 43 umieszczoną w komórce num[6]. Ponieważ 40 jest mniejsze od 43, zatem warunek kopca jest spełniony, a my możemy umieścić nową liczbę w komórce num[13], co zakończy proces dodawania. Załóżmy jednak, że chcemy dodać do kopca liczbę 80. Ponownie wyobrażamy sobie, że umieszczamy ją w komórce num[13] (choć jeszcze tego nie robimy) i porównujemy z rodzicem, czyli komórką num[6] zawierającą wartość 43. Ponieważ 80 jest większe od 43, zatem przenosimy 43 do num[13] i wyobrażamy sobie, że zapisujemy liczbę 80 w komórce num[6]. Następnie porównujemy 80 z wartością nowego rodzica — wartością komórki num[3] — czyli z liczbą 73. Ponieważ 80 jest większe, zatem przenosimy 43 do komórki num[6] i wyobrażamy sobie, że zapisujemy 80 w komórce num[3]. 269 Kup książkęPoleć książkę JAVA. ZAAWANSOWANE ZASTOSOWANIA Rysunek 9.7. Kopiec, do którego dodamy nowy element W końcu porównujemy 80 z wartością nowego rodzica — wartością komórki num[1] — czyli z liczbą 84. Ponieważ liczba 80 jest mniejsza, zatem zapisujemy ją w num[3] i przetwarzanie zostaje zakończone. Należy zwrócić uwagę, że gdybyśmy do kopca dodawali liczbę 90, wartość 84 zostałaby przeniesiona do komórki num[3], a 90 została zapisana w komórce num[1]. W ten sposób nowy element stanie się największą wartością kopca. Na rysunku 9.8 przedstawiono kopiec po dodaniu do niego liczby 80. Rysunek 9.8. Kopiec po dodaniu liczby 80 Poniższy kod pozwala dodać wartość newKey do kopca zapisanego w tablicy num, w zakresie num[1] do num[n]. child = n + 1; parent = child / 2; while (parent 0) { if (newKey = num[parent]) break; num[child] = num[parent]; //przenosimy rodzica w dół child = parent; parent = child / 2; } num[child] = newKey; n = n + 1; Opisany powyżej proces jest zazwyczaj określany jako przesiewanie w górę (ang. sifting up). Możemy przepisać go w formie metody siftUp. Zakładamy, że do metody będzie przekazywana tablica heap[1..n], taka że heap[1..n-1] zawiera kopiec, a heap[n] zawiera element do „przesiania w górę”. W efekcie metoda ma zapewnić, że tablica heap[1..n] będzie zawierać kopiec. Innymi słowy, element heap[n] pełni rolę zmiennej newKey z powyższych rozważań. Kod metody siftUp przedstawimy jako fragment programu P9.2, który tworzy kopiec na podstawie liczb odczytywanych z pliku heap.in. 270 Kup książkęPoleć książkę ROZDZIA(cid:146) 9. (cid:132) ZAAWANSOWANE METODY SORTOWANIA Program P9.2 import java.io.*; import java.util.*; public class SiftUpTest { final static int MaxHeapSize = 100; public static void main (String[] args) throws IOException { Scanner in = new Scanner(new FileReader( heap.in )); int[] num = new int[MaxHeapSize + 1]; int n = 0, number; while (in.hasNextInt()) { number = in.nextInt(); if (n MaxHeapSize) { //sprawdzamy, czy tablica jest dostatecznie duża num[++n] = number; siftUp(num, n); } } for (int h = 1; h = n; h++) System.out.printf( d , num[h]); System.out.printf( \n ); in.close(); } //koniec main public static void siftUp(int[] heap, int n) { //heap[1] do heap[n–1] zawiera kopiec //przesiewamy wartość heap[n] w górę kopca, tak by heap[1..n] zawierała kopiec int siftItem = heap[n]; int child = n; int parent = child / 2; while (parent 0) { if (siftItem = heap[parent]) break; heap[child] = heap[parent]; //przenosimy rodzica w dół child = parent; parent = child / 2; } heap[child] = siftItem; } //koniec siftUp } //koniec klasy SiftUpTest Załóżmy, że plik heap.in zawiera następujące liczby: 37 25 43 65 48 84 73 18 79 56 69 32 Program P9.2 zbuduje kopiec (opisany poniżej) i wyświetli następujące wyniki. 84 79 73 48 69 37 65 18 25 43 56 32 Po wczytaniu liczb 37, 25 oraz 43 kopiec będzie miał postać przedstawioną na rysunku 9.9. Rysunek 9.9. Kopiec po przetworzeniu liczb 37, 25 i 43 271 Kup książkęPoleć książkę JAVA. ZAAWANSOWANE ZASTOSOWANIA Po wczytaniu kolejnych liczb, takich jak 65, 48, 84 i 73, kopiec przyjmie postać przedstawioną na rysunku 9.10. Rysunek 9.10. Kopiec po przetworzeniu liczb 65, 48, 84 i 73 Po wczytaniu kolejnych liczb, 18, 79, 56, 69 i 32, kopiec przyjmie postać przedstawioną na rysunku 9.11. Rysunek 9.11. Ostateczna postać kopca po przetworzeniu liczb 18, 79, 56, 69 i 32 Warto zwrócić uwagę, że kopiec z rysunku 9.11 jest inny niż przedstawiony na rysunku 9.3, choć oba zostały utworzone na podstawie tych samych liczb. Nie zmieniło się jednak to, że największa z liczb umieszczonych w kopcu, czyli 84, znajduje się w jego korzeniu. Jeśli wartości zostały już zapisane w tablicy num[1..n], możemy przekształcić je w kopiec, używając następującego wywołania: for (int k = 2; k = n; k++) siftUp(num, k); 9.3. Analiza algorytmu sortowania przez kopcowanie Która z metod, siftUp czy siftDown, lepiej nadaje się do tworzenia kopca? Trzeba pamiętać, że w większości przypadków liczba przesunięć wierzchołka wyniesie log2n. W metodzie siftDown przetwarzamy n/2 wierzchołków i w ramach każdego etapu wykonujemy dwa porównania: jedno, by znaleźć większe dziecko, i drugie, by porównać je z wartością wierzchołka. Uproszczona analiza pokazuje, że w najgorszym przypadku będziemy musieli wykonać 2*n/2*log2n = nlog2n porównań. Jednak nieco bardziej dokładna analiza pozwala wykazać, że konieczne będzie wykonanie co najwyżej 4n porównań. W metodzie siftUp przetwarzamy n–1 wierzchołków. W każdym z etapów wykonujemy jedno porównanie: wierzchołka z jego rodzicem. Uproszczona analiza pokazuje, że w najgorszym przypadku wykonamy (n–1)log2n porównań. Może się jednak zdarzyć, że wszystkie węzły będą musiały przebyć całą drogę, aż do korzenia drzewa. W takim przypadku mamy n/2 wierzchołków, które muszą przebyć drogę o długości log2n, co daje łączną liczbę (n/2)log2n porównań. A powyższe rozważania dotyczą wyłącznie liści. Ostatecznie szczegółowa analiza pokazuje, że łączna liczba porównań wykonywanych przez metodę siftUp wynosi w przybliżeniu nlog2n. 272 Kup książkęPoleć książkę ROZDZIA(cid:146) 9. (cid:132) ZAAWANSOWANE METODY SORTOWANIA Ta różnica w wydajności jest związana z faktem, że w metodzie siftDown nie trzeba wykonywać żadnych operacji dla połowy wierzchołków (liści), natomiast metoda siftUp właśnie dla tych wierzchołków musi wykonać większość operacji. Niezależnie od tego, której metody użyjemy do utworzenia początkowego kopca, algorytm sortowania przez kopcowanie posortuje tablicę o wielkości n, wykonując przy tym co najwyżej 2nlog2n porównań oraz nlog2n operacji przypisania. To bardzo szybki algorytm. Co więcej, jest to algorytm stabilny, w tym znaczeniu, że jego najgorsza wydajność zawsze wynosi 2nlog2n, niezależnie od początkowej kolejności elementów w tablicy. Aby unaocznić, jak szybkie jest sortowanie przez kopcowanie (oraz wszystkie inne algorytmy sortowania o złożoności rzędu O(nlog2n), takie jak sortowanie szybkie lub sortowanie przez scalanie), porównajmy go z algorytmem sortowania przez wybieranie, który podczas sortowania tablicy n-elementowej wykonuje około 1/2n2 porównań. Wyniki tego porównania przedstawiono w tabeli 9.1. Tabela 9.1. Porównanie sortowania przez kopcowanie z sortowaniem przez wybieranie wybieranie (w sekundach) 0,005 0,5 50 5000 500 000 wybieranie (porówn.) 5000 500 000 50 000 000 5 000 000 000 500 000 000 000 kopcowanie (w sekundach) 0,001 0,020 0,266 3,322 39,863 kopcowanie (porówn.) 1329 19 932 265 754 3 321 928 39 863 137 1 000 000 100 000 10 000 n 100 1000 W drugiej oraz trzeciej kolumnie pokazano liczbę porównań, które należy wykonać. Z kolei w ostatnich dwóch kolumnach przedstawiono czasy wykonania każdej z metod (wyrażone w sekundach), przy założeniu, że komputer jest w stanie wykonać milion porównań na sekundę. Aby np. posortować milion elementów, sortowanie przez wybieranie będzie potrzebować 500 tysięcy sekund (prawie 6 dni!), natomiast sortowanie przez kopcowanie poradzi sobie z tym w ciągu niespełna 40 sekund. 9.4. Kopce i kolejki priorytetowe Kolejka priorytetowa to kolejka, w której poszczególnym elementom są przypisywane pewne „priorytety” określające położenie danego elementu w kolejce. Element z najwyższym priorytetem jest umieszczany na początku kolejki. Poniżej przedstawiono kilka typowych operacji wykonywanych na kolejkach priorytetowych. (cid:120) Usunięcie (udostępnienie) elementu o najwyższym priorytecie. (cid:120) Dodanie elementu o podanym priorytecie. (cid:120) Usunięcie (usunięcie bez udostępniania) elementu z kolejki. (cid:120) Zmiana priorytetu elementu i aktualizacja jego położenia zgodnie z nowym priorytetem. Priorytet możemy sobie wyobrazić jako liczbę całkowitą — im wyższa liczba, tym wyższy priorytet. Od razu możemy zgadnąć, że jeśli zaimplementujemy taką kolejkę jako kopiec maksymalny, element o najwyższym priorytecie znajdzie się w jego korzeniu, dzięki czemu bardzo łatwo będzie można go usunąć. Reorganizacja kopca będzie wymagać „przesiania w dół” ostatniego elementu z korzenia kopca. Dodanie nowego elementu będzie wymagać umieszczenia go za aktualnie ostatnim elementem kopca i przesiania w górę, aż do momentu określenia właściwego położenia. Aby usunąć z kolejki dowolny element, konieczna będzie znajomość jego położenia. Sam proces usunięcia będzie polegał na zamienieniu usuwanego elementu z aktualnie ostatnim elementem kopca, a następnie przesianiu go w górę, aż do określenia właściwego położenia. W efekcie kopiec zmniejszy się o jeden element. 273 Kup książkęPoleć książkę JAVA. ZAAWANSOWANE ZASTOSOWANIA Jeśli zmienimy priorytet elementu, może się okazać, że konieczne jest przesianie go w górę lub w dół, w celu umieszczenia w odpowiednim położeniu. Oczywiście, w zależności od zmiany, może się okazać, że element pozostanie w swoim oryginalnym położeniu. W wielu sytuacjach (np. w kolejkach zadań stosowanych w systemach wielozadaniowych) priorytet zadania może się zwiększać z upływem czasu, dzięki czemu w końcu zostanie ono wykonane. W takich sytuacjach po każdej zmianie priorytetu zadanie jest przesuwane coraz bliżej korzenia kopca; jak można się domyślić, wymaga to jedynie przesiania elementów w górę. W typowych rozwiązaniach informacje o elementach kolejki priorytetowej są przechowywane w innej strukturze danych, w której można je łatwo odnaleźć, np. w drzewie binarnym. Jedno pole wierzchołka będzie zawierać indeks elementu tablicy używanej do przechowywania kolejki priorytetowej. Kontynuując przykład priorytetowej kolejki zadań, załóżmy, że chcemy dodać do niej nowy element. Możemy przeszukać drzewo na podstawie np. numeru zadania i dodać dany element do drzewa. Wartość jego priorytetu posłuży do określenia miejsca w kolejce, w którym zadanie będzie umieszczone. Położenie to zostanie następnie zapisane w wierzchołku drzewa. Jeśli później priorytet zadania ulegnie zmianie, zmienione zostanie także położenie zadania w kolejce, a jego nowe położenie ponownie będzie zapisane w wierzchołku drzewa. Warto zwrócić uwagę, że zmiana położenia tego elementu może także powodować zmianę położenia innych elementów w kolejce (które będą przesuwane w górę lub w dół kopca), zatem także dla tych elementów konieczne będzie przeprowadzenie aktualizacji drzewa. 9.5. Sortowanie listy elementów przy u(cid:285)yciu sortowania szybkiego U podstaw algorytmu sortowania szybkiego (ang. quicksort) leży idea podziału listy na dwie części, względem pewnego, wybranego elementu, nazywanego elementem rozdzielającym (ang. pivot). Załóżmy np., że naszym zadaniem jest posortowanie następującej tablicy liczb. Taką tablicę możemy podzielić względem pierwszej wartości, 53. Oznacza to umieszczenie wartości 53 w takim miejscu, że wszystkie wartości znajdujące się w tablicy na lewo od niej będą mniejsze, a znajdujące się na prawo będą od niej większe lub jej równe. Innymi słowy, algorytm podziału tablicy num opiszemy w następujący sposób. Wartość 53 służy jako element rozdzielający. Zostaje umieszczona w komórce o numerze 6. Wszystkie wartości na lewo od 53 są od niej mniejsze, a wszystkie wartości na prawo są od niej większe. Miejsce, w którym jest umieszczony element rozdzielający, nosi nazwę punktu podziału (ang. division point; oznaczymy je jako dp). Z definicji wartość 53 znajduje się już w swoim docelowym, posortowanym położeniu. Jeśli będziemy w stanie posortować fragmenty tablicy num[1..dp-1] oraz num[dp+1..n], to będziemy mogli posortować ją całą. Jednak do wykonania tego sortowania możemy zastosować ten sam proces, a to oznacza, że sortowanie można zaimplementować w formie rozwiązania rekurencyjnego. Zakładając, że dysponujemy funkcją partition, która dzieli podany fragment tablicy i zwraca jego punkt podziału, funkcję quicksort możemy napisać w następujący sposób. 274 Kup książkęPoleć książkę ROZDZIA(cid:146) 9. (cid:132) ZAAWANSOWANE METODY SORTOWANIA public static void quicksort(int[] A, int lo, int hi) { //sortuje A[lo] do A[hi] w kolejności rosnącej if (lo hi) { int dp = partition(A, lo, hi); quicksort(A, lo, dp-1); quicksort(A, dp+1, hi); } } //koniec quicksort Wywołanie quicksort(num, 1, n) posortuje tablicę num[1..n] w kolejności rosnącej. Teraz przyjrzymy się, jak można napisać funkcję partition. Załóżmy, że dysponujemy następującą tablicą: Spróbujemy podzielić ją względem wartości num[1], czyli liczby 53 (elementu rozdzielającego), przechodząc przy tym tablicę tylko jeden raz. Kolejno odczytamy wartości poszczególnych elementów tablicy. Jeśli dany element będzie większy do elementu rozdzielającego, nie robimy nic. Jeśli będzie mniejszy, przeniesiemy go na lewą stronę tablicy. Początkowo zmiennej lastSmall przypisujemy wartość 1; w trakcie dalszego działania metody zmienna ta będzie przechowywać indeks ostatniego znanego elementu tablicy, który jest mniejszy od elementu rozdzielającego. Proces podziału tablicy num przebiega w następujący sposób. 1. Porównujemy 12 z 53, ponieważ jest mniejsze, dodajemy 1 do wartości lastSmall (czyli zmienna ta przyjmie wartość 2) i zamieniamy element num[2] z nim samym. 2. Porównujemy 98 z 53; ponieważ 98 jest większe, przechodzimy do następnego elementu. 3. Porównujemy 63 z 53; ponieważ 63 jest większe, przechodzimy do następnego elementu. 4. Porównujemy 18 z 53; ponieważ 18 jest mniejsze, dodajemy 1 do lastSmall (zmienna ta będzie mieć aktualnie wartość 3) i zamieniamy num[3] (czyli 98) z 18. Na tym etapie tablica ma postać: 5. Porównujemy 32 z 53; ponieważ 32 jest mniejsze, dodajemy 1 do lastSmall (zmienna ta będzie mieć aktualnie wartość 4) i zamieniamy num[4] (czyli 63) z 32. 6. Porównujemy 80 z 53; ponieważ 80 jest większe, przechodzimy do następnego elementu. 7. Porównujemy 46 z 53; ponieważ 46 jest mniejsze, dodajemy 1 do lastSmall (zmienna ta będzie mieć aktualnie wartość 5) i zamieniamy num[5] (czyli 98) z 46. Na tym etapie tablica ma postać: 8. Porównujemy 72 z 53; ponieważ 72 jest większe, przechodzimy do następnego elementu. 9. Porównujemy 21 z 53; ponieważ 21 jest mniejsze, dodajemy 1 do lastSmall (zmienna ta będzie mieć aktualnie wartość 6) i zamieniamy num[6] (czyli 63) z 21. 10. Dotarliśmy do końca tablicy; zamieniamy num[1] z num[lastSmall]; przenosimy tym samym element rozdzielający w jego docelowe, posortowane położenie (w naszym przykładzie będzie to komórka o numerze 6). 275 Kup książkęPoleć książkę JAVA. ZAAWANSOWANE ZASTOSOWANIA W efekcie uzyskujemy tablicę o następującej zawartości. Punkt podziału jest wskazywany przez wartość zmiennej lastSmall (czyli 6). Metodę działającą zgodnie z powyższym opisem zaimplementujemy jako funkcję partition1. Jej kod przedstawiono jako fragment programu P9.3, którego można użyć do przetestowania działania obu zaprezentowanych wcześniej metod, czyli quicksort oraz partition1. Program P9.3 import java.io.*; public class QuicksortTest { public static void main(String[] args) throws IOException { int[] num = {0, 37, 25, 43, 65, 48, 84, 73, 18, 79, 56, 69, 32}; int n = 12; quicksort(num, 1, n); for (int h = 1; h = n; h++) System.out.printf( d , num[h]); System.out.printf( \n ); } public static void quicksort(int[] A, int lo, int hi) { //sortuje A[lo] do A[hi] w kolejności rosnącej if (lo hi) { int dp = partition1(A, lo, hi); quicksort(A, lo, dp-1); quicksort(A, dp+1, hi); } } //koniec quicksort public static int partition1(int[] A, int lo, int hi) { //dzieli A[lo] do A[hi], używając A[lo] jako elementu rozdzielającego int pivot = A[lo]; int lastSmall = lo; for (int j = lo + 1; j = hi; j++) if (A[j] pivot) { ++lastSmall; swap(A, lastSmall, j); } //koniec for swap(A, lo, lastSmall); return lastSmall; //zwracamy punkt podziału } //koniec partition1 public static void swap(int[] list, int i, int j) { //funkcja zamienia elementy list[i] oraz list[j] int hold = list[i]; list[i] = list[j]; list[j] = hold; } } //koniec klasy QuicksortTest 276 Kup książkęPoleć książkę ROZDZIA(cid:146) 9. (cid:132) ZAAWANSOWANE METODY SORTOWANIA Po wykonaniu program P9.3 wyświetli następujące wyniki (pokazujące, że elementy tablicy od num[1] do num[12] zostały posortowane). 18 25 32 37 43 48 56 65 69 73 79 84 Sortowanie szybkie jest jednym z tych algorytmów sortowania, których wydajność może się wahać w granicach od bardzo dużej do bardzo małej. Zazwyczaj algorytm ten ma złożoność rzędu O(nlog2n), a dla danych losowych liczba porównań waha się w granicach pomiędzy nlog2n a 3nlog2n. Jednak może ona być znacznie większa. Idea działania tego algorytmu polega na podzieleniu sortowanego fragmentu na dwie stosunkowo równe części. To, czy uda się to zrobić, czy nie, w znacznej mierze zależy od tego, jaka wartość zostanie wybrana na element rozdzielający. W przedstawionej funkcji jako element rozdzielający wybieramy pierwszy element sortowanego zakresu. Takie rozwiązanie sprawdzi się w większości przypadków, a zwłaszcza podczas sortowania danych losowych. Jeśli jednak pierwszy element okaże się najmniejszym elementem sortowanego zakresu, cała operacja podziału stanie się bezużyteczna, gdyż element rozdzielający znajdzie się na jego pierwszym miejscu. „Lewa” część zakresu będzie pusta, a „prawa” będzie tylko o jeden element mniejsza od aktualnie sortowanego zakresu. Podobnie stanie się, gdy elementem rozdzielającym okaże się największy element sortowanego zakresu. Choć nawet w takich przypadkach algorytm sortowania szybkiego spełni swoje zadanie, to jednak będzie działał znacząco wolniej. Jeśli np. tablica będzie już posortowana, sortowanie szybkie będzie działać równie wolno jak sortowanie przez wybieranie. Jednym z rozwiązań tego problemu jest wybranie jako elementu rozdzielającego losowego elementu tablicy, a nie pierwszego. Choć także w tym przypadku istnieje możliwość trafienia na element najmniejszy (lub największy), jednak stanie się to wyłącznie przez przypadek. Jeszcze innym rozwiązaniem jest użycie jako elementu rozdzielającego mediany pierwszego (A[lo]), ostatniego (A[hi]) oraz środkowego (A[(lo+hi)/2]) elementu zakresu. Sugerujemy, żeby spróbować przetestowania różnych sposobów wyboru elementu rozdzielającego. Przeprowadzone eksperymenty pokazały, że wybór losowego elementu tablicy jako elementu rozdzielającego był szybki i dawał dobre efekty nawet w przypadku sortowania już posortowanych danych. W rzeczywistości, w wielu przypadkach takie rozwiązanie będzie działać szybciej na danych posortowanych niż na danych losowych, co w przypadku algorytmu sortowania szybkiego jest niezwykłym wynikiem. Jedną z możliwych wad algorytmu sortowania szybkiego jest to, że zależnie od sortowanych danych narzuty związane z wykonywaniem wywołań rekurencyjnych mogą być wysokie. W punkcie 9.5.2 pokazano, jak można zminimalizować to zagrożenie. Z drugiej strony, wielką zaletą tego algorytmu jest niewielkie wykorzystanie dodatkowej pamięci. Warto to porównać z algorytmem mergesort (sortowaniem przez scalanie, także rekurencyjnym), wymagającym znacznie więcej dodatkowego miejsca (dokładnie tyle samo, ile wynosi wielkość sortowanej tablicy), którego używa do scalenia sortowanych fragmentów. Żadnej z tych wad nie ma natomiast algorytm sortowania przez kopcowanie. Nie jest to algorytm rekurencyjny i wymaga bardzo niewiele dodatkowej pamięci. Poza tym, zgodnie z informacjami podanymi w podrozdziale 9.3, sortowanie przez kopcowanie jest stabilne, pod tym względem, że jego wydajność w najgorszym razie wynosi 2nlog2n i to niezależnie od porządku elementów w sortowanej tablicy. 9.5.1. Inny sposób podziału Cel podziału sortowanego zakresu tablicy — czyli utworzenie dwóch części, takich że wszystkie elementy w lewej będą mniejsze od wszystkich elementów w prawej — można uzyskać na wiele sposobów. Pierwsza metoda, przedstawiona wcześniej, umieszczała element rozdzielający w jego docelowym położeniu. Dla odmiany przeanalizujemy teraz nieco inny sposób podziału. Choć także on przeprowadza podział względem elementu rozdzielającego, to jednak nie umieszcza go w docelowym położeniu. Jak się jednak przekonamy, nie będzie to żadnym problemem. 277 Kup książkęPoleć książkę JAVA. ZAAWANSOWANE ZASTOSOWANIA Ponownie załóżmy, że dysponujemy tablicą num[1..n], gdzie n = 10. Jako element rozdzielający wybieramy element 53. Ogólna idea polega na tym, by przeglądać tablicę, zaczynając od prawej, i szukać w niej klucza o wartości mniejszej lub równej wartości elementu rozdzielającego. Następnie tablica jest przeglądana od lewej, w poszukiwaniu klucza, który jest większy lub równy wartości elementu rozdzielającego. W końcu obie te wartości są zamieniane miejscami. Proces ten w efekcie powoduje, że wartości mniejsze są umieszczane z lewej, a większe z prawej strony sortowanego fragmentu tablicy. Zastosujemy dwie zmienne, lo oraz hi, które będą oznaczały położenie z lewej oraz z prawej. Początkowo zmiennej lo przypisujemy wartość 0, a zmiennej hi wartość 11 (n+1). Następnie powtarzamy następujące czynności. 1. Odejmujemy 1 od hi (czyli zmienna ta przyjmuje wartość 10). 2. Porównujemy num[hi], czyli 21, z 53; ponieważ 21 jest mniejsze, zatrzymujemy przeszukiwanie tablicy od prawej na hi = 10. 3. Dodajemy 1 do lo (czyli zmienna ta przyjmuje wartość 1). 4. Porównujemy num[lo], czyli 53, z 53; ponieważ 53 nie jest mniejsze, zatrzymujemy przeszukiwanie tablicy od lewej na lo = 1. 5. lo (1) jest mniejsze od hi (10), czyli zamieniamy num[lo] z num[hi]. 6. Odejmujemy 1 od hi (czyli zmienna ta przyjmuje wartość 9). 7. Porównujemy num[hi], czyli 72, z 53; ponieważ 72 jest większe, zmniejszamy wartość hi o 1 (przez co zmienna ta przyjmie wartość 8). Porównujemy num[hi], czyli 46, z 53, ponieważ 46 jest mniejsze, zatrzymujemy przeszukiwanie tablicy od prawej na hi = 8. 8. Dodajemy 1 do lo (czyli zmienna ta przyjmuje wartość 2). 9. Porównujemy num[lo], czyli 12, z 53; ponieważ 12 jest mniejsze, dodajemy 1 do lo (zmienna ta przyjmuje wartość 3). Porównujemy num[lo], czyli 98, z 53; ponieważ 98 jest większe, zatrzymujemy przeszukiwanie tablicy od lewej na lo = 3. 10. lo (3) jest mniejsze od hi (8), czyli zamieniamy num[lo] z num[hi]. Na tym etapie działania zmienna lo = 3, zmienna hi = 8, a zawartość tablicy num ma postać: 11. Odejmujemy 1 od hi (czyli zmienna ta przyjmuje wartość 7). 12. Porównujemy num[hi], czyli 80, z 53; ponieważ 80 jest większe, zmniejszamy wartość hi o 1 (przez co zmienna ta przyjmie wartość 6). Porównujemy num[hi], czyli 32, z 53, ponieważ 32 jest mniejsze, zatrzymujemy przeszukiwanie tablicy od prawej na hi = 6. 13. Dodajemy 1 do lo (czyli zmienna ta przyjmuje wartość 4). 14. Porównujemy num[lo], czyli 63, z 53; ponieważ 63 jest większe, zatrzymujemy przeszukiwanie tablicy od lewej na lo = 4. 15. lo (4) jest mniejsze od hi (6), czyli zamieniamy num[lo] z num[hi], uzyskując tablicę o następującej zawartości: 278 Kup książkęPoleć książkę ROZDZIA(cid:146) 9. (cid:132) ZAAWANSOWANE METODY SORTOWANIA 16. Odejmujemy 1 od hi (czyli zmienna ta przyjmuje wartość 5). 17. Porównujemy num[hi], czyli 18, z 53; ponieważ 18 jest mniejsze, zatrzymujemy przeszukiwanie tablicy od prawej na hi = 5. 18. Dodajemy 1 do lo (czyli zmienna ta przyjmuje wartość 5). 19. Porównujemy num[lo], czyli 18, z 53; ponieważ 18 jest mniejsze, dodajemy 1 do lo (zmienna ta przyjmuje wartość 6). Porównujemy num[lo], czyli 63, z 53; ponieważ 63 jest większe, zatrzymujemy przeszukiwanie tablicy od lewej na lo = 6. 20. lo (6) nie jest mniejsze od hi (5), zatem algorytm kończy działanie. Wartość zmiennej hi spełnia tę właściwość, że wartości num[1..hi] są mniejsze od wartości num[hi+1..n]. W naszym przypadku wartości num[1..5] są mniejsze od wartości num[6..10]. Trzeba zwrócić uwagę, że wartość 53 nie znajduje się w swoim docelowym, posortowanym położeniu. Jednak nie stanowi to większego problemu, gdyż w celu posortowania całej tablicy musimy jeszcze posortować jej fragmenty: num[1..hi] oraz num[hi+1..n]. Tak opisaną procedurę podziału możemy zaimplementować w formie następującej metody partition2. public static int partition2(int[] A, int lo, int hi) { //funkcja zwraca punkt podziału (dp), taki że A[lo..dp] = A[dp+1..hi] int pivot = A[lo]; --lo; ++hi; while (lo hi) { do --hi; while (A[hi] pivot); do ++lo; while (A[lo] pivot); if (lo hi) swap(A, lo, hi); } return hi; } //koniec partition2 W przypadku zastosowania tej metody podziału tablicy na dwie części metodę quicksort2 możemy napisać w następujący sposób. public static void quicksort2(int[] A, int lo, int hi) { //sortuje A[lo] do A[hi] w kolejności rosnącej if (lo hi) { int dp = partition2(A, lo, hi); quicksort2(A, lo, dp); quicksort2(A, dp+1, hi); } } W metodzie partition2 jako element rozdzielający wybieramy pierwszy element sortowanego zakresu tablicy. Jednak zgodnie z informacjami podanymi wcześniej, wybór dowolnego elementu zapewniłby lepsze wyniki. Taki losowy element można wybrać w następujący sposób: swap(A, lo, random(lo, hi)); int pivot = A[lo]; W tym przypadku funkcja random będzie mieć postać: public static int random(int m, int n) { //zwraca losową liczbę całkowitą z zakresu do m do n włącznie return (int) (Math.random() * (n - m + 1)) + m; } 279 Kup książkęPoleć książkę JAVA. ZAAWANSOWANE ZASTOSOWANIA 9.5.2. Nierekurencyjna wersja algorytmu sortowania szybkiego W przedstawionych wcześniej wersjach metody quicksort po dokonaniu podziału sortowanego fragmentu tablicy ta sama metoda była wykonywana rekurencyjnie, w celu posortowania najpierw lewej, a następnie prawej części zakresu. Takie rozwiązanie spełnia się doskonale. Jednak może się zdarzyć, że dla dużych wartości n liczba wykonywanych wywołań rekurencyjnych stanie się tak duża, że wystąpi błąd „przepełniania buforu rekurencji” (ang. recursive stack overflow). Z przeprowadzonych eksperymentów wynika, że dzieje się tak dla n = 7000, jeśli dane były już wcześniej posortowane, a jako element rozdzielający wybrany został pierwszy element sortowanego zakresu. Jednak algorytm działał bardzo dobrze nawet dla n = 100 000, kiedy elementem rozdzielającym został wybrany losowy element tablicy. Jeszcze innym rozwiązaniem jest napisanie metody quicksort w taki sposób, by nie korzystać w niej z rekurencji. Wymaga ona umieszczenia na stosie tych elementów listy, które jeszcze nie zostały posortowane. Można wykazać, że jeśli podlista jest dzielona na dwie części, to posortowanie najpierw mniejszej z nich sprawia, że liczba elementów na stosie zostanie ograniczona niemal do log2n. Załóżmy np., że sortujemy tablicę A[1..99], a pierwszy punkt podziału wypadł w elemencie o numerze 40. Załóżmy dodatkowo, że używamy metody partition2, która nie umieszcza elementu rozdzielającego w jego docelowym, posortowanym położeniu. A zatem w celu dokończenia sortowania musimy posortować dwa fragmenty tablicy: A[1..40] oraz A[41..99]. Umieścimy zatem na stosie parę liczb (41, 99) i zajmiemy się posortowaniem fragmentu tablicy A[1..40] (czyli krótszej podlisty). Załóżmy, że punkt podziału fragmentu A[1..40] wypadł w elemencie numer 25. Umieszczamy zatem na stosie (1, 25) i przetwarzamy w pierwszej kolejności fragment A[26..40]. Na tym etapie prac na stosie znajdują się dwie podlisty — (41, 99) oraz (1, 25) — którymi jeszcze musimy się zająć. Próba posortowania fragmentu A[26..40] spowoduje umieszczenie na stosie kolejnej podlisty itd. W naszej implementacji algorytmu na stosie będziemy także umieszczali krótszą podlistę, jednak natychmiast będzie ona zdejmowana z niego i przetwarzana. Wspominane wcześniej wyniki gwarantują, że na stosie nigdy nie będzie więcej niż log299 = 7 (po zaokrągleniu w górę) elementów. Nawet w razie sortowania n = 1 000 000 elementów mamy gwarancję, że liczba elementów umieszczonych na stosie nigdy nie przekroczy 20. Oczywiście, tym stosem musimy zarządzać samodzielnie. Każdy element stosu będzie zawierał dwie liczby całkowite (nazwiemy je left i right), określające, że do posortowania pozostaje jeszcze zakres tablicy pomiędzy elementami left i right. Klasę NodeData możemy zdefiniować w następujący sposób. class NodeData { int left, right; public NodeData(int a, int b) { left
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Java. Zaawansowane zastosowania
Autor:

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: