Wpisany przez Michał Knasiecki,
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>
Implementacje
| Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
| kris | C# | .cs | .cs | ***** / 13 | |
| Michał Knasiecki | C/C++ | .cpp | .cpp | ***** / 20 | |
| Marian | C/C++ | C++ | .cpp | .cpp | ***** / 25 |
| Tybias | C/C++ | C++ | .cpp | .cpp | ***** / 3 |
| Mattioo | C/C++ | .cpp | .cpp | ***** / 7 | |
| Adam Chrapkowski | Haskell | .hs | .hs | ***** / 3 | |
| Tomasz Lubiński | Java | .java | .java | ***** / 6 | |
| Rafał Gawlik | Java | .java | .java | ***** / 8 | |
| Krzysztof | Java | .java | .java | ***** / 0 | |
| Maciej Lipiński | JavaScript | funkcja sortująca + test | .js | .js | ***** / 0 |
| Dominik Goździuk | Perl | .pl | .pl | ***** / 0 | |
| Adam Chrapkowski | Python | .py | .py | ***** / 9 | |
| Maskara | Python | Z testem stworzonym za pomocą biblioteki pytest. | .py | .py | ***** / 1 |
| mephisto | Ruby | .rb | .rb | ***** / 0 |
Poprawiony: 26 listopada 2015 14:14
Komentarze
+5
#
MarcinM
2014-05-23 03:16
To nie jest prawda że wstawienie elementu do posortowanej tablicy ma słożoność n. Ma ono złożoność log_2(n). Porównujemy najpierw z elementem znajdującym się w środku tablicy jeśli wstawiany element jest większy to porównujemy z elementem w 3/4 itd. Złożoność obliczeniowa przy tym algorytmie (gdy zostanie on dobrze zaimplementowan y) wynosi o(n*log(n))
Odpowiedz | Odpowiedz z cytatem | Cytować
-4
#
Tomasz Lubiński
2015-10-02 10:24
Masz rację przeszukiwanie można zoptymalizować do złożoności O(log(n)), ale pozostaje jeszcze kwestia włożenia elementu do tablicy, które ma złożoność O(n), bo trzeba przesunąć O(n) elementów żeby wepchnąć element na swoje miejsce...
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz