algorytm.org

Sortowanie przez wstawianie (insertionsort)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sortowanie przez wstawianie (insertionsort)
Ocena użytkowników:***** / 86
SłabyŚwietny 
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>
Sortowanie przez wstawianie

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
krisC#
.cs
.cs
***** / 11
Michał KnasieckiC/C++
.cpp
.cpp
***** / 16
MarianC/C++C++
.cpp
.cpp
***** / 16
TybiasC/C++C++
.cpp
.cpp
***** / 0
MattiooC/C++
.cpp
.cpp
***** / 0
Adam ChrapkowskiHaskell
.hs
.hs
***** / 1
Tomasz LubińskiJava
.java
.java
***** / 4
Rafał GawlikJava
.java
.java
***** / 6
KrzysztofJava
.java
.java
***** / 0
Maciej LipińskiJavaScriptfunkcja sortująca + test
.js
.js
***** / 0
Dominik GoździukPerl
.pl
.pl
***** / 0
Adam ChrapkowskiPython
.py
.py
***** / 0
mephistoRuby
.rb
.rb
***** / 0
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 listopada 2015 14:14
Komentarze
photo
+6 # 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ć
photo
-11 # 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