Rozdział 3: Algorytmy sortowania

Sortowanie to proces reorganizacji sekwencji obiektów w celu uszeregowania ich w określonej logicznej kolejności. Na przykład, Twój rachunek za kartę kredytową prezentuje transakcje w kolejności chronologicznej, a Twoje książki są ustawione na półce alfabetycznie według autora i tytułu. Sortowanie jest podstawową operacją w informatyce i odgrywa kluczową rolę w wielu zastosowaniach. Istnieje wiele klasycznych algorytmów sortowania, które ucieleśniają różne podejścia do tego problemu.

W tym rozdziale rozważamy kilka klasycznych metod sortowania oraz ważną strukturę danych znaną jako kolejka priorytetowa. Zaczynamy od omówienia kilku elementarnych metod sortowania, w tym sortowania przez wybór, sortowania przez wstawianie i sortowania Shella. Metody te są odpowiednio stosowane w wielu zastosowaniach, ale w przypadku dużych problemów przechodzimydo sortowania przez scalanie i sortowania szybkiego, dwóch rekurencyjnych algorytmów sortowania, które można wykorzystać do sortowania ogromnej liczby elementów. Kończymy na omówieniu kolejek priorytetowych i ich zastosowaniu w sortowaniu i innych zastosowaniach.

Proste sortowania

Najprostsze algorytmy sortowania wykonują następujące operacje:

Sortowanie przez wybór: Znajdź najmniejszy element i zamień go z pierwszym wpisem, następnie znajdź drugi najmniejszy element i zamień go z drugim wpisem, itd.
Sortowanie przez wstawianie: Weź każdy element po kolei i wstaw go w odpowiednie miejsce wśród już rozważonych (zachowując je posortowane).

Te operacje odzwierciedlają sposób, w jaki ludzie zwykle wykonują zadania sortowania i są skuteczne dla małych rozmiarów problemu. Jednak nie skalują się dobrze i stają się niepraktyczne do sortowania dużych tablic.

Sortowanie przez wybór

Sortowanie przez wybór to prosty algorytm sortowania, który działa w następujący sposób: Najpierw znajdź najmniejszy element w tablicy i zamień go z pierwszym wpisem (sam ze sobą, jeśli pierwszy wpis jest już najmniejszy). Następnie znajdź następny najmniejszy element i zamień go z drugim wpisem. Kontynuuj w ten sposób, aż cała tablica będzie posortowana.

Pętla wewnętrzna sortowania przez wybórHere is the Polish translation of the provided markdown file, with the code comments translated:

Sortowanie przez wybór jest używane do znalezienia minimalnego elementu w niesortowanej podtablicy a[i..N-1]. Indeks minimalnego elementu jest przechowywany w min. Następnie, a[i] jest wymieniane z a[min], co umieszcza minimalny element w jego ostatecznej pozycji. Gdy indeks i przemieszcza się od lewej do prawej, elementy po jego lewej stronie są w posortowanej kolejności w tablicy i nie będą już dotykane.

Oto implementacja sortowania przez wybór w Javie:

public static void selectionSort(Comparable[] a) {
    int N = a.length;
    for (int i = 0; i < N; i++) {
        int min = i;
        for (int j = i+1; j < N; j++) {
            if (less(a[j], a[min])) min = j;
        }
        exch(a, i, min);
    }
}

Sortowanie przez wybór używa około ~N^2/2 porównań i N wymian, aby posortować tablicę długości N. Czas działania jest niewrażliwy na dane wejściowe - zajmuje mniej więcej tyle samo czasu, aby uruchomić sortowanie przez wybór dla tablicy, która jest już w kolejności, lub dla tablicy ze wszystkimi kluczami równymi, jak dla losowo uporządkowanej tablicy.

Sortowanie przez wstawianie

Sortowanie przez wstawianie to inny prosty algorytm sortujący, który działa poprzez budowanie ostatecznej posortowanej tablicy jeden element na raz. Jest on znacznie mniej wydajny na dużych tablicach niż bardziej zaawansowane algorytmy, takie jak szybkie sortowanie, sortowanie przez kopcowanie lub sortowanie przez scalanie, ale ma kilka zalet:

Jest wydajny dla małych zbiorów danych.
Jest bardziej wydajny w praktyce niż sortowanie przez wybór.
Jest stabilny, tzn. nie zmienia względnej kolejności elementów o równych kluczach.
Jest w miejscu, tzn. wymaga tylko stałej ilości O(1) dodatkowej pamięci.
Jest online, tzn. może sortować listę w miarę jej otrzymywania.

Oto implementacja sortowania przez wstawianie w Javie:

public static void insertionSort(Comparable[] a) {
    int N = a.length;
    for (int i = 1; i < N; i++) {
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            exch(a, j, j-1);
        }
    }
}

Wewnętrzna pętla sortowania przez wstawianie przesuwa większe elementy o jedną pozycję w prawo, robiąc miejsce na wstawienie bieżącego elementu.Here is the Polish translation of the provided markdown file, with the code comments translated:

Czas działania sortowania przez wstawianie zależy od początkowego porządku elementów w danych wejściowych. Na przykład, jeśli tablica jest duża, a jej elementy są już posortowane (lub prawie posortowane), to sortowanie przez wstawianie jest znacznie, znacznie szybsze niż gdy elementy są losowo uporządkowane lub w odwrotnej kolejności.

Sortowanie Shella

Sortowanie Shella jest prostym rozszerzeniem sortowania przez wstawianie, które zyskuje na szybkości, pozwalając na wymianę elementów tablicy, które są daleko od siebie, aby uzyskać częściowo posortowane tablice, które można następnie efektywnie posortować, ostatecznie za pomocą sortowania przez wstawianie.

Idea polega na przestawieniu tablicy, aby nadać jej właściwość, że pobierając co h-ty element (rozpoczynając od dowolnego miejsca), otrzymuje się posortowaną podtablicę. Taka tablica jest nazywana h-posortowaną. Innymi słowy, h-posortowana tablica to h niezależnych posortowanych podciągów, przeplatanych ze sobą. Poprzez h-sortowanie dla niektórych dużych wartości h, możemy przesuwać elementy w tablicy na duże odległości, a tym samym ułatwić h-sortowanie dla mniejszych wartości h. Stosując taki proces dla dowolnej sekwencji wartości h, kończącej się na 1, otrzymamy posortowaną tablicę: to jest sortowanie Shella.

Oto implementacja sortowania Shella w Javie:

public class MaxPQ<Key extends Comparable<Key>> {
    // Tablica przechowująca kolejkę priorytetową
    private Key[] pq;
    // Liczba elementów w kolejce
    private int N;
    
    public MaxPQ(int capacity) {
        // Inicjalizacja tablicy o podanej pojemności
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() {
        // Sprawdzenie, czy kolejka jest pusta
        return N == 0;
    }
   
    public void insert(Key key) {
        // Dodanie nowego elementu do kolejki
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() {
        // Usunięcie i zwrócenie elementu o najwyższym priorytecie
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) {
        // Przywrócenie właściwości kolejki po dodaniu nowego elementu
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) {
        // Przywrócenie właściwości kolejki po usunięciu elementu
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private booleaPoniżej znajduje się tłumaczenie pliku Markdown na język polski. Komentarze w kodzie zostały przetłumaczone, ale sam kod pozostał niezmieniony.
 
n mniejszy(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }
 
    prywatna void wymiana(int i, int j) {
        Klucz t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}

Ten kod implementuje kopiec binarny zorientowany na maksimum, używając tablicy pq do przechowywania drzewa binarnego uporządkowanego według kopca. Operacje insert() i delMax() utrzymują niezmiennik kopca, używając pomocniczych metod swim() i sink() do przywrócenia porządku kopca przez wymianę kluczy z rodzicem większym niż dziecko lub dzieckiem większym niż jego rodzic.

Stoper

Bardziej przydatnym typem abstrakcyjnym danych jest prosty i skuteczny abstrakcja dla stopera, pokazana na sąsiedniej stronie. Aby go użyć, utwórz obiekt Stopwatch, gdy chcesz uruchomić stoper, a następnie użyj metody elapsedTime(), aby uzyskać upłynięty czas w sekundach od utworzenia obiektu. Implementacja używa System.currentTimeMillis() Javy, aby uzyskać bieżący czas w milisekundach od północy 1 stycznia 1970 r.

Zmienna instancyjna start rejestruje czas, w którym został utworzony stoper, a elapsedTime() używa start, aby obliczyć upłynięty czas. Pokazany klient jest typowy: wykonuje jakieś obliczenia i używa Stopwatch, aby zmierzyć, jak długo trwa obliczenie. Typ danych Stopwatch jest skuteczną abstrakcją, ponieważ oddziela koncepcję stopera (interfejs) od implementacji (przy użyciu System.currentTimeMillis() Javy). To oddzielenie interfejsu i implementacji jest podstawową cechą typów abstrakcyjnych danych, którą zobaczymy w każdym ADT w całej książce.

Podsumowanie

Typy abstrakcyjne danych są niezbędnym elementem programowania obiektowego, które są szeroko stosowane we współczesnym programowaniu. W tej sekcji zobaczyliśmy:

Definiowanie typu abstrakcyjnego danych jako klasy Javy, z zmiennymi instancyjnymi do definiowania wartości typu danych i metod instancyjnych do implementacji operacji na tych wartościach.
Opracowywanie wielu implementacji tego samego interfejsu API, przy użyciu różnych reprezentacji tego samego abstrakcyjnego typu danych.Oto tłumaczenie na język polski:

Typy danych abstrakcyjnych

Rozróżnianie interfejsów API, klientów i implementacji typu danych abstrakcyjnego.
Projektowanie interfejsów API dla typów danych abstrakcyjnych.
Tworzenie klientów i klientów testowych do użycia w testowaniu i debugowaniu.
Rozumowanie na temat poprawności implementacji typu danych abstrakcyjnego, przy użyciu asercji.
Porównywanie wydajności różnych implementacji tego samego interfejsu API.

Te działania są niezbędną częścią rozwoju każdego programu w Javie. Każdy program w Javie, który piszemy, będzie obejmował korzystanie z typów danych abstrakcyjnych z bibliotek; wiele z nich będzie obejmowało opracowanie nowych typów danych abstrakcyjnych. W następnej sekcji rozważamy trzy podstawowe typy danych abstrakcyjnych, które są istotnymi składnikami w ogromnej liczbie programów, a w Sekcji 1.4 rozważamy proces analizowania charakterystyk wydajności implementacji w szczegółach.

Chapter 2 Algorithms Fundamentals Chapter 4 Searching Algorithms