Sortowanie przez wstawianie - program jest algorytmem szczególnie polecanym do sortowania krótkich ciągów. Kod klasyczny według Wikibooks. Jego złożoność pesymistyczna też jest kwadratowa podobnie do sortowania bąbelkowego.
Idea sortowania przez wstawianie jest
następująca. Sortujemy w n-1 fazach,
ponumerowanych dla wygody opisu od 2 do n.
Przed rozpoczęciem i-tej fazy wiemy,
że podtablica a[1..i-1] jest już
posortowana. Naszym celem jest uporządkowanie podtablicy a[1..i], co w
rzeczywistości oznacza wstawienie na właściwe miejsce elementu a[i]
w uporządkowany ciąg a[1..i-1]. W tym celu odkładamy
element z pozycji a[i] na bok (zapamiętujemy w pomocniczej zmiennej), a następnie
przeglądamy elementy podtablicy a[1..i-1] od prawej do lewej,
przesuwając każdy element większy od odłożonego o jedną pozycję w prawo. Po
napotkaniu w tablicy a elementu nie większego od elementu
odłożonego (nazwijmy go elementem blokującym), element odłożony wstawiany tuż
przed element blokujący.
Postępując według tłumaczenia pokazanego na Youtube (od 4,44 min) można sortowanie przez wstawianie napisać w sposób następujący: program,
Ogólnie o sortowaniu:
Sortowanie jest jednym z najczęściej rozwiązywanych problemów informatycznych. Według różnych autorów, komputery spędzają od 25 do 80 procent czasu na porządkowaniu informacji. Porządek wśród elementów ułatwia i przyspiesza wykonywanie innych operacji (np. przeszukiwania).
Sortowanie jest też przykładem problemu, który może być rozwiązany na wiele sposobów, a ich efektywność jest istotnie różna. Za efektywność algorytmów sortujących przyjmuje się liczbę porównań wykonywanych między elementami danych. Zwykle jest ona podawana jako zależność od liczby elementów do uporządkowania.
Po wykonaniu InsertionSort
Ponownie Wioska Świętego Mikołaja
oraz Godzina Kodowania,
może tym razem Minecraft w GK
Świąteczne słówka
Postępując według tłumaczenia pokazanego na Youtube (od 4,44 min) można sortowanie przez wstawianie napisać w sposób następujący: program,
Ogólnie o sortowaniu:
Problem sortowania można zdefiniować następująco:
- Danymi wejściowymi jest ciąg n liczb.
- Wynikiem jest taka ich permutacja (czyli zmiana kolejności), że tworzą one ciąg rosnący (niemalejący).
Zadaniem algorytmu sortowania jest takie przestawienie
elementów danego ciągu, aby były one uporządkowane rosnąco (niemalejąco).
OpisSortowanie jest jednym z najczęściej rozwiązywanych problemów informatycznych. Według różnych autorów, komputery spędzają od 25 do 80 procent czasu na porządkowaniu informacji. Porządek wśród elementów ułatwia i przyspiesza wykonywanie innych operacji (np. przeszukiwania).
Sortowanie jest też przykładem problemu, który może być rozwiązany na wiele sposobów, a ich efektywność jest istotnie różna. Za efektywność algorytmów sortujących przyjmuje się liczbę porównań wykonywanych między elementami danych. Zwykle jest ona podawana jako zależność od liczby elementów do uporządkowania.
Stabilny algorytm porządkowania to taki, w którym
kolejność elementów względem siebie w
uporządkowanym ciągu jest taka sama, jak w ciągu danym do uporządkowania.
Porządkowanie w miejscu (in situ) Algorytm
porządkowania odbywa się w tym samym miejscu w
pamięci komputera, w którym są dane ciągi do uporządkowania. Ta własność ma duże znaczenie, bo algorytmem
działającym w miejscu można porządkować dwa razy dłuższe ciągi niż np. algorytmem
przez scalanie, który nie jest algorytmem działającym in situ.
Po wykonaniu InsertionSort
Ponownie Wioska Świętego Mikołaja
oraz Godzina Kodowania,
może tym razem Minecraft w GK
Świąteczne słówka