Porównania
Zamiany
Przebieg

  • Wstawiana
  • Porównywane
  • Zamienione
  • Posortowana część

Więcej o sortowaniu przez wstawianie

Sortowanie przez wstawianie

Sortowanie przez wstawianie działa tak, jak wiele osób układa karty w ręce. Utrzymuje posortowaną część na początku listy, bierze kolejną wartość i przesuwa ją wstecz obok każdej większej wartości, aż trafi na swoje miejsce. Odtwórz sortowanie w dowolnym tempie albo przechodź przez nie po jednym porównaniu i obserwuj liczniki porównań, zamian i przebiegów. Naciśnij Odtwórz, aby obejrzeć sortowanie, albo Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce. Kafelki liczą porównania, zamiany i przebiegi. Wybierz liczbę słupków, ich początkowy układ albo wpisz własne liczby. Gdy plansza jest zaznaczona, strzałki przechodzą o krok, spacja uruchamia i wstrzymuje, a Home i End przenoszą na początek i na koniec.

Jak to działa

  1. Wybierz liczbę słupków i ich początkowy układ: losowy, prawie posortowany, odwrócony lub z kilkoma różnymi wartościami. Możesz też wpisać własne liczby.
  2. Naciśnij Odtwórz albo używaj przycisków Krok i Wstecz, aby przechodzić po jednym porównaniu. Przeciągnij suwak kroków, aby przeskoczyć w dowolne miejsce sortowania.
  3. Wypróbuj prawie posortowaną listę i odwróconą, i porównaj, ile porównań wymaga każda z nich.

Jak działa sortowanie przez wstawianie

Pierwsza wartość sama w sobie jest posortowaną częścią. Weź drugą wartość i porównaj ją z poprzednią; jeśli poprzednia jest większa, zamień je i porównuj oraz zamieniaj dalej, aż poprzednia wartość nie będzie większa albo wartość dotrze na początek. Teraz pierwsze dwie wartości są w dobrej kolejności. Zrób to samo z trzecią wartością, czwartą i tak dalej aż do końca listy.

Szybkie dla prawie posortowanych list

Każdy przebieg kończy się na pierwszej wartości, która nie jest większa, więc wartość, która już stoi blisko swojego miejsca, kosztuje tylko jedno lub dwa porównania. Posortowana lista wymaga n − 1 porównań i żadnych zamian; odwrócona, czyli najgorszy przypadek, wymaga n(n − 1)/2 jednych i drugich. Liczba zamian zawsze równa się liczbie inwersji w liście początkowej, czyli par w złej kolejności. Dlatego sortowanie przez wstawianie często stosuje się do krótkich lub prawie posortowanych list, a także wewnątrz szybszych algorytmów do dokończenia małych fragmentów.

Często zadawane pytania

Jak działa sortowanie przez wstawianie?

Buduje posortowaną część na początku listy. Każdy przebieg bierze kolejną wartość i przesuwa ją wstecz obok każdej większej wartości przed nią, aż trafi na swoje miejsce. Po przebiegu k pierwsze k + 1 wartości są już uporządkowane, choć późniejsza wartość wciąż może zostać wstawiona między nie.

Ile porównań i zamian wykonuje sortowanie przez wstawianie?

Liczba zamian zawsze równa się liczbie inwersji w liście początkowej: zero dla posortowanej listy, n(n − 1)/2 dla odwróconej. Porównań jest tyle, ile zamian, plus najwyżej jedno na przebieg, czyli od n − 1 do n(n − 1)/2.

Dlaczego sortowanie przez wstawianie jest szybkie dla prawie posortowanych list?

Bo przebieg kończy się, gdy tylko napotka wartość, która nie jest większa. Gdy każda wartość jest blisko swojego ostatecznego miejsca, każdy przebieg jest krótki, a całe sortowanie zajmuje czas bliski n.

Czy sortowanie przez wstawianie jest stabilne?

Tak. Wartość przesuwa się tylko obok wartości ściśle większych, więc równe wartości nigdy się nie mijają i zachowują pierwotną kolejność.

Czy moje liczby są gdzieś wysyłane?

Nie. Sortowanie działa w twojej przeglądarce, a ostatnie ustawienia zostają w pamięci lokalnej tej przeglądarki.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Przejdź do edytora