Wpisany przez Michał Knasiecki
sobota, 13 sierpnia 2005 11:00
Zasada działania tego algorytmu jest często porównywana do porządkowania kart w wachlarz podczas gry. Każdą kartę wstawiamy w odpowiednie miejsce, tzn. po młodszej, ale przed starszą. Podobnie jest z liczbami.
Pierwszy element pozostaje na swoim miejscu. Następnie bierzemy drugi i sprawdzamy, w jakiej relacji jest on z pierwszym. Jeśli jest niemniejszy, to zostaje na drugim miejscu, w przeciwnym wypadku wędruje na pierwsze miejsce. Dalej sprawdzamy trzeci element (porównujemy go do dwóch pierwszych i wstawiamy w odpowiednie miejsce), czwarty (porównujemy z trzema pierwszymi), piąty itd. Idea działania algorytmu opiera się na podziale ciągu na dwie części: pierwsza jest posortowana, druga jeszcze nie. Wybieramy kolejną liczbę z drugiej części i wstawiamy ją do pierwszej. Ponieważ jest ona posortowana, to szukamy dla naszej liczby takiego miejsca, aby liczba na lewo była niewiększa a liczba na prawo niemniejsza. Wstawienie liczby do posortowanej tablicy wymaga więc czasu O(n). Wynika z tego złożoność algorytmy: O(n2)
Oto przykład dla nieposortowanego ciągu <2, 4, 1, 3>

Pierwszy element pozostaje na swoim miejscu. Następnie bierzemy drugi i sprawdzamy, w jakiej relacji jest on z pierwszym. Jeśli jest niemniejszy, to zostaje na drugim miejscu, w przeciwnym wypadku wędruje na pierwsze miejsce. Dalej sprawdzamy trzeci element (porównujemy go do dwóch pierwszych i wstawiamy w odpowiednie miejsce), czwarty (porównujemy z trzema pierwszymi), piąty itd. Idea działania algorytmu opiera się na podziale ciągu na dwie części: pierwsza jest posortowana, druga jeszcze nie. Wybieramy kolejną liczbę z drugiej części i wstawiamy ją do pierwszej. Ponieważ jest ona posortowana, to szukamy dla naszej liczby takiego miejsca, aby liczba na lewo była niewiększa a liczba na prawo niemniejsza. Wstawienie liczby do posortowanej tablicy wymaga więc czasu O(n). Wynika z tego złożoność algorytmy: O(n2)
Oto przykład dla nieposortowanego ciągu <2, 4, 1, 3>

| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| kris | C# | ![]() | ![]() |
![]() ![]() ![]() ![]() / 7 | |
| Michał Knasiecki | C/C++ | ![]() | ![]() |
![]() ![]() ![]() ![]() / 12 | |
| Marian | C/C++ | C++ | ![]() | ![]() |
![]() ![]() ![]() ![]() / 6 |
| Tomasz Lubiński | Java | ![]() | ![]() |
![]() ![]() ![]() ![]() / 2 | |
| Rafał Gawlik | Java | ![]() | ![]() |
![]() ![]() ![]() ![]() / 2 | |
| Dominik Goździuk | Perl | ![]() | ![]() |
![]() ![]() ![]() ![]() / 0 |
Poprawiony: piątek, 27 maja 2011 08:43



/ 7

