Sortowanie przez wstawianie
Sortowanie przez wstawianie to następny prosty, ale mało wydajny algorytm sortowania. Pierwsza iteracja algorytmu pobiera drugi element tablicy i sprawdza, czy jest mniejszy od pierwszego, a jeśli tak, zastępuje go pierwszym elementem. Następna iteracja „patrzy” na trzeci element i wstawia go w odpowiednie miejsce na podstawie dwóch pierwszych, więc wszystkie trzy elementy są ułożone poprawnie. W i-tej iteracji algorytmu pierwsze i elementów oryginalnej tablicy zostanie posortowanych. Przeanalizujmy jako przykład następującą tablicę, która jest taka sama jak tablica wykorzystywana w sortowaniu przez wybieranie:
Program, który implementuje algorytm sortowania przez wstawianie, najpierw „przyjrzy” się dwóm pierwszym elementom tablicy, czyli 34 i 56. Ponieważ są ułożone poprawnie, program przejdzie dalej. (Gdyby nie były ułożone prawidłowo, zamieniłby je miejscami).
W następnej iteracji program analizuje trzecią wartość, czyli 4. Ta wartość jest mniejsza od 56, więc zapamiętuje 4 w tymczasowej zmiennej i przesuwa 56 o jedno miejsce w prawo. Teraz program sprawdza, czy 4 jest mniejsze od 34, i jeśli tak, przesuwa 34 o jedno miejsce w prawo. Program osiągnął początek tablicy, więc wstawia 4 w zerowym elemencie. Teraz tablica ma postać:
W następnej iteracji program zapamiętuje 10 w zmiennej tymczasowej. Porównuje tę wartość z 56 i przesuwa 56 o jeden element w prawo, bo jest to wartość większa od 10. Teraz porówna 10 i 34, co spowoduje przesunięcie 34 w prawo. Gdy porówna 10 i 4, okaże się, że 10 jest większe od 4, więc wstawi 10 na pozycji 1. Teraz tablica ma postać:
Używając tego algorytmu, po i-tej iteracji mamy poprawnie posortowaną tablicę i pierwszych elementów, ale mogą nie być to ich końcowe położenia — może się okazać, że w dalszej części tablicy pojawią się elementy mniejsze.
Implementacja sortowania przez wstawianie
Klasa InsertionSortTest (rysunek 19.5) zawiera:
- metodę statyczną insertionSort sortującą wartości typu int algorytmem sortowania przez wstawianie;
- metodę statyczną printPass, która wyświetla zawartość każdego przebiegu;
- metodę main testującą metodę insertionSort.
2 // Sortowanie przez wstawianie
3 import java.security.SecureRandom;
4 import java.util.Arrays;
5
6 public class InsertionSortTest {
7 // Sortowanie tablicy algorytmem sortowania przez wstawianie
8 public static void insertionSort(int[] data) {
9 // Przejście w pętli przez data.length - 1 elementów
10 for (int next = 1; next < data.length; next++) {
11 int insert = data[next]; // Wartość do wstawienia
12 int moveItem = next; // Lokalizacja do wstawienia elementu
13
14 // Poszukaj miejsca wstawienia aktualnego elementu
15 while (moveItem > 0 && data[moveItem - 1] > insert) {
16 // Przesuń element w prawo o jedno miejsce
17 data[moveItem] = data[moveItem - 1];
18 moveItem--;
19 }
20
21 data[moveItem] = insert; // Umieść wstawiany element
22 printPass(data, next, moveItem); // Wyświetl przebieg algorytmu
23 }
24 }
25
26 // Wyświetl przebieg algorytmu
27 public static void printPass(int[] data, int pass, int index) {
28 System.out.printf("Po przebiegu %2d: ", pass);
29
30 // Wyświetlaj elementy aż do wybranego
31 for (int i = 0; i < index; i++) {
32 System.out.printf("%d ", data[i]);
33 }
34
35 System.out.printf("%d* ", data[index]); // Wskaż zamianę
36
37 // Wyświetl pozostałą część
38 for (int i = index + 1; i < data.length; i++) {
39 System.out.printf("%d ", data[i]);
40 }
41
42 System.out.printf("%n "); // Wyrównanie
43
44 // Wskaż posortowaną część tablicy
45 for (int i = 0; i <= pass; i++) {
46 System.out.print("-- ");
47 }
48 System.out.println();
49 }
50
51 public static void main(String[] args) {
52 SecureRandom generator = new SecureRandom();
53
54 // Utwórz nieposortowaną tablicę 10 liczb losowych
55 int[] data = generator.ints(10, 10, 100).toArray();
56
57 System.out.printf("Tablica nieposortowana: %s%n%n", Arrays.toString(data));
58 insertionSort(data); // Posortuj tablicę
59 System.out.printf("%nTablica posortowana: %s%n", Arrays.toString(data));
60 }
61 }
Po przebiegu 1: 34 96* 12 87 40 80 16 50 30 45
-- --
Po przebiegu 2: 12* 34 96 87 40 80 16 50 30 45
-- -- --
Po przebiegu 3: 12 34 87* 96 40 80 16 50 30 45
-- -- -- --
Po przebiegu 4: 12 34 40* 87 96 80 16 50 30 45
-- -- -- -- --
Po przebiegu 5: 12 34 40 80* 87 96 16 50 30 45
-- -- -- -- -- --
Po przebiegu 6: 12 16* 34 40 80 87 96 50 30 45
-- -- -- -- -- -- --
Po przebiegu 7: 12 16 34 40 50* 80 87 96 30 45
-- -- -- -- -- -- -- --
Po przebiegu 8: 12 16 30* 34 40 50 80 87 96 45
-- -- -- -- -- -- -- -- --
Po przebiegu 9: 12 16 30 34 40 45* 50 80 87 96
-- -- -- -- -- -- -- -- -- --
Tablica posortowana: [12, 16, 30, 34, 40, 45, 50, 80, 87, 96]
Rysunek 19.5. Sortowanie przez wstawianie
Metoda main (wiersze od 51. do 60.) jest taka sama jak metoda main z rysunku 19.4. Jedyna różnica polega na wywoływanej metodzie tym razem jest to insertionSort.
Metoda insertionSort
Wiersze od 8. do 24. deklarują metodę insertionSort. Wiersze od 10. do 23. przechodzą w pętli przez data.length - 1 elementów. W każdej iteracji wiersz 11. deklaruje i inicjalizuje zmienną insert przechowującą wartość elementu, który zostanie wstawiony do posortowanej części tablicy. Wiersz 12. deklaruje i inicjalizuje zmienną moveItem, która śledzi, gdzie wstawić element. Wiersze od 15. do 19. określają właściwe miejsce wstawienia elementu. Pętla kończy się po osiągnięciu początku tablicy lub znalezieniu elementu o mniejszej wartości. Wiersz 17. przesuwa element w prawo, a wiersz 18. zmniejsza indeks wstawiania następnego
elementu. Po zakończeniu pętli wiersz 21. wstawia element w odpowiednie miejsce.
Metoda printPass
Wynik działania metody printPass (wiersze od 27. do 49.) używa znaków minusa do wskazania części tablicy, która jest posortowana po każdym przebiegu. Znak gwiazdki wskazuje element, który został umieszczony w danym przebiegu na swoim miejscu.
Wydajność sortowania przez wstawianie
Algorytm sortowania przez wstawianie również działa w czasie O(n2). Podobnie jak sortowanie przez wybieranie, algorytm ten zawiera dwie zagnieżdżone pętle (wiersze od 8. do 24.). Pętla for (wiersze od 10. do 23.) wykonuje się data.length - 1 razy, wstawiając element w odpowiednie miejsce już posortowanego fragmentu. Na potrzeby tej aplikacji data.length - 1 jest równoważne n – 1 (bo data.length to rozmiar tablicy). Pętla while (wiersze od 15. do 19.) przechodzi przez poprzednie elementy tablicy. W najgorszej sytuacji pętla while wymaga n – 1 porównań. Każda pętla jest więc typu O(n). W notacji dużego O zagnieżdżenie pętli oznacza, że trzeba pomnożyć liczbę porównań, bo dla każdej iteracji pętli zewnętrznej pojawi się wiele iteracji pętli wewnętrznej. W tym algorytmie dla każdych O(n) iteracji pętli zewnętrznej będzie O(n) iteracji pętli wewnętrznej. W efekcie uzyskujemy O(n2).
Programowanie w Javie. Solidna wiedza w praktyce. Wydanie XI, Autorzy: Paul Deitel, Harvey Deitel, Wydawnictwo: Helion
