Wstawia kolejne elementy na właściwe miejsce w już posortowanej części tablicy. O(n²).
Sortowanie przez wstawianie działa podobnie do układania kart w ręku. Bierzesz kartę po karcie i wstawiasz ją w odpowiednie miejsce wśród już posortowanych – przesuwając większe karty w prawo.
Algorytm: przechodzimy przez tablicę od drugiego elementu. Dla każdego elementu szukamy jego właściwego miejsca w lewej, posortowanej części, przesuwając większe elementy o jedno miejsce w prawo.
Zastosowanie praktyczne: mimo złożoności O(n²) sortowanie przez wstawianie jest wyjątkowo szybkie na małych i prawie posortowanych zbiorach danych. Z tego powodu bywa składnikiem algorytmów hybrydowych. Przykładem jest Timsort – domyślny algorytm sortowania w Pythonie (list.sort() oraz funkcja sorted()) – który łączy sortowanie przez scalanie z sortowaniem przez wstawianie, używając tego drugiego do porządkowania krótkich fragmentów danych.
Cecha charakterystyczna: sortowanie przez wstawianie jest stabilne – zachowuje względną kolejność elementów o tej samej wartości.
Na maturze: często stawiany w opozycji do sortowania przez wybór – różnica polega na sposobie, w jaki rozszerza się posortowana część tablicy.
Prześledź krok po kroku, jak algorytm porządkuje tablicę. Porównywane elementy są podświetlone, a te, które trafiły na swoje docelowe miejsce, zmieniają kolor na zielony.
Naciśnij „Krok", aby wykonać jedną operację, albo „Auto", aby uruchomić całą animację.
funkcja sortuj_przez_wstawianie(T, n): dla i od 1 do n - 1: klucz ← T[i] j ← i - 1 // przesuwamy w prawo elementy większe od klucza dopóki j ≥ 0 oraz T[j] > klucz: T[j + 1] ← T[j] j ← j - 1 // wstawiamy klucz w odpowiednie miejsce T[j + 1] ← klucz zwróć T
def sortowanie_przez_wstawianie(tablica):
n = len(tablica)
for i in range(1, n):
klucz = tablica[i]
j = i - 1
# przesuwamy większe elementy w prawo
while j >= 0 and tablica[j] > klucz:
tablica[j + 1] = tablica[j]
j -= 1
tablica[j + 1] = klucz
return tablica
# Przykład użycia
dane = [64, 25, 12, 22, 11]
print(sortowanie_przez_wstawianie(dane))
# Wynik: [11, 12, 22, 25, 64]
# Działa szybko dla danych prawie posortowanych
posortowane = [1, 2, 3, 5, 4]
print(sortowanie_przez_wstawianie(posortowane))
# Wynik: [1, 2, 3, 4, 5]#include <vector>
#include <iostream>
using namespace std;
void sortowanie_przez_wstawianie(vector<int>& t) {
int n = t.size();
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;
}
}
int main() {
vector<int> dane = {64, 25, 12, 22, 11};
sortowanie_przez_wstawianie(dane);
for (int x : dane) cout << x << " ";
// Wynik: 11 12 22 25 64
}Tak – to algorytm stabilny. Element wstawiamy dopiero za ostatnim równym mu elementem po lewej stronie (przesuwamy tylko elementy ściśle większe), więc kolejność elementów o tej samej wartości nigdy się nie zmienia.
O(n²) w najgorszym i średnim przypadku, ale O(n) w najlepszym – dla danych już posortowanych. To właśnie ta różnica odróżnia go od sortowania przez wybór, które zawsze wykonuje tę samą liczbę porównań, niezależnie od stanu tablicy.
Nie – sortuje w miejscu (in-place) i potrzebuje tylko O(1) dodatkowej pamięci, czyli jednej zmiennej na przenoszony element.
Przy małych tablicach oraz przy danych, które są już prawie posortowane – wtedy działa niemal liniowo. Z tego właśnie powodu jest składnikiem algorytmów hybrydowych, jak Timsort, gdzie porządkuje krótkie fragmenty danych.
Oba mają złożoność O(n²), ale sortowanie przez wstawianie od razu wstawia element na właściwe miejsce w posortowanej części, natomiast sortowanie bąbelkowe przesuwa większe elementy w stronę końca tablicy pojedynczymi zamianami sąsiadów w każdym przebiegu.
O(n²)O(n)O(1)Najgorszy i średni przypadek to O(n²). Najtrudniejsza jest tablica odwrócona (posortowana malejąco): każdy nowy element jest mniejszy od wszystkich poprzednich, więc wstawiając i-ty element trzeba przesunąć aż i elementów. Łączna liczba przesunięć to 1 + 2 + ... + (n − 1) ≈ n²/2, a po pominięciu stałej otrzymujemy O(n²).
Najlepszy przypadek to O(n). Dla danych już posortowanych warunek pętli wewnętrznej od razu jest fałszywy i nie wykonuje ona żadnego przesunięcia. To dlatego algorytm jest tak skuteczny dla danych prawie posortowanych.
Pamięć O(1). Elementy wstawiamy w obrębie tej samej tablicy, bez dodatkowych struktur rosnących wraz z n.
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: