Sortowanie przez wstawianie

Autor podstrony: Krzysztof Zajączkowski

Stronę tą wyświetlono już: 4604 razy

Algorytm sortowania przez wstawienie w odróżnieniu od sortowania bombelkowego w kolejnych przejściach p sprawdza k-ty element tablicy z elementami o indeksach i < k i gdy i-ty element > k-ty to następuje przeniesienie elementu k-tego za element i-ty chyba, że żaden element nie okaże się mniejszy od k-tego wtedy tenże element ląduje na samym początku tablicy. Przejścia są powtarzane aż do p = n - 1, gdzie n - to liczba elementów sortowanej tablicy.

Rys. 1
Animacja algorytmu sortowania przez wstawianie. Kolory użyte w animacji oznaczają:
  • czerwony - element tablicy, który jest mniejszy od sortowanego elementu;
  • niebieski - element tablicy, który jest większy od sortowanego elementu;
  • pomarańczowy - element tablicy, który jest w danym przejściu sortowany;
  • zielony - pozostałe elementy tablicy

W najgorszym przypadku liczba kroków niezbędnych do wykonania w implementacji z powyższej animacji wynosi:

złożoność obliczeniowa implementacji algorytmu sortowania bombelkowego [1]

Zapis wyrażenia w formacie TeX-a:

\frac{1}{2}\cdot n\cdot (n-1)

Warto też nadmienić, że sortownie przez wstawianie jest szybsze od sortowania bombelkowego dla danych losowych. Dzieje się tak dlatego, że liczba wykonywanych operacji zamiany miejscami sortowanych wartości jest znacznie mniejsza niż w przypadku sortowania bombelkowego. Nie zmienia to niemniej faktu, że sortowanie bombelkowe, gdy dane są częściowo posortowane może się okazać znacznie szybsze od sortowania przez wstawienie.

Propozycje książek
tytuł: Algorytmy. Ilustrowany przewodnik autor: Aditya Bhargava

Tytuł:

Algorytmy. Ilustrowany przewodnik

Autor:

Aditya Bhargava

tytuł: Algorytmy. Struktury danych i złożoność obliczeniowa autor: Feliks Kurp

Tytuł:

Algorytmy. Struktury danych i złożoność obliczeniowa

Autor:

Feliks Kurp

tytuł: Algorytmy w Pythonie. Techniki programowania dla praktyków autor: Piotr Wróblewski

Tytuł:

Algorytmy w Pythonie. Techniki programowania dla praktyków

Autor:

Piotr Wróblewski

tytuł: Matematyka dyskretna dla praktyków. Algorytmy i uczenie maszynowe w Pythonie autor: Ryan T. White, Archana Tikayat Ray

Tytuł:

Matematyka dyskretna dla praktyków. Algorytmy i uczenie maszynowe w Pythonie

Autor:

Ryan T. White, Archana Tikayat Ray

tytuł: Algorytmy kryptograficzne w Pythonie. Wprowadzenie autor: Shannon W. Bray

Tytuł:

Algorytmy kryptograficzne w Pythonie. Wprowadzenie

Autor:

Shannon W. Bray

tytuł: Algorytmy sztucznej inteligencji. Ilustrowany przewodnik autor: Rishal Hurbans

Tytuł:

Algorytmy sztucznej inteligencji. Ilustrowany przewodnik

Autor:

Rishal Hurbans

tytuł: Algorytmy bez tajemnic  autor: Thomas H. Cormen

Tytuł:

Algorytmy bez tajemnic

Autor:

Thomas H. Cormen

tytuł: Algorytmy dla bystrzaków autor: John Paul Mueller, Luca Massaron

Tytuł:

Algorytmy dla bystrzaków

Autor:

John Paul Mueller, Luca Massaron

tytuł: Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II autor: David Natingga

Tytuł:

Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II

Autor:

David Natingga

tytuł: Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji autor: Giuseppe Bonaccorso

Tytuł:

Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji

Autor:

Giuseppe Bonaccorso

W związku z tym, że firma Helion nie wywiązuje się z swoich zobowiązań naliczania prowizji za każdą zakupioną książkę a kontakt z ową frmą jest nie możliwy autor strony zmuszony został do zablokowania linkowania książek. Za wszelkie niedogodności z tym związane z góry przepraszam i obiecuję włączenie linkowania gdy tylko sprawa zostanie wyjaśniona