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;
}
}
{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).
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ąbelkowe | Zamiana sąsiadów | O(n²) | tak, przy > |
| Przez wybór | Minimum na pozycję i | O(n²) | nie |
| Przez wstawianie | Klucz w ułożony początek | O(n²), lepiej gdy prawie ułożone | tak |
| Szybkie | Pivot i dwie strony | około n log n, pechowo n² | nie |
| Scalanie | Połówki i scalenie | n 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.
{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ę
Wymagania na ocenę
Dział 6 planu (lekcje 31–39), ocena roczna. Ocena wyższa zawiera wymagania na oceny niższe.
| Ocena | Uczeń |
|---|---|
| 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. |