Algorytm sortowania przez wstawianie w języku C, C++, Java, Python Przykłady

Co to jest sortowanie przez wstawianie?

Sortowanie przez wstawianie to jeden z algorytmów sortowania przez porównywanie, który służy do sortowania elementów poprzez iterowanie po jednym elemencie na raz i umieszczanie elementu w jego odpowiednim miejscu w już uporządkowanym regionie.

Każdy element jest sekwencyjnie wstawiany do już posortowanej listy. Początkowy rozmiar posortowanej listy wynosi jeden. Algorytm sortowania przez wstawianie zapewnia, że ​​pierwsze k elementów zostanie posortowanych po k-tej iteracji pętli zewnętrznej.

Ponieważ sortowanie przez wstawianie generuje wynik stopniowo, jest intuicyjne w nauczaniu, łatwe do debugowania i stanowi solidną bazę dla bardzo małych danych wejściowych, w przypadku których bardziej złożone algorytmy spowodowałyby dodatkowe obciążenie bez mierzalnych korzyści.

Charakterystyka algorytmu sortowania przez wstawianie

Algorytm sortowania przez wstawianie ma następujące ważne cechy, które wyjaśniają jego zachowanie w rzeczywistych obciążeniach:

• Jest to stabilna technika sortowania, więc nie zmienia względnej kolejności równych elementów.
• Jest to wydajne rozwiązanie w przypadku mniejszych zbiorów danych, ale nieefektywne w przypadku większych list, gdzie dominuje wzrost kwadratowy.
• Sortowanie przez wstawianie jest adaptacyjne, co oznacza, że ​​zmniejsza całkowitą liczbę kroków, jeśli dane wejściowe są częściowo posortowane. Szyk jest dostarczany jako dane wejściowe, co zwiększa jego wydajność, ponieważ losowy dostęp umożliwia stałe przesunięcia czasowe podczas pętli wewnętrznej.
• Jest to algorytm działający w miejscu, więc nie wymaga dodatkowej pamięci proporcjonalnej do rozmiaru danych wejściowych.

Mając na uwadze te cechy, w następnej sekcji wyjaśniono podstawową operację wstawiania, która stanowi podstawę każdego przebiegu algorytmu.

Jak działa Wstaw Operapraca?

W algorytmie sortowania przez wstawianie operacja wstawiania służy do sortowania nieposortowanych elementów. Pomaga ona wstawić nowy element do już posortowanej listy, zachowując jednocześnie istniejącą kolejność sortowanego obszaru.

Pseudokod operacji wstawiania:

Rozważmy listę A złożoną z N elementów.

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

W powyższym przykładzie nowy element 6 jest wstawiany do już posortowanej listy. Poniższe kroki trace wewnętrzna pętla, gdy nowy element przemieszcza się w lewo, w kierunku swojej właściwej pozycji.

Krok 1) W porównaniu z lewym sąsiadującym elementem A[5], 9 > 6, zamieniamy położenie 9 i 6. Teraz element 6 zostaje przeniesiony do A[4].

Krok 2) Teraz porównujemy A[4] i A[3] i stwierdzamy, że A[3] > A[4], więc ponownie zamieniamy miejscami 6 i 8.

Krok 3) Porównajmy teraz A[3] i A[2]. Ponieważ A[2] > A[3], zamieniamy miejscami liczby 7 i 6.

Krok 4) Porównujemy A[1] i A[2]. Ponieważ A[1] < A[2], lewy sąsiadujący element nie jest już większy. Wnioskujemy, że 6 jest wstawione poprawnie i zatrzymujemy tutaj wewnętrzną pętlę.

Jak działa sortowanie przez wstawianie

Omówiona powyżej operacja wstawiania stanowi podstawę sortowania przez wstawianie. Procedura wstawiania jest wykonywana dla każdego elementu, a na końcu otrzymujemy posortowaną listę, ponieważ posortowany obszar rośnie o jeden element przy każdym zewnętrznym przejściu.

Powyższy rysunek ilustruje działanie sortowania przez wstawianie w strukturze danych. Początkowo w posortowanej podliście znajduje się tylko jeden element, tj. 4. Po wstawieniu elementu A[1], tj. 3, rozmiar posortowanej podlisty rośnie do 2, a algorytm kontynuuje ten schemat, aż do umieszczenia wszystkich elementów.

Mając już ustalony przepływ koncepcyjny, w poniższych sekcjach przedstawiono konkretne wdrożenia w C++, C i Python dzięki czemu możesz porównywać struktury pętli w różnych językach.

C++ Program do sortowania przez wstawianie

C++ Poniższa implementacja wykorzystuje dwie zagnieżdżone pętle: pętla zewnętrzna wybiera następny nieposortowany element, a pętla wewnętrzna przesuwa go w lewo, aż do znalezienia właściwej pozycji.

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

Wyjście:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code do sortowania przez wstawianie

Tę samą logikę można bezpośrednio przełożyć na język C. Standard printf wywołania zastępują wyjście strumienia, ale wzór zamiany wewnątrz pętli wewnętrznej jest identyczny z C++ wersja.

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

Wyjście:

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python Program do sortowania przez wstawianie

Python obsługuje zamianę krotekping w jednym wyrażeniu, więc wewnętrzna pętla jest bardziej zwarta niż jej C i C++ odpowiedników, zachowując przy tym to samo zachowanie algorytmiczne.

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

Wyjście:

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Właściwości sortowania przez wstawianie

Oto ważne właściwości sortowania przez wstawianie, które pomogą Ci zdecydować, czy jest to właściwe narzędzie:

• online: Sortowanie przez wstawianie umożliwia sortowanie elementów w miarę ich otrzymywania. Jeśli posortowaliśmy już listę elementów i dodaliśmy do niej kolejne, nie musimy ponownie uruchamiać całej procedury sortowania. Zamiast tego iterujemy jedynie po nowo dodanych elementach.
• W miejscu: Złożoność przestrzenna algorytmu sortowania przez wstawianie jest stała i nie wymaga dodatkowej przestrzeni. Algorytm ten sortuje elementy w miejscu.
• Stabilny: W sortowaniu przez wstawianie nie zamieniamy elementów, jeśli ich wartości są równe. Na przykład, jeśli dwa elementy, x i y, są równe, a x występuje przed y na liście nieposortowanej, to na liście posortowanej x nadal będzie występować przed y. Dzięki temu sortowanie przez wstawianie jest stabilne.
• Adaptacyjny: A algorytm sortowania Jest adaptacyjny, jeśli zajmuje mniej czasu, gdy elementy wejściowe lub podzbiór elementów są już posortowane. Jak omówiliśmy powyżej, najlepszy czas wykonania sortowania przez wstawianie wynosi O(N), a najgorszy O(N^2). Sortowanie przez wstawianie jest jednym z adaptacyjnych algorytmów sortowania.

Złożoność sortowania przez wstawianie

Poniższa dyskusja na temat złożoności obejmuje zarówno użycie pamięci, jak i czas wykonania, dzięki czemu można określić pozycję sortowania przez wstawianie w odniesieniu do alternatyw, takich jak Bubble Sortuj oraz Szybkie sortowanie.

Złożoność przestrzeni

Sortowanie przez wstawianie nie wymaga dodatkowej przestrzeni do sortowania elementów. Złożoność przestrzenna jest stała, tj. O(1), ponieważ niezależnie od rozmiaru danych wejściowych, używanych jest tylko kilka zmiennych tymczasowych.

Złożoność czasowa

Ponieważ sortowanie przez wstawianie iteruje element po elemencie, wymaga N-1 przebiegów do posortowania N elementów. W każdym przebiegu może nie wykonać żadnej zamiany, jeśli elementy są już posortowane, lub może wymagać wielu zamian, jeśli elementy są ułożone w kolejności malejącej.

• W przypadku przebiegu 1 minimalne wymagane zamiany wynoszą zero, a maksymalne wymagane zamiany wynoszą 1.
• W przypadku przebiegu 2 minimalne wymagane zamiany wynoszą zero, a maksymalne wymagane zamiany wynoszą 2.
• W przypadku przebiegu N minimalna wymagana zamiana wynosi zero, a maksymalna wymagana zamiana wynosi N.
• Minimalna wartość zamiany wynosi zero, więc najlepsza złożoność czasowa wynosi O(N) dla iteracji N przebiegów.
• Łączna maksymalna liczba zamian wynosi (1+2+3+4+…+N), tj. N(N+1)/2, więc najgorsza złożoność czasowa wynosi O(N^2).

Oto ważna złożoność czasowa sortowania przez wstawianie:

• Najgorszy przypadek złożoności: O(n^2): Sortowanie tablicy w kolejności malejącej, podczas gdy wymagana jest kolejność rosnąca, to najgorszy scenariusz.
• Najlepsza złożoność przypadku: O(n): Najlepszy przypadek występuje, gdy tablica jest już posortowana; pętla zewnętrzna wykonuje się n razy, a pętla wewnętrzna nie wykonuje się wcale. Jest tylko n porównań, więc złożoność jest liniowa.
• Średnia złożoność przypadku: O(n^2): Dzieje się tak, gdy elementy tablicy występują w nieuporządkowanej kolejności, która nie jest ani rosnąca, ani malejąca.

FAQ