Home-theater-designers
Sortowanie przez wstawianie to technika polegająca na wykorzystaniu posortowanej podlisty i ciągłym dodawaniu do niej wartości z listy nieposortowanej, aż do posortowania całej listy.
Algorytm rozpoczyna się od pierwszego elementu listy jako posortowanej podlisty. Następnie porównuje następną liczbę z pierwszą. Jeśli jest większy, to jest wstawiany do pierwszego indeksu. W przeciwnym razie pozostaje w swoim indeksie.
Trzecia wartość jest następnie porównywana z pozostałymi dwoma, a następnie wstawiana do prawidłowego indeksu. Ten proces trwa, dopóki cała lista nie zostanie posortowana.
Bliższe spojrzenie na sortowanie wstawiania
Powyższy opis mógł nie mieć dla Ciebie sensu. Przykład powinien pomóc ci lepiej zrozumieć.
Załóżmy, że masz listę: [39, 6, 2, 51, 30, 42, 7].
Algorytm identyfikuje 39 jako pierwszą wartość posortowanej podlisty. Ocena następnie przechodzi na drugą pozycję.
Powiązane: Programowanie dynamiczne: przykłady, typowe problemy i rozwiązania
6 jest następnie porównywane z 39. Ponieważ 6 jest mniejsze niż 39, 6 jest wstawiane w pierwszej pozycji, a 39 w drugiej. Nowa kolejność na liście jest teraz po pierwszym przejściu:
[6, 39, 2, 51, 30, 42, 7]
Ocena przechodzi teraz na trzecią pozycję. 2 jest porównywana z dwiema ostatnimi liczbami, a następnie wstawiana we właściwej pozycji. Nowa kolejność na liście jest teraz po drugim przejściu:
[2, 6, 39, 51, 30, 42, 7]
W przypadku trzeciego przejścia kolejność na liście jest następująca:
[2, 6, 39, 51, 30, 42, 7]
Proces powtarza się, dopóki cała lista nie zostanie posortowana.
Zobacz poniższy diagram, który podsumowuje te operacje:
Analiza algorytmu
Złożoność czasowa sortowania przez wstawianie wynosi O(n2), tak jak sortowanie bąbelkowe . Liczba porównań w najgorszym przypadku to suma wszystkich liczb całkowitych od 1 do (n-1), dająca sumę kwadratową.
Implementacja kodu
Poniższy kod Pythona i Java pokazuje, jak zaimplementować metodę Insertion Sort.
Pyton:
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_elementJawa:
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
} Lepsze kodowanie z pseudokodem
Powyższe przykłady kodu zostały podane bez pseudokodu, do którego można się odwołać, aby napisać ten algorytm w innych językach. Większość programistów (włącznie z autorem) lubi podbiegać do klawiatury po tym, jak powiedziano im „szeptem” o tym, jak działa program.
Takie podejście jest niestety podatne na błędy, ponieważ logika programu staje się bardziej skomplikowana. Jak chciałbyś podnieść poziom swojej gry programistycznej, ucząc się korzystania z pseudokodu?
Udział Udział Ćwierkać E-mail Co to jest pseudokod i jak czyni cię lepszym programistą?Masz problemy z nauką programowania? Opanuj kod, ucząc się pseudokodu. Ale czym jest pseudokod i czy może naprawdę pomóc?
Czytaj dalej Powiązane tematy- Programowanie
- Jawa
- Pyton
- Poradniki kodowania
Jerome jest pisarzem sztabowym w MakeUseOf. Zajmuje się artykułami na temat programowania i systemu Linux. Jest także entuzjastą kryptowalut i zawsze śledzi branżę kryptograficzną.
jak zrobić filtr urodzinowy na snapchatWięcej od Jerome'a Davidsona
Zapisz się do naszego newslettera
Dołącz do naszego newslettera, aby otrzymywać porady techniczne, recenzje, bezpłatne e-booki i ekskluzywne oferty!
Kliknij tutaj, aby zasubskrybować