Klasa 4 · rozdział 6 · lekcje 31–39 · II okres

Sortowanie

Pięć algorytmów układa tablicę niemalejąco. Trzy proste są kwadratowe. Szybkie i scalanie dzielą zadanie na mniejsze. Stabilność mówi, czy równe klucze zachowują kolejność. Po sortowaniu wolno puścić wyszukiwanie binarne.

Po tym rozdziale powinieneś umieć

  • wyjaśnić stabilność na parach o tym samym kluczu;
  • zaimplementować bąbelkowe, przez wybór i przez wstawianie bez we/wy;
  • opisać dziel i zwyciężaj;
  • zaimplementować quicksort i scalanie oraz rozpisać jeden podział albo jedno scalenie;
  • porównać złożoność kwadratową z n log n i liczbę zamian na małym przykładzie;
  • opakować sortowanie szablonem albo metodą klasy.

1. Stabilność i złożoność

Sortowanie niemalejące: każdy następny element jest nie mniejszy od poprzedniego. Funkcje przestawiają tablicę w miejscu albo przez tablicę pomocniczą. Nic nie wypisują.

Stabilność: dwa elementy o równym kluczu zostają w tej kolejności, w której przyszły. Ma to sens, gdy oprócz liczby jest etykieta. Weź pary (klucz, etykieta): (4, a), (3, b), (4, c), (2, d). Po stabilnym sortowaniu po kluczu czwórki zostają a przed c: (2, d), (3, b), (4, a), (4, c).

Wybór minimum psuje ten porządek. Na starcie minimum to 2 na końcu. Zamiana z pierwszą czwórką daje (2, d), (3, b), (4, c), (4, a). Klucze są posortowane, ale c stanęło przed a. Sortowanie przez wybór nie jest stabilne. Bąbelkowe przy porównaniu > (równych nie zamienia) jest stabilne. Scalanie z <= biorącym lewą część też. Szybkie w wersji z tego rozdziału — nie.

Złożoność trzech prostych metod to O(n²): pętla w pętli. Szybkie i scalanie przy typowych danych robią około n log n kroków, bo poziomów podziału jest około log n, a na każdym poziomie oglądasz n elementów. Pechowy pivot w szybkim potrafi zejść do kwadratu. Scalanie trzyma poziom n log n, kosztem tablicy pomocniczej.

2. Bąbelkowe, wybór, wstawianie

Bąbelkowe zamienia sąsiadów, gdy lewy jest większy. Po przejściu maksimum stoi na końcu, więc wewnętrzna pętla skraca się o i.

void babelkowe(int t[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (t[j] > t[j + 1]) {
                int tmp = t[j];
                t[j] = t[j + 1];
                t[j + 1] = tmp;
            }
}

{4, 2, 3, 1}, pierwsze przejście: 2 4 3 1, 2 3 4 1, 2 3 1 4. Dużo zamian sąsiadów.

Przez wybór: dla pozycji i szukasz minimum od i do końca i zamieniasz je z t[i]. Co najwyżej jedna zamiana na pozycję. Na {4, 2, 3, 1} pierwsza zamiana od razu daje 1 2 3 4.

void przezWybor(int t[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (t[j] < t[minIdx]) minIdx = j;
        int tmp = t[i];
        t[i] = t[minIdx];
        t[minIdx] = tmp;
    }
}

Przez wstawianie: początek do i jest już ułożony. Klucz t[i] wchodzi w lukę, a większe elementy z lewej przesuwają się w prawo. Na danych prawie ułożonych wewnętrzna pętla kończy się szybko. Na odwrotnie ułożonych znowu jest około n² przesunięć.

void przezWstawianie(int t[], int n) {
    for (int i = 1; i < n; i++) {
        int klucz = t[i];
        int j = i - 1;
        while (j >= 0 && t[j] > klucz) {
            t[j + 1] = t[j];
            j--;
        }
        t[j + 1] = klucz;
    }
}
Trzy ślady, jeden wynik Każda metoda na kopii {4, 2, 3, 1} kończy jako 1 2 3 4. Różni się droga: bąbelkowe ma kilka zamian sąsiadów w pierwszym przejściu, wybór — jedną zamianę minimum, wstawianie — przesuwanie klucza w ułożony początek.

3. Dziel i zwyciężaj

Dzielisz zadanie na mniejsze tego samego rodzaju, rozwiązujesz je (często rekurencyjnie) i składasz wyniki. Warunek stopu: zadanie tak małe, że odpowiedź jest oczywista (zero albo jeden element już jest posortowany).

Sortowanie szybkie dzieli tablicę względem pivota, a potem sortuje lewą i prawą część. Składanie jest tanie: pivot już stoi na swoim miejscu. Scalanie dzieli tablicę na pół bez patrzenia na wartości, sortuje połówki i dopiero składa je w jedną rosnącą całość. Euklides też „zmniejsza” zadanie, ale nie składa dwóch niezależnych połówek — to rekurencja, nie każda rekurencja jest dziel i zwyciężaj. Na lekcji tą nazwą obejmujesz szybkie i scalanie.

4. Sortowanie szybkie

Pivot to u nas ostatni element przedziału. Na lewo idzie to, co nie większe, na prawo to, co większe. Pivot wskakuje między części. Potem dwa wywołania: lewa część i prawa. Sam pivot już nie wchodzi do żadnej.

int podziel(int t[], int lewy, int prawy) {
    int pivot = t[prawy];
    int i = lewy - 1;
    for (int j = lewy; j < prawy; j++) {
        if (t[j] <= pivot) {
            i++;
            int tmp = t[i];
            t[i] = t[j];
            t[j] = tmp;
        }
    }
    int tmp = t[i + 1];
    t[i + 1] = t[prawy];
    t[prawy] = tmp;
    return i + 1;
}

void szybkie(int t[], int lewy, int prawy) {
    if (lewy < prawy) {
        int p = podziel(t, lewy, prawy);
        szybkie(t, lewy, p - 1);
        szybkie(t, p + 1, prawy);
    }
}

{3, 1, 4, 2}, pivot 2. Jedynka zamienia się z trójką: 1 3 4 2. Pivot ląduje na indeksie 1: 1 2 4 3. Lewa część to sama jedynka. Prawa {4, 3} daje 3 4. Całość: 1 2 3 4. Wywołanie na całej tablicy: szybkie(t, 0, n - 1).

Dwa wywołania Po podziale sortujesz obie strony. Samo lewe wywołanie zostawia prawą część nieuporządkowaną.

5. Sortowanie przez scalanie

Dzielisz indeksami na pół, aż zostanie jeden element. Potem scalasz dwie już ułożone połówki do tablicy pomocniczej i kopiujesz z powrotem. Przy równych kluczach bierzesz lewy (<=), więc metoda jest stabilna.

void scal(int t[], int lewy, int srodek, int prawy, int pom[]) {
    int i = lewy, j = srodek + 1, k = lewy;
    while (i <= srodek && j <= prawy) {
        if (t[i] <= t[j]) pom[k++] = t[i++];
        else pom[k++] = t[j++];
    }
    while (i <= srodek) pom[k++] = t[i++];
    while (j <= prawy) pom[k++] = t[j++];
    for (int p = lewy; p <= prawy; p++) t[p] = pom[p];
}

void scalanie(int t[], int lewy, int prawy, int pom[]) {
    if (lewy >= prawy) return;
    int srodek = (lewy + prawy) / 2;
    scalanie(t, lewy, srodek, pom);
    scalanie(t, srodek + 1, prawy, pom);
    scal(t, lewy, srodek, prawy, pom);
}

Ślad {4, 2, 3, 1}. Połówki {4, 2} i {3, 1}. Scalenie jedynek: {2, 4} oraz {1, 3}. Ostatnie scalenie bierze 1, potem 2, potem 3, potem 4. Tablicę pom tworzysz raz, rozmiaru n, i podajesz w głąb. Wywołanie: int pom[4]; scalanie(t, 0, 3, pom); — przy zmiennym n użyj vector<int> pom(n).

6. Porównanie i szablon

Algorytm Idea Złożoność typowa Stabilne
BąbelkoweZamiana sąsiadówO(n²)tak, przy >
Przez wybórMinimum na pozycję iO(n²)nie
Przez wstawianieKlucz w ułożony początekO(n²), lepiej gdy prawie ułożonetak
SzybkiePivot i dwie stronyokoło n log n, pechowo n²nie
ScalaniePołówki i scalenien log n, dodatkowa pamięćtak, przy <=

Szablon zdejmuje int z nagłówka, jeśli typ da się porównać i kopiować. Poniżej wstawianie — ten sam szkielet co wyżej.

template <typename T>
void wstawianie(T t[], int n) {
    for (int i = 1; i < n; i++) {
        T klucz = t[i];
        int j = i - 1;
        while (j >= 0 && t[j] > klucz) {
            t[j + 1] = t[j];
            j--;
        }
        t[j + 1] = klucz;
    }
}

Po sortowaniu rosnącym szukajBin z poprzedniego rozdziału jest legalne. Kolejność w programie: ułóż, potem szukaj. Przy pięciu elementach liniowe bez sortowania dalej jest uczciwe. Przy tysiącu posortowanych kodów — binarne.

Zlicz zamiany Na {4, 2, 3, 1} dopisz licznik w bąbelkowym i w wyborze. Bąbelkowe zamienia więcej razy. Wybór — najwyżej raz na pozycję, nawet gdy porównań jest tyle samo rzędu.

Ćwiczenia do samodzielnego wykonania

Folder: Dokumenty\cwiczenia-po\klasa-4\rozdzial-06.

Ćwiczenie 1. Trzy proste łatwe

Bąbelkowe, wybór i wstawianie na kopiach {4, 2, 3, 1}. Wynik każdego: 1 2 3 4. Funkcje bez we/wy.

Ćwiczenie 2. Stabilność na kartce średnie

Pary (4,a), (3,b), (4,c), (2,d). Pokaż wynik stabilny i wynik po jednej zamianie wyboru minimum. Napisz, która metoda z tabeli jest niestabilna.

Ćwiczenie 3. Quicksort średnie

Odtwórz podział {3, 1, 4, 2}: pivot 2 na indeksie 1. Potem pełne sortowanie.

Ćwiczenie 4. Scalanie średnie

scalanie na {4, 2, 3, 1}. Na kartce wypisz obie połówki tuż przed ostatnim scal.

Ćwiczenie 5. Szablon i binarne trudne

Szablon wstawiania na int i na string. Po sortowaniu liczb szukaj binarnie. Wypisz indeks albo −1.

Ćwiczenie 6. Licznik trudne

Policz zamiany bąbelkowego i wyboru na tej samej tablicy 8 liczb. Dopisz zdanie: oba są O(n²), a liczba zamian może się różnić. Uzasadnij wybór scalania, gdy n rośnie i potrzebujesz stabilności.

Sprawdź się

1. Sortowanie stabilne:
2. Przez wybór na {4, 2, 3, 1} w pierwszym kroku:
3. Dziel i zwyciężaj w tym rozdziale:
4. Scalanie względem szybkiego:
5. O(n²) opisuje:

Wymagania na ocenę

Dział 6 planu (lekcje 31–39), ocena roczna. Ocena wyższa zawiera wymagania na oceny niższe.

OcenaUczeń
2 Omawia bąbelkowe i przez wybór własnymi słowami. Uzupełnia pętle bąbelkowego według wzoru.
3 Implementuje bąbelkowe i przez wybór. Implementuje wstawianie według przykładu. Wyjaśnia, że wynik jest niemalejący.
4 Charakteryzuje dziel i zwyciężaj. Implementuje quicksort albo scalanie w całości. Sortowanie jest funkcją bez we/wy. Porównuje trzy proste metody pod kątem liczby zamian.
5 Implementuje quicksort i omawia przebieg scalania (albo ma oba w kodzie). Odróżnia złożoność kwadratową od n log n. Stosuje szablon. Wskazuje ideę stabilności.
6 Porównuje metody pomiarem liczby zamian albo porównań. Uzasadnia wybór algorytmu, także stabilność, gdy przy kluczu jest etykieta.

Lista „już umiem”