Sortowanie przez wstawianie
Sortowanie przez wstawianie to interaktywny eksperyment z aplikacji Algorytmy w akcji – darmowej symulacji ze StudyFi Lab, która działa bezpośrednio w przeglądarce.
Sortowanie przez wstawianie działa jak układanie kart w ręce: lewa część jest już posortowana, a każdy kolejny element (key) przesuwa się w lewo, aż trafi na mniejszy. Większe elementy przesuwają się po drodze o jedno miejsce w prawo. Dla losowych danych to O(n²), ale dla prawie posortowanych niemal O(n) — posortowana tablica wymaga tylko n−1 porównań.
Spróbuj: Uruchom je na prawie posortowanej tablicy, a potem na odwróconej. Ile razy więcej przesunięć potrzebuje odwrócona?
Najczęstsze pytania
Co pokazuje eksperyment „Sortowanie przez wstawianie”?
Sortowanie przez wstawianie działa jak układanie kart w ręce: lewa część jest już posortowana, a każdy kolejny element (key) przesuwa się w lewo, aż trafi na mniejszy. Większe elementy przesuwają się po drodze o jedno miejsce w prawo. Dla losowych danych to O(n²), ale dla prawie posortowanych niemal O(n) — posortowana tablica wymaga tylko n−1 porównań.
Jak wypróbować „Sortowanie przez wstawianie”?
Uruchom je na prawie posortowanej tablicy, a potem na odwróconej. Ile razy więcej przesunięć potrzebuje odwrócona?
Uczysz się do sprawdzianu?
Wgraj swoje notatki, a StudyFi zrobi z nich fiszki, testy i podcasty.