Sortowanie przez Wstawianie (Insertion Sort) na Maturze
Sortowanie przez wstawianie (Insertion Sort) to kolejny prosty algorytm sortowania o złożoności O(n^2). Jego działanie idealnie obrazuje sposób, w jaki ludzie sortują karty w ręku. Wyobraź sobie, że masz już kilka posortowanych kart po lewej stronie, a po prawej bierzesz nową kartę. Gdzie ją wstawić? Przesuwasz się od prawej do lewej po posortowanych kartach, aż znajdziesz dla niej właściwe miejsce. Dokładnie tak działa ten algorytm. Dzieli tablicę na dwie części: małą, posortowaną na początku, i dużą, nieposortowaną resztę. Następnie po kolei bierze elementy z nieposortowanej części i 'wstawia' je w odpowiednie miejsce w części posortowanej.
Dlaczego to ważne? Podobnie jak sortowanie bąbelkowe, musisz znać ten algorytm, aby umieć go rozpoznać, przeanalizować 'na sucho' lub zaimplementować. Ma on jednak ważną przewagę nad bąbelkowym: jest *bardzo* szybki (złożoność O(n)) dla danych, które są już *prawie* posortowane. Jest to też algorytm 'stabilny', co bywa przydatne. Na maturze jest to jeden z trzech 'kwadratowych' algorytmów, które warto mieć w repertuarze.
Teoria
Algorytm iteruje od drugiego elementu (indeks 1) do końca. Każdy element (nazwijmy go 'kluczem') jest porównywany z elementami w posortowanej podtablicy po jego lewej stronie. Elementy w posortowanej części, które są większe od 'klucza', są przesuwane o jedną pozycję w prawo, aby zrobić miejsce. Gdy znajdziemy miejsce (element mniejszy lub równy, albo początek tablicy), 'klucz' jest wstawiany.
Jak to działa?
- Krok 1: Pętlą zewnętrzną `i` przechodzimy od *drugiego* elementu (indeks 1) do końca tablicy (indeks `n-1`).
- Krok 2: Element `tab[i]` (który chcemy wstawić) zapisujemy w zmiennej pomocniczej, np. `klucz` (key).
- Krok 3: Ustawiamy drugi wskaźnik, `j`, na pozycję *na lewo* od klucza (`j = i - 1`). To jest ostatni element posortowanej części.
- Krok 4: Rozpoczynamy pętlę wewnętrzną `while`, która działa dopóki `j >= 0` (nie wyszliśmy poza tablicę) ORAZ `tab[j] > klucz` (element po lewej jest większy niż nasz klucz).
- Krok 5: W pętli `while`: przesuwamy większy element w prawo: `tab[j + 1] = tab[j]`.
- Krok 6: W pętli `while`: cofamy wskaźnik `j`: `j = j - 1`.
- Krok 7: Po wyjściu z pętli `while`, wskaźnik `j` jest o 1 za mały, więc wstawiamy `klucz` na pozycję `j + 1`: `tab[j + 1] = klucz`.
- Krok 8: Pętla zewnętrzna `i` przechodzi do następnego elementu. Powtarzamy.
Złożoność: Złożoność czasowa (Najgorszy i Średni przypadek): O(n²). Dzieje się tak, gdy tablica jest posortowana odwrotnie. Każdy element trzeba 'przesunąć' przez całą posortowaną część. Złożoność czasowa (Najlepszy przypadek): O(n). Dzieje się tak, gdy tablica jest już posortowana. Pętla wewnętrzna `while` nigdy się nie uruchomi. Złożoność pamięciowa: O(1) (stała), bo sortujemy 'w miejscu' (in-place).
Implementacja
Standardowe sortowanie przez wstawianie
Pythondef insertion_sort(tab):
n = len(tab)
# Pętla zewnętrzna od drugiego elementu (indeks 1)
for i in range(1, n):
klucz = tab[i] # Element do wstawienia
j = i - 1 # Ostatni element posortowanej części
# Pętla wewnętrzna: przesuwaj elementy większe od klucza w prawo
while j >= 0 and klucz < tab[j]:
tab[j + 1] = tab[j] # Przesunięcie
j -= 1
# Wstaw klucz w znalezione wolne miejsce
tab[j + 1] = klucz
return tab
dane = [64, 34, 25, 12, 22, 11, 90]
print(f"Przed: {dane}")
insertion_sort(dane)
print(f"Po: {dane}")To jest klasyczna implementacja. Zwróć uwagę, że nie robimy 'zamian' (swap) jak w sortowaniu bąbelkowym. My *przesuwamy* elementy w prawo (`tab[j+1] = tab[j]`), aż zrobi się 'dziura' (`j+1`), w którą wstawiamy nasz `klucz`.
Sortowanie przez wstawianie (vector)
C++#include <iostream>
#include <vector>
using namespace std;
void insertion_sort(vector<int>& tab) {
int n = tab.size();
for (int i = 1; i < n; i++) {
int klucz = tab[i]; // Element do wstawienia
int j = i - 1; // Ostatni element posortowanej części
// Pętla wewnętrzna: przesuwaj elementy większe od klucza w prawo
while (j >= 0 && tab[j] > klucz) {
tab[j + 1] = tab[j]; // Przesunięcie
j = j - 1;
}
// Wstaw klucz w znalezione wolne miejsce
tab[j + 1] = klucz;
}
}
int main() {
vector<int> dane = {64, 34, 25, 12, 22, 11, 90};
insertion_sort(dane);
for (int x : dane) {
cout << x << " ";
}
cout << endl;
return 0;
}Logika w C++ jest identyczna jak w Pythonie. Pętla zewnętrzna 'i' idzie od 1 do n-1. Bierzemy 'klucz', a pętla 'while' z wskaźnikiem 'j' przesuwa większe elementy w prawo, robiąc miejsce na 'klucz'.
Przykładowe Zadania Maturalne
W pliku 'dane.txt' znajduje się 100 liczb całkowitych, każda w osobnym wierszu. Wczytaj wszystkie liczby do tablicy. Następnie posortuj tę tablicę malejąco, implementując algorytm sortowania przez wstawianie. Na koniec wypisz 5 największych liczb z posortowanej tablicy.
Wskazówka: Najpierw wczytaj wszystkie liczby do listy. Następnie zaimplementuj sortowanie przez wstawianie. Aby sortować *malejąco*, musisz zmienić warunek w pętli 'while' z `klucz < tab[j]` na `klucz > tab[j]`. Po posortowaniu, 5 największych liczb to będzie 5 pierwszych elementów (indeksy 0-4).
Pokaż szkic rozwiązania
1. Stwórz pustą listę `liczby = []`. 2. Wczytaj wszystkie liczby z pliku 'dane.txt' do listy `liczby`. 3. Zaimplementuj funkcję `insertion_sort_malejaco(tab)`: a. `for i in range(1, len(tab)):` b. ` klucz = tab[i]` c. ` j = i - 1` d. ` while j >= 0 and klucz > tab[j]:` (zmiana warunku!) e. ` tab[j + 1] = tab[j]` f. ` j -= 1` g. ` tab[j + 1] = klucz` 4. Wywołaj `insertion_sort_malejaco(liczby)`. 5. Wypisz 5 pierwszych elementów: `for i in range(5): print(liczby[i])`.
W pliku liczby.txt w pierwszym wierszu znajduje się 3000 liczb pierwszych. Napisz program, który spośród liczb z pierwszego wiersza poda liczbę, która jest sto pierwszą liczbą w kolejności, licząc od największej po ich uporządkowaniu.
Wskazówka: Zadanie wymaga sortowania. Wczytaj 3000 liczb do tablicy. Zaimplementuj algorytm sortowania (np. przez wstawianie, choć dla 3000 liczb O(n^2) jest wolne - na maturze lepiej użyć `.sort()`). Jeśli posortujesz malejąco, 'sto pierwsza' liczba będzie miała indeks 100.
Pokaż szkic rozwiązania
1. Wczytaj pierwszy wiersz z pliku 'liczby.txt'. 2. Podziel wiersz na stringi (po spacji) i zamień je na int, zapisując do listy `liczby`. 3. Zaimplementuj funkcję sortującą, np. `insertion_sort_malejaco(liczby)` (jak wyżej). 4. Wywołaj sortowanie. *(Uwaga: W praktyce maturalnej `liczby.sort(reverse=True)` będzie 100x szybsze i jest zalecane, jeśli nie ma wymogu implementacji algorytmu)*. 5. Po posortowaniu malejącym, 'sto pierwsza' liczba jest na pozycji 100 (indeksy: 0, 1, 2... 100). 6. Wypisz: `print(liczby[100])`.
Częste Błędy
❌ Pomylenie pętli zewnętrznej (start od 0)
Algorytm zakłada, że `tab[0]` to *już posortowana* lista jednoelementowa. Pętla zewnętrzna `i` *musi* zaczynać się od indeksu 1 (drugi element), bo to jest pierwszy element, który 'wstawiamy'. Start od 0 jest niepotrzebny i może prowadzić do błędów.
Poprawka: Pamiętaj: pętla zewnętrzna `for i in range(1, n):`.
❌ Próba zamiany (swap) zamiast przesuwania (shift)
Uczniowie mylą to z sortowaniem bąbelkowym i próbują zamieniać `tab[j]` z `tab[j+1]`. W insertion sort nie zamieniamy `klucza` wielokrotnie. `Klucz` jest trzymany 'w ręku' (w zmiennej), a elementy są *przesuwane w prawo* (`tab[j+1] = tab[j]`), aby zrobić dla niego miejsce.
Poprawka: Zapamiętaj schemat: 1. Weź `klucz`. 2. Przesuwaj większych w prawo (pętla `while`). 3. Wstaw `klucz` w powstałą 'dziurę'.
❌ Błąd 'Off-by-One' w pętli wewnętrznej `while`
W pętli `while j >= 0 and ...` zapomnienie o warunku `j >= 0` jest krytyczne. Bez tego, pętla będzie próbowała sprawdzić `tab[-1]`, `tab[-2]` itd., co w Pythonie da zły wynik, a w C++ wyjdzie poza zakres tablicy i spowoduje błąd.
Poprawka: Warunek `while` musi *zawsze* zawierać sprawdzenie granicy tablicy: `j >= 0`.
❌ Złe miejsce wstawienia klucza
Pętla `while` kończy się, gdy `tab[j]` jest mniejsze lub równe `klucz` (lub gdy `j = -1`). Oznacza to, że `klucz` ma być wstawiony na pozycję *na prawo* od `j`. Uczniowie mylą się i wstawiają `klucz` w `tab[j]`.
Poprawka: Pętla `while` zmniejsza `j`. Po jej zakończeniu, właściwe miejsce to `j + 1`. Zawsze wstawiaj: `tab[j + 1] = klucz`.
Kluczowe Wnioski
- Sortowanie przez wstawianie ma złożoność O(n^2) (średnia i najgorsza).
- Jest bardzo szybkie (O(n)) dla danych już posortowanych lub prawie posortowanych.
- Jest to algorytm 'w miejscu' (O(1) pamięci) i 'stabilny'.
- Działa jak sortowanie kart w ręku: bierze element i wstawia go w odpowiednie miejsce w już posortowanej części.
- Algorytm *przesuwa* elementy w prawo, a nie *zamienia* ich (jak bubble sort).
- Pętla zewnętrzna `i` idzie od 1 do `n-1`.
- Pętla wewnętrzna `while j >= 0 and tab[j] > klucz` szuka miejsca i przesuwa elementy.
Najczęściej Zadawane Pytania
❓ Czy sortowanie przez wstawianie jest lepsze niż bąbelkowe?
Tak, w większości przypadków. Średnio wykonuje mniej zamian. Co najważniejsze, jego najlepszy przypadek (dla posortowanych danych) to O(n), podczas gdy dla bąbelkowego (nawet zoptymalizowanego) to wciąż O(n). Jest to preferowany algorytm O(n^2).
❓ Kiedy na maturze używać .sort() a kiedy Insertion Sort?
Zawsze używaj wbudowanej funkcji `.sort()` (lub `sorted()`), która działa w czasie O(n log n). Jest *zawsze* szybsza dla dużych danych. Insertion Sort implementuj tylko wtedy, gdy zadanie *wprost* o to prosi lub gdy masz przeanalizować jego kod.
❓ Dlaczego pętla zewnętrzna zaczyna się od 1 a nie od 0?
Ponieważ algorytm zakłada, że podtablica o jednym elemencie (na indeksie 0) jest z definicji posortowana. Zaczynamy od 'wstawiania' drugiego elementu (na indeksie 1) do tej posortowanej jednoelementowej podtablicy.
❓ Co to znaczy, że sortowanie jest 'stabilne'?
Oznacza to, że jeśli masz w tablicy dwa równe elementy (np. dwie piątki), to po posortowaniu nie zamienią się one miejscami. Ta 'piątka', która była pierwsza, pozostanie pierwsza. Insertion Sort jest stabilny.
Chcesz opanować wszystkie tematy maturalne?
Dołącz do kursu i zyskaj dostęp do interaktywnych lekcji, edytora kodu i setek zadań.