|
Strona główna
Ważne definicje:
Algorytmy sortowania:
Porównanie algorytmów
Instrukcja użytkownika
Informacja o programie
|
|
Opis algorytmu
|
W algorytmie sortowania przez wstawianie ciąg danych jest dzielony na dwie części:
- już uporządkowaną (przed uruchomieniem procedury nie zawiera ona żadnych elementów),
- jeszcze nie uporządkowaną (na początku zawiera wszystkie elementy).
Sposób porządkowania można opisać następująco:
- weź pierwszy element z części nieuporządkowanej (jeśli jest pusta to zakończ działanie algorytmu),
- wstaw go w odpowiednie miejsce w części uporządkowanej (po takiej operacji część nieuporządkowana jest jeden element krótsza,
a część posortowana zyskuje jeden element).
Pozostaje jeszcze do rozstrzygnięcia, w jaki sposób wyznaczyć prawidłowe położenie nowego elementu w części uporządkowanej.
Najprostszy sposób polega na porównaniu tego elementu z kolejnymi elementami części uporządkowanej.
Jeżeli element na pozycji i jest większy od wstawianego, to ten nowy element należy wstawić między elementy
na pozycjach i-1 i i.
Takie podejście jest zastosowane w demonstracji poniżej. Inna strategia wstawiania elementu do uporządkowanego ciągu jest
zastosowana w sortowaniu przez wstawianie z binarnym umieszczaniem.
|
Demonstracja
|
Poniższy applet demonstruje działanie opisanego algorytmu sortowania. Dane do sortowania mogą być losowe, uporządkowane lub odwrotnie uporządkowane.
- Zieloną i niebieską kropką są zaznaczone aktualnie porównywane elementy.
- Żółtą linią jest oznaczona uporządkowana część ciągu.
- Aby uruchomić demonstrację, naciśnij Start.
- Aby zatrzymać demonstrację, naciśnij Stop.
- Aby wykonać jeden krok algorytmu, naciśnij Krok.
- Aby przyspieszyć działanie, naciśnij >.
- Aby spowolnić działanie, naciśnij <.
- Aby zmienić typ danych, użyj pola wyboru Typ danych.
- Aby zmienić wielkość danych, użyj pola edycyjnego Wielkość danych i naciśnij przycisk Zmień dane.
Wielkość danych musi być liczbą z zakresu od 5 do 300.
|
