StartAlgorytmyAlgorytmy sortowaniaSortowanie przez wstawianie (insertionsort)
Baza Wiedzy
Wersja offline serwisu przeznaczona na urządzenia z systemem Android.

Darowizny
darowiznaWspomóż rozwój serwisu


Nagłówki RSS
Kanał artykuły
Kanał implementacje
Kanał komentarze
Kanał forum


Bookmarki









Sonda
Implementacji w jakim języku programowania poszukujesz?
 
Sortowanie przez wstawianie (insertionsort)
Ocena użytkowników:++++- / 28
SłabyŚwietny 
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>
Image



Autor Język programowania Komentarz Otwórz Pobierz Ocena
kris C#
Implementacja w C#
Implementacja w C#
++++- / 7
Michał Knasiecki C/C++
Implementacja w C/C++
Implementacja w C/C++
++++- / 12
Marian C/C++ C++
Implementacja w C/C++
Implementacja w C/C++
++++- / 6
Tomasz Lubiński Java
Implementacja w Java
Implementacja w Java
++++- / 2
Rafał Gawlik Java
Implementacja w Java
Implementacja w Java
+++++ / 2
Dominik Goździuk Perl
Implementacja w Perl
Implementacja w Perl
----- / 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: piątek, 27 maja 2011 08:43

Dodaj komentarz

Kod antysapmowy
Odśwież