Kluczowa różnica – sortowanie przez wstawianie a sortowanie przez wybór
Sortowanie przez wstawianie i sortowanie przez wybór to dwa algorytmy sortowania używane do sortowania kolekcji danych. Czasami konieczne jest uporządkowanie danych w określonej kolejności. Algorytmy sortowania to mechanizmy sortowania zbioru danych. Podczas sortowania dane są uporządkowane według porządku numerycznego lub leksykograficznego. Jeśli dane są odpowiednio posortowane, łatwiej byłoby szybciej wyszukiwać dane. Jeśli numery telefonów w książce telefonicznej nie są posortowane, trudno byłoby znaleźć konkretny numer telefonu. W ten sam sposób, jeśli słowa w słowniku nie są ułożone w kolejności alfabetycznej, bardzo trudno byłoby znaleźć słowa. Dlatego sortowanie jest przydatne w życiu codziennym. W informatyce istnieją algorytmy sortowania do sortowania zbioru danych. Dwa takie algorytmy to sortowanie przez wstawianie i sortowanie przez wybór. Sortowanie przez wstawianie to algorytm sortowania, który sortuje tablicę, przesuwając elementy jeden po drugim. Sortowanie przez wybór to algorytm sortowania, który znajduje najmniejszy element w tablicy i wymienia element z pierwszą pozycją, następnie znajduje drugi najmniejszy element i wymienia go z elementem na drugiej pozycji i kontynuuje proces, aż cała tablica zostanie posortowana. Kluczową różnicą między sortowaniem przez wstawianie a sortowaniem przez wybór jest to, że sortowanie przez wstawianie porównuje dwa elementy naraz, podczas gdy sortowanie przez wybór wybiera minimalny element z całej tablicy i sortuje go.
Co to jest sortowanie przez wstawianie?
Sortowanie przez wstawianie to algorytm sortowania oparty na porównaniu w miejscu. W tej metodzie tablica jest przeszukiwana krok po kroku. Nieposortowane elementy są przenoszone i wstawiane do posortowanej podlisty tablicy. Algorytm sortowania przez wstawianie można wyjaśnić na poniższym przykładzie.
Na przykład weź początkową tablicę jako 77, 33, 44, 11, 88. W tym algorytmie sortowania pierwszym krokiem jest wybranie bieżącego elementu.
Bieżący element to 77. Bieżący element jest porównywany ze wszystkimi elementami po lewej stronie. 77, to pierwszy element i nie ma żadnych elementów po lewej stronie. Indeks bieżącej pozycji to 0.
Wtedy indeks bieżącej pozycji jest zwiększany o 1. Teraz indeks wynosi 1, a bieżący element to 33. Porównując go z elementem po lewej stronie, jest on mniejszy niż 77. Wtedy obie te wartości są zamienione. Teraz 33 jest w indeksie 0, a 77 jest w indeksie 1.
Teraz tablica to 33, 77, 44, 11, 88.
Ponownie indeks jest zwiększany. Indeks wynosi 2, a bieżący element to 44. Jest porównywany z elementami po lewej stronie. 44 jest mniejsze niż 77. Więc te dwie wartości są zamieniane. Teraz tablica to 33, 44, 77, 11, 88. Konieczne jest porównanie wszystkich elementów po lewej stronie. Tak więc 44 jest w porównaniu z 33. 33 jest mniejsze niż 44. Więc te elementy nie muszą być wymieniane.
Teraz tablica to 33, 44, 77, 11, 88.
Ponownie indeks jest zwiększany. Indeks wynosi 3, a bieżący element to 11. Jest porównywany ze wszystkimi elementami po lewej stronie. 11 to mniej niż 77, więc te dwa są zamienione. Teraz tablica to 33, 44, 11, 77, 88. Porównując 11 i 44, 11 jest mniejsze niż 44. Więc te dwa są zamienione. Teraz tablice to 33, 11, 44, 77, 88. Ponownie 11 jest porównywane z 33. 11 jest mniejsze niż 33, więc te dwie wartości są zamieniane.
Teraz tablica to 11, 33, 44, 77, 88.
Zwiększenie indeksu spowoduje, że indeks będzie wynosił 4. Wartość wynosi 88. Jest wyższa niż 77. Nie ma więc potrzeby zamiany. Wreszcie posortowana tablica to 11, 33, 44, 77, 88.
Rysunek 01: Przykład sortowania przez wstawianie
Implementacja sortowania przez wstawianie jest jak powyżej. Początkowa tablica to 77, 33, 44, 11, 88. Po posortowaniu daje wynik 11, 33, 44, 77, 88.
Co to jest sortowanie wyboru?
Sortowanie przez wybór to algorytm sortowania w miejscu oparty na porównaniu. Tablice są podzielone na sekcje. Posortowana część znajduje się na lewym końcu. Niesortowana część znajduje się na prawym końcu. Najpierw należy znaleźć najmniejszą wartość. Następnie jest zamieniany z lewym elementem. Teraz ten element znajduje się w posortowanej tablicy. Ten proces kontynuuje przesuwanie nieposortowanej granicy tablicy z jednego elementu w prawo. Algorytm sortowania przez wybór można wyjaśnić na poniższym przykładzie.
Na przykład weź początkową tablicę jako 77, 33, 44, 11, 88, 22. W tym algorytmie sortowania znajduje się najmniejsza w tablicy. Najmniejszy element to 11. Jest zamieniany z elementem w indeksie 0 tablicy.
Teraz tablica to 11, 33, 44, 77, 88, 22.
Najmniejszy element znajduje się w indeksie 0, więc 11 jest teraz posortowane. Spośród pozostałych elementów najmniejszym jest 22. Jest on zamieniany z elementem indeksu 1st.
Teraz tablica to 11, 22, 44, 77, 88, 33.
Elementy 11 i 22 są już posortowane. Spośród pozostałych najmniejsza wartość to 33. Jest ona zamieniana z elementem indeksu 2nd.
Teraz tablica to 11, 22, 33, 77, 88, 44.
Elementy 11, 22 i 33 są już posortowane. Spośród pozostałych najmniejsza wartość to 44. Jest ona zamieniana z elementem indeksu 3rd.
Teraz tablica to 11, 22, 33, 44, 88, 66.
Elementy 11, 22, 33, 44 są już posortowane. Pozostałe elementy to 88 i 66. Element 66 jest zamieniany z elementem indeksu 4th.
Teraz tablica to 11, 22, 33, 44, 66, 88.
Jest to posortowana tablica przy użyciu algorytmu sortowania wyboru.
Rysunek 02: Przykład sortowania wyboru
Implementacja sortowania przez wstawianie jest jak powyżej. Początkowa tablica to 77, 33, 44, 11, 88. Po posortowaniu daje wynik 11, 33, 44, 77, 88.
Jakie jest podobieństwo między sortowaniem przez wstawianie i sortowaniem przez wybór?
Zarówno sortowanie przez wstawianie, jak i przez wybór są algorytmami sortowania
Jaka jest różnica między sortowaniem przez wstawianie a sortowaniem przez wybór?
Sortowanie przez wstawianie a sortowanie przez wybór |
|
| Sortowanie przez wstawianie to algorytm sortowania, który sortuje tablicę, przesuwając elementy jeden po drugim. | Sortowanie przez wybór to algorytm sortowania, który znajduje najmniejszy element w tablicy i wymienia element z pierwszą pozycją, następnie znajduje drugi najmniejszy element i wymienia go z elementem na drugiej pozycji i kontynuuje proces do cała tablica jest posortowana. |
| Proces | |
| Sortowanie przez wstawianie polega na posortowaniu listy podrzędnej przez porównanie dwóch elementów, aż posortowana zostanie cała tablica. | Sortowanie wyboru wybiera minimalny element i zamienia go z pierwszą pozycją, ponownie wybiera minimum dla reszty i zamienia go na drugą pozycję i kontynuuj ten proces do końca. |
| Stabilność | |
| Sortowanie przez wstawianie to stabilny algorytm sortowania. | Sortowanie przez wybór nie jest stabilnym algorytmem sortowania. |
Podsumowanie – sortowanie przez wstawianie a sortowanie przez wybór
Czasami konieczne jest sortowanie danych. W informatyce istnieją algorytmy do sortowania danych. W tym artykule omówiono dwa algorytmy sortowania, którymi są sortowanie przez wstawianie i sortowanie przez wybór. Sortowanie przez wstawianie to algorytm sortowania, który sortuje tablicę, przesuwając elementy jeden po drugim. Sortowanie przez wybór to algorytm sortowania, który znajduje najmniejszy element w tablicy i wymienia element z pierwszą pozycją, następnie znajduje drugi najmniejszy element i wymienia go z elementem na drugiej pozycji i kontynuuje proces, aż cała tablica zostanie posortowana. Różnica między sortowaniem przez wstawianie a sortowaniem przez wybór polega na tym, że sortowanie przez wstawianie porównuje dwa elementy naraz, podczas gdy sortowanie przez wybór wybiera minimalny element z całej tablicy i sortuje go.
Pobierz plik PDF z sortowaniem przez wstawianie a sortowaniem przez wybór
Możesz pobrać wersję PDF tego artykułu i używać jej do celów offline zgodnie z notatką cytowania. Proszę pobrać wersję PDF tutaj: Różnica między sortowaniem przez wstawianie a sortowaniem przez selekcję
