Login lub e-mail Hasło   

Sortowanie przez wstawianie

Wprowadzenie Sortowanie przez wstawienie ( insertion sort ) to algorytm, którego czas działania wynosi O(n 2 ). Jest on skuteczny dla małej ilości danych. Jest to jeden z...
Wyświetlenia: 11.018 Zamieszczono 29/10/2006

Wprowadzenie

Sortowanie przez wstawienie (insertion sort) to algorytm, którego czas działania wynosi O(n2). Jest on skuteczny dla małej ilości danych. Jest to jeden z prostszych i jeden z bardziej znanych algorytmów sortowania. Jest on stabilny i nie wymaga dodatkowej pamięci (działa w miejscu). Często stosujemy go podczas gry w karty, biorąc je ze stołu. Biorąc po jednej karcie ze stołu wstawiamy ją w odpowiednie miejsce do kart, które mamy w ręce.

 

Przykład

Rozważmy jakiś przykład. Weźmy następujący ciąg liczb do posortowania:

 
3 0 9 5 1 7 6

Możemy sobie wyobrazić, że liczby po prawej stronie to nasze karty na stole, które będziemy po kolei brać, a te, które są po lewej (na razie nie mamy żadnej) to karty, które trzymamy w ręce. Przypominam, że każdą kartę, którą bierzemy ze stołu wstawiamy w odpowiednie miejsce wśród kart, które mamy w ręce tak, aby były one posortowane.

Tak więc bierzemy pierwszą liczbę (w tym wypadku jest to 3) i przenosimy ją na lewą stronę. Nie musimy nic poza tym robić, ponieważ po lewej stronie nie ma żadnych liczb. W ten sposób otrzymujemy:

3
0 9 5 1 7 6

Teraz bierzemy kolejną liczbę z lewej strony, czyli 0 i wstawiamy w odpowiednią pozycję po lewej stronie. Ponieważ 0 jest mniejsze od 3, więc wstawiamy je przed tą liczbę:

0 3
9 5 1 7 6

Podobnie postępujemy z liczbą 9. Ponieważ jest ona największa z tych po lewej, więc wstawiamy ją na końcu:

0 3 9
5 1 7 6

Następnie wstawiamy pierwszą liczbę w ciągu po prawej, czyli 5 w odpowiednie miejsce w ciągu po lewej. Odpowiednie miejsce dla tej liczby to pozycja między liczbami 3 i 9:

0 3 5 9
1 7 6

Postępując podobnie jak wyżej z 1 wstawiamy ją po lewej stronie między 0 a 3:

0 1 3 5 9
7 6

Tak samo dla liczby 7 - wstawiamy ją między liczby 5 i 9:

0 1 3 5 7 9
6

Na sam koniec wstawiamy ostatnią z liczb - 6 do ciągu po lewej stronie między 5 a 7:

0 1 3 5 6 7 9
 

Algorytm sortowania przez wstawianie najlepiej jest zaimplementować na strukturach danych zwanych listami, są one bowiem w tym przypadku bardziej elastyczne. Implementacja na tablicach może być mało efektywna ze względu na konieczność przesuwania danych w tychże tablicach.

Podobne artykuły


49
komentarze: 18 | wyświetlenia: 64976
37
komentarze: 9 | wyświetlenia: 28519
50
komentarze: 27 | wyświetlenia: 63525
41
komentarze: 19 | wyświetlenia: 32981
32
komentarze: 12 | wyświetlenia: 26675
12
komentarze: 3 | wyświetlenia: 29779
11
komentarze: 2 | wyświetlenia: 33151
11
komentarze: 1 | wyświetlenia: 86405
9
komentarze: 2 | wyświetlenia: 6132
19
komentarze: 10 | wyświetlenia: 21324
21
komentarze: 9 | wyświetlenia: 12473
18
komentarze: 11 | wyświetlenia: 9267
17
komentarze: 10 | wyświetlenia: 10596
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska