Sortowanie przez wstawianie a sortowanie przez wybór

Próbuję zrozumieć różnice między sortowaniem przez wstawianie a sortowaniem przez wybór.

Wydaje się, że oba mają dwa składniki: listę nieposortowaną i listę posortowaną. Obaj wydają się pobierać jeden element z nieposortowanej listy i umieszczać go na posortowanej liście w odpowiednim miejscu. Widziałem niektóre witryny / książki mówiące, że sortowanie przez wybór robi to, zamieniając pojedynczo, podczas gdy sortowanie przez wstawianie po prostu znajduje właściwe miejsce i wstawia je. Jednak widziałem inne artykuły, które mówią coś, mówiąc, że sortowanie przez wstawianie również zamienia. W konsekwencji jestem zdezorientowany. Czy jest jakieś źródło kanoniczne?

Sortowanie przez wybór:

Mając listę, weź bieżący element i zamień go na najmniejszy element po prawej stronie bieżącego elementu.

Sortowanie przez wstawianie:

Mając listę, weź bieżący element i wstaw go w odpowiednim miejscu listy, dostosowując listę za każdym razem, gdy wstawiasz. Jest to podobne do układania kart w grze karcianej.

Złożoność czasowa sortowania przez wybieranie jest zawsze n(n - 1)/2, podczas gdy sortowanie przez wstawianie ma większą złożoność czasową, ponieważ jest to najgorsza złożoność przypadku n(n - 1)/2. Generalnie będzie to wymagało mniejszych lub równych porównań n(n - 1)/2.

Źródło: http://cheetahonfire.blogspot.com/2009/05/selection-sort-vs-insertion-sort.html

Zarówno sortowanie przez wstawianie, jak i sortowanie przez wybór mają zewnętrzną pętlę (nad każdym indeksem) i wewnętrzną pętlę (nad podzbiorem indeksów). Każde przejście pętli wewnętrznej rozszerza posortowany region o jeden element kosztem regionu niesortowanego, aż skończą się nieposortowane elementy.

Różnica polega na tym, co robi pętla wewnętrzna:

• W sortowaniu przez wybór pętla wewnętrzna znajduje się nad nieposortowanymi elementami. Każdy przebieg wybiera jeden element i przesuwa go w jego ostateczne położenie (na bieżącym końcu sortowanego regionu).

• Podczas sortowania przez wstawianie każdy przebieg wewnętrznej pętli iteruje po posortowanych elementach. Posortowane elementy są przesuwane, aż pętla znajdzie właściwe miejsce do wstawienia kolejnego nieposortowanego elementu.

Tak więc w sortowaniu przez wybór posortowane elementy są znajdowane w kolejności wyjściowej i pozostają na miejscu, gdy zostaną znalezione. I odwrotnie, w sortowaniu przez wstawianie nieposortowane elementy pozostają na miejscu, dopóki nie zostaną wykorzystane w kolejności wejściowej, podczas gdy elementy posortowanego regionu są nadal przemieszczane.

Jeśli chodzi o zamianę: sortowanie przez wybór wykonuje jedną zamianę na przebieg pętli wewnętrznej. Sortowanie przez wstawianie zazwyczaj zapisuje element, który ma być wstawiony, tak jak temp przed wewnętrzną pętlą, pozostawiając miejsce dla wewnętrznej pętli na przesunięcie posortowanych elementów o jeden w górę, a następnie kopiowanie tempdo punktu wstawiania.

SORTOWANIE SELEKCJI
Załóżmy, że istnieje tablica liczb zapisana w szczególny / losowy sposób i powiedzmy, że mamy uporządkować w kolejności rosnącej, więc bierzemy po jednej liczbie na raz i zastępujemy je najmniejszą liczbą. dostępne na liście. wykonując ten krok, ostatecznie uzyskamy pożądany rezultat.

SORTOWANIE WSTAWEK
Pamiętając o podobnym założeniu, jedyną różnicą jest to, że tym razem wybieramy po jednym numerze i wstawiamy go do wstępnie wyselekcjonowanej części, co zmniejszyło porównania i przez to jest bardziej wydajne.

Możliwe, że zamieszanie jest spowodowane tym, że porównujesz opis sortowania połączonej listy z opisem sortowania tablicy . Ale nie jestem pewien, ponieważ nie zacytowałeś swoich źródeł.

Najłatwiejszym sposobem na zrozumienie algorytmów sortowania jest często uzyskanie szczegółowego opisu algorytmu (nie są to niejasne rzeczy typu „ten rodzaj używa zamiany. Gdzieś. Nie mówię gdzie”), zdobycie kilku kart do gry (5-10 powinno wystarczyć dla prostych algorytmów sortowania) i uruchom algorytm ręcznie.

Sortowanie przez wybór: przejrzyj nieposortowane dane w poszukiwaniu najmniejszego pozostałego elementu, a następnie zamień je na pozycję bezpośrednio po posortowanych danych. Powtarzaj, aż skończysz. Podczas sortowania listy nie musisz zamieniać najmniejszego elementu na miejsce, zamiast tego możesz usunąć węzeł listy ze starej pozycji i wstawić go w nowym.

Sortowanie przez wstawianie: weź element znajdujący się bezpośrednio po posortowanych danych, przejrzyj posortowane dane, aby znaleźć miejsce, w którym można je umieścić, i umieść je tam. Powtarzaj, aż skończysz.

Sortowanie przez wstawianie może używać zamiany w fazie "skanowania", ale nie musi i nie jest to najbardziej efektywny sposób, chyba że sortujesz tablicę typu danych, których: (a) nie można przenosić, tylko kopiować lub zamieniać; oraz (b) jest droższe do kopiowania niż do zamiany. Jeśli sortowanie przez wstawianie używa zamiany, działa to tak, że jednocześnie wyszukujesz miejsce i umieszczasz tam nowy element, wielokrotnie zamieniając nowy element z elementem znajdującym się bezpośrednio przed nim, tak długo, jak poprzedni element jest większy niż to. Po dotarciu do elementu, który nie jest większy, znalazłeś właściwą lokalizację i przechodzisz do następnego nowego elementu.

Logika obu algorytmów jest dość podobna. Oba mają częściowo posortowaną pod tablicę na początku tablicy. Jedyną różnicą jest sposób wyszukiwania następnego elementu do umieszczenia w posortowanej tablicy.

• Sortowanie przez wstawianie : wstawia następny element we właściwej pozycji;

• Sortowanie przez wybór : wybiera najmniejszy element i zamienia go na aktualny;

Ponadto sortowanie przez wstawianie jest stabilne, w przeciwieństwie do sortowania przez wybór .

Zaimplementowałem oba w pythonie i warto zwrócić uwagę, jak są podobne:

def insertion(data):
    data_size = len(data)
    current = 1
    while current < data_size:
        for i in range(current):
            if data[current] < data[i]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

Z niewielką zmianą możliwe jest wykonanie algorytmu Sortowanie przez wybór.

def selection(data):
    data_size = len(data)
    current = 0
    while current < data_size:
        for i in range(current, data_size):
            if data[i] < data[current]:
                temp = data[i]
                data[i] = data[current]
                data[current] = temp

        current += 1

    return data

Krótko mówiąc, myślę, że sortowanie przez wybór wyszukuje najpierw najmniejszą wartość w tablicy, a następnie wykonuje zamianę, podczas gdy sortowanie przez wstawianie pobiera wartość i porównuje ją z każdą wartością pozostawioną (za nią). Jeśli wartość jest mniejsza, zamienia się. Następnie ta sama wartość jest ponownie porównywana i jeśli jest mniejsza od wartości znajdującej się za nią, zamienia się ponownie. Mam nadzieję, że to ma sens!

W skrócie,

Sortowanie przez wybór: wybierz pierwszy element z niesortowanej tablicy i porównaj go z pozostałymi nieposortowanymi elementami. Jest podobne do sortowania bąbelkowego, ale zamiast zamieniać mniejsze elementy, utrzymuje aktualizację indeksu najmniejszego elementu i zamienia go na końcu każdej pętli .

Sortowanie przez wstawianie: jest przeciwieństwem sortowania przez wybór, w którym wybiera pierwszy element z niesortowanej pod-tablicy i porównuje go z posortowaną pod-tablicą i wstawia najmniejszy element, w którym został znaleziony, i przesuwa wszystkie posortowane elementy z prawej strony do pierwszego nieposortowanego elementu.

Spróbuję jeszcze raz: zastanów się, co dzieje się w szczęśliwym przypadku prawie posortowanej tablicy.

Podczas sortowania można przyjąć, że tablica składa się z dwóch części: po lewej stronie - posortowana, po prawej - nieposortowanej.

Sortowanie przez wstawianie - wybierz pierwszy nieposortowany element i spróbuj znaleźć dla niego miejsce wśród już posortowanych części. Ponieważ wyszukujesz od prawej do lewej, może się zdarzyć, że pierwszy posortowany element, z którym porównujesz (największy, najbardziej po prawej w lewej części) jest mniejszy niż wybrany element, więc możesz natychmiast przejść do następnego nieposortowanego elementu.

Sortowanie przez wybór - wybierz pierwszy nieposortowany element i spróbuj znaleźć najmniejszy element z całej niesortowanej części i zamień te dwa, jeśli jest to pożądane. Problem polega na tym, że ponieważ właściwa część jest nieposortowana, za każdym razem musisz przemyśleć każdy element, ponieważ nie możesz mieć pewności, czy jest, czy nie ma nawet mniejszego elementu niż wybrany.

. Btw, to jest dokładnie to, co sortowanie przez kopcowanie ulepsza wyboru sortowania - jest w stanie dużo szybciej odnaleźć najmniejszy element ze względu na stercie .

Sortowanie przez wybór: Kiedy zaczynasz budować posortowaną podlistę, algorytm zapewnia, że ​​posortowana podlista jest zawsze całkowicie posortowana, nie tylko pod względem własnych elementów, ale także pod względem całej tablicy, tj. Zarówno posortowanej, jak i niesortowanej podlisty. W ten sposób nowy najmniejszy element znaleziony raz z niesortowanej podlisty byłby po prostu dołączany na końcu posortowanej podlisty.

Sortowanie przez wstawianie: Algorytm ponownie dzieli tablicę na dwie części, ale tutaj element jest wybierany z drugiej części i wstawiany we właściwej pozycji do pierwszej części. To nigdy nie gwarantuje, że pierwsza część zostanie posortowana pod względem pełnej tablicy, chociaż oczywiście w ostatnim przebiegu każdy element znajduje się na właściwej pozycji posortowanej.

Oba algorytmy ogólnie działają w ten sposób

Krok 1: następnie weź następny nieposortowany element z nieposortowanej listy

Krok 2: umieść go we właściwym miejscu na posortowanej liście.

Jeden z kroków jest łatwiejszy dla jednego algorytmu i odwrotnie.

Sortowanie przez wstawianie : Bierzemy pierwszy element nieposortowanej listy i umieszczamy go gdzieś na posortowanej liście . Wiemy, gdzie wziąć następny element (pierwsza pozycja na nieposortowanej liście), ale potrzeba trochę pracy, aby znaleźć miejsce, w którym go umieścić ( gdzieś ). Krok 1 jest łatwy.

Sortowanie przez wybór : bierzemy element gdzieś z niesortowanej listy, a następnie umieszczamy go na ostatniej pozycji posortowanej listy. Musimy znaleźć następny element (najprawdopodobniej nie znajduje się on na pierwszej pozycji nieposortowanej listy, a raczej gdzieś ), a następnie umieścić go na końcu posortowanej listy. Krok 2 jest łatwy

Wewnętrzna pętla sortowania przez wstawianie przechodzi przez już posortowane elementy (w przeciwieństwie do sortowania przez wybieranie). Pozwala to na przerwanie pętli wewnętrznej po znalezieniu właściwej pozycji . Co oznacza że:

1. W przeciętnym przypadku wewnętrzna pętla przejdzie tylko przez połowę swoich elementów.
2. Wewnętrzna pętla zostanie przerwana nawet wcześniej, jeśli tablica jest prawie posortowana.
3. Wewnętrzna pętla zostanie przerwana natychmiast, jeśli tablica jest już posortowana, przez co złożoność sortowania przez wstawianie jest w tym przypadku liniowa.

Sortowanie przez wybór zawsze będzie musiało przechodzić przez wszystkie elementy pętli wewnętrznej. Dlatego sortowanie przez wstawianie jest przeważnie preferowane niż sortowanie przez wybór. Ale z drugiej strony sortowanie przez wybór powoduje znacznie mniej zamian elementów, co może być ważniejsze w niektórych przypadkach.

Zasadniczo sortowanie przez wstawianie działa na zasadzie porównywania dwóch elementów naraz, a sortowanie przez wybieranie wybiera minimalny element z całej tablicy i sortuje go.

Koncepcyjnie sortowanie przez wstawianie sortuje listę podrzędną, porównując dwa elementy, aż cała tablica zostanie posortowana, podczas gdy sortowanie przez wybór wybiera minimalny element i zamienia go na pierwszą pozycję, drugi minimalny element na drugą pozycję i tak dalej.

Sortowanie przez wstawianie można wyświetlić jako:

    for(i=1;i<n;i++)
        for(j=i;j>0;j--)
            if(arr[j]<arr[j-1])
                temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;

Sortowanie przez wybór można wyświetlić jako:

    for(i=0;i<n;i++)
        min=i;
        for(j=i+1;j<n;j++)
        if(arr[j]<arr[min])
        min=j;
        temp=arr[i];
        arr[i]=arr[min];
        arr[min]=temp;

Wybór tych 2 algorytmów sortowania sprowadza się do zastosowanej struktury danych.

Kiedy używasz tablic, użyj sortowania przez wybór (chociaż dlaczego, kiedy możesz użyć qsort?). Jeśli korzystasz z list połączonych, użyj sortowania przez wstawianie.

To dlatego, że:

• Przechodzenie przez listę połączoną jest droższe niż tablice.
• Wstawianie listy połączonej jest znacznie tańsze niż tablice.

Sortowanie przez wstawianie wstawia nową wartość w środek posortowanego segmentu. Dlatego dane muszą być „wypychane”. Jednak gdy używasz listy połączonej, przekręcając 2 wskaźniki, skutecznie odepchnąłeś całą listę z powrotem. W tablicy musisz wykonać n - i zamiany, aby przesunąć wartości z powrotem, co może być bardzo kosztowne.

Sortowanie przez wybór zawsze dopisuje na końcu, więc nie ma tego problemu podczas używania tablic. W związku z tym dane nie muszą być „wypychane”.

Proste wyjaśnienie może wyglądać następująco:

Podane : nieposortowana tablica lub lista liczb.

Stwierdzenie problemu : aby posortować listę / tablicę liczb w porządku rosnącym, aby zrozumieć różnicę między sortowaniem przez wybór i sortowaniem przez wstawianie.

Sortowanie przez wstawianie:Widzisz listę od góry do dołu, aby ułatwić zrozumienie. Pierwszy element uważamy za naszą początkową wartość minimalną. Chodzi o to, że przechodzimy przez każdy indeks tej listy / tablicy liniowo, aby dowiedzieć się, czy w jakimkolwiek indeksie jest jakikolwiek inny element, który ma mniejszą wartość niż początkowa wartość minimalna. Jeśli znajdziemy taką wartość, po prostu zamieniamy wartości na ich indeksach, czyli powiedzmy, że 15 było minimalną wartością początkową przy indeksie 1 i podczas liniowego przechodzenia indeksów natrafiamy na liczbę o mniejszej wartości, powiedzmy 7 pod indeksem 9 Teraz ta wartość 7 pod indeksem 9 jest zamieniana na indeks 1 mający 15 jako wartość. To przemierzanie będzie kontynuowało porównywanie wartości bieżącego indeksu z pozostałymi indeksami w celu zamiany na mniejszą wartość. To trwa do przedostatniego indeksu listy / tablicy,

Sortowanie przez wybór:Załóżmy, że pierwszy element indeksu listy / tablicy jest posortowany. Teraz z elementu w drugim indeksie porównujemy go z jego poprzednim indeksem, aby sprawdzić, czy wartość jest mniejsza. Przejście można wizualizować w dwóch częściach, posortowanych i nieposortowanych. Można by wizualizować sprawdzenie porównania od nieposortowanego do posortowanego dla danego indeksu na liście / tablicy. Powiedzmy, że masz wartość 19 pod indeksem 1 i wartość 10 pod indeksem 3. Rozważamy przechodzenie od niesortowanych do posortowanych, tj. Od prawej do lewej. Powiedzmy, że musimy sortować według indeksu 3. Widzimy, że ma on mniejszą wartość niż indeks 1, gdy porównujemy go od prawej do lewej. Po zidentyfikowaniu, po prostu umieszczamy tę liczbę 10 w indeksie 3 w miejscu indeksu 1 o wartości 19. Oryginalna wartość 19 w indeksie 1 zostaje przesunięta o jedno miejsce w prawo.

Nie dodałem żadnego kodu, ponieważ wydaje się pytanie o zrozumienie koncepcji metody przechodzenia.

Sortowanie przez wstawianie nie zamienia rzeczy. Mimo że korzysta ze zmiennej tymczasowej, celem wykorzystania zmiennej temp. Jest sytuacja, gdy stwierdzimy, że wartość w indeksie jest mniejsza w porównaniu do wartości z poprzedniego indeksu, przesuwamy większą wartość w miejsce wartości o mniejszej wartości indeks, który nadpisuje rzeczy. Następnie używamy temp var do zastąpienia poprzedniego indeksu. Przykład: 10, 20, 30, 50, 40. iteracja 1: 10, 20, 30, 50, 50. [temp = 40] iteracja 2: 10,20, 30, 40 (wartość temp), 50. Więc po prostu wstaw wartość w żądanym miejscu z jakiejś zmiennej.

Ale kiedy rozważamy sortowanie przez wybór, najpierw znajdujemy indeks o niższej wartości i zamieniamy tę wartość na wartość z pierwszego indeksu i kontynuujemy wymianę, aż wszystkie indeksy zostaną posortowane. To dokładnie to samo, co tradycyjna zamiana dwóch liczb. Przykład: 30, 20, 10, 40, 50. Iteracja 1: 10, 20, 30, 40, 50. Tutaj temp var jest używany wyłącznie do zamiany.

Sortowanie przez wstawianie znacznie bardziej zmienia ten wybór. Oto przykład:

Wspólną cechą ich obu jest to, że oboje używają partycji do rozróżnienia posortowanej części tablicy od nieposortowanej.

Różnica polega na tym, że przy sortowaniu przez wybór masz gwarancję, że posortowana część tablicy nie zmieni się podczas dodawania elementów do posortowanej partycji.

Powodem jest to, że selekcja wyszukuje minimum nieposortowanego zbioru i dodaje je zaraz po ostatnim elemencie posortowanego zbioru, zwiększając w ten sposób posortowany zbiór o 1.

Z drugiej strony, wstawianie dba tylko o następny napotkany element, który jest pierwszym elementem w niesortowanej części tablicy. Wziął ten element i po prostu wpasuje go we właściwe miejsce w posortowanym zestawie.

Sortowanie przez wstawianie zawsze będzie lepszym kandydatem dla tablic, które są tylko częściowo sortowane, ponieważ marnujesz operacje na znalezienie minimum.

Wniosek:

Sortowanie przez wybór przyrostowo dodaje element na końcu, znajdując minimalny element w nieposortowanej sekcji.

Sortowanie przez wstawianie propaguje pierwszy element znaleziony w nieposortowanej sekcji do dowolnego miejsca w posortowanej sekcji.

Chociaż złożoność czasowa sortowania przez wybór i sortowania przez wstawianie jest taka sama, to znaczy n (n - 1) / 2. Średnia wydajność sortowania przez wstawianie jest lepsza. Testowane na moim procesorze i5 z losowymi liczbami całkowitymi 30000, sortowanie przez wybór trwało średnio 1,5 sekundy, a sortowanie przez wstawianie średnio 0,6 sekundy.

W kategoriach laika (i prawdopodobnie najłatwiejszy sposób na osiągnięcie wysokiego poziomu zrozumienia problemu)

Sortowanie bąbelkowe jest podobne do stania w kolejce i próbowania sortowania według wysokości. Ciągle przełączasz się z osobą obok, aż znajdziesz się we właściwym miejscu. Odbywa się to od lewej (lub prawej w zależności od implementacji) i przełączasz się, aż wszyscy zostaną posortowani.

Jednak w sortowaniu przez wybór to, co robisz, jest podobne do układania kart. Patrzysz na karty, bierzesz najmniejszą, kładziesz ją maksymalnie w lewo i tak dalej.

selekcja - zaznaczenie określonego elementu (najniższego) i zamiana go na i (liczba iteracji) th element. (tj. pierwsza, druga, trzecia .......), tworząc posortowaną listę po jednej stronie.

wstawianie - porównanie pierwszego z drugim porównaniem trzeciego z drugim i pierwszym porównaniem czwartego z trzecim, drugim i pierwszym ...

łącze, w którym porównywane są wszystkie sortowania