Algoritmus řazení vkládáním s jazykem C C++, Java, Python Příklady

Co je řazení vložení?

Vkládání je jeden z algoritmů porovnávacího řazení používaných k řazení prvků iterací jednoho prvku po druhém a umístěním prvku na správnou pozici v již uspořádané oblasti.

Každý prvek je postupně vkládán do již seřazeného seznamu. Velikost již seřazeného seznamu je zpočátku jedna. Algoritmus řazení vkládáním zajišťuje, že prvních k prvků je seřazeno po k-té iteraci vnější smyčky.

Protože řazení vkládáním vytváří výsledek inkrementálně, je intuitivní na učení, snadno laditelné a představuje silný základ pro velmi malé vstupy, kde by složitější algoritmy přidaly režijní náklady bez měřitelných zisků.

Charakteristika algoritmu řazení vložení

Algoritmus pro řazení vložením má následující důležité vlastnosti, které vysvětlují jeho chování při reálných úlohách:

• Je to stabilní technika třídění, takže nemění relativní pořadí stejných prvků.
• Je efektivní pro menší datové sady, ale ne efektivní pro větší seznamy, kde dominuje kvadratický růst.
• Vkládání je adaptivní, což snižuje celkový počet kroků, pokud je vstup částečně seřazen. Řada je poskytován jako vstup, aby byl efektivní, protože náhodný přístup umožňuje konstantní časové posuny během vnitřní smyčky.
• Jedná se o algoritmus pracující na místě, takže nevyžaduje pomocné úložiště úměrné velikosti vstupu.

S ohledem na tyto vlastnosti následující část vysvětluje základní operaci vkládání, která pohání každý průchod algoritmu.

Jak funguje Insert Operapráce?

V algoritmu řazení vložením se operace vložení používá k řazení neseřazených prvků. Pomáhá vložit nový prvek do již seřazeného seznamu a zároveň zachovat stávající pořadí seřazené oblasti.

Pseudokód operace vkládání:

Uvažujme seznam A N prvků.

// 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

Ve výše uvedeném příkladu je do již seřazeného seznamu vložen nový prvek 6. Následující kroky tracvnitřní smyčku, jak se nový prvek posouvá doleva směrem ke své správné pozici.

Krok 1) V porovnání s levým sousedním prvkem A[5], 9 > 6, prohodíme pozici 9 a 6. Nyní je prvek 6 přesunut do A[4].

Krok 2) Nyní porovnáme A[4] a A[3] a zjistíme, že A[3] > A[4], takže opět prohodíme pozice 6 a 8.

Krok 3) Nyní porovnejte A[3] a A[2]. Jelikož A[2] > A[3], prohodíme si pozice 7 a 6.

Krok 4) Porovnáme A[1] a A[2]. Protože A[1] < A[2], levý sousední prvek již není větší. Dojdeme k závěru, že číslo 6 je vloženo správně, a zde ukončíme vnitřní smyčku.

Jak funguje řazení vložení

Výše popsaná operace vkládání je páteří řazení vkládáním. Procedura vkládání se provádí na každém prvku a na konci získáme seřazený seznam, protože seřazená oblast se při každém vnějším průchodu zvětšuje o jeden prvek.

Obrázek výše ukazuje fungování řazení vložením v datové struktuře. Zpočátku je v seřazeném podseznamu pouze jeden prvek, tj. 4. Po vložení A[1], tj. 3, se velikost seřazeného podseznamu zvětší na 2 a algoritmus v tomto vzoru pokračuje, dokud nejsou umístěny všechny prvky.

Po zavedení koncepčního toku následující části ukazují konkrétní implementace v C++, C a Python takže můžete porovnávat struktury smyček napříč jazyky.

C++ Program pro řazení vložení

Jedno C++ Níže uvedená implementace používá dvě vnořené smyčky: vnější smyčka vybere další neseřazený prvek a vnitřní smyčka jej posouvá doleva, dokud nenajde správnou pozici.

#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;
}

Výstup:

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

C Code pro řazení vložením

Stejná logika se přímo překládá do jazyka C. Standard printf volání nahrazují výstup streamu, ale vzor pro výměnu uvnitř vnitřní smyčky je identický s C++ verze.

#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;
}

Výstup:

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 pro řazení vložení

Python podporuje výměnu n-ticping v jednom výrazu, takže vnitřní smyčka je kompaktnější než její C a C++ protějšky při zachování stejného algoritmického chování.

#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=" ")

Výstup:

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

Vlastnosti řazení vložení

Zde jsou důležité vlastnosti řazení vložením, které vám pomohou rozhodnout se, kdy je to ten správný nástroj:

• Online: Vkládání prvků umožňuje třídit prvky hned, jak je přijímá. Pokud jsme již seznam prvků seřadili a přidáváme do seznamu další prvky, nemusíme celý třídicí postup spouštět znovu. Místo toho iterujeme pouze s nově přidanými prvky.
• Na místě: Prostorová složitost algoritmu řazení vložením je konstantní a nevyžaduje další prostor. Tento algoritmus řadí prvky na místě.
• Stabilní: V řazení vložením neprohazujeme prvky, pokud jsou jejich hodnoty stejné. Například pokud jsou dva prvky, x a y, stejné a x se v neseřazeném seznamu objeví před y, pak se v seřazeném seznamu x stále objeví před y. Díky tomu je řazení vložením stabilní.
• Adaptivní: A algoritmus třídění je adaptivní, pokud trvá kratší dobu, když jsou vstupní prvky nebo podmnožina prvků již seřazeny. Jak jsme uvedli výše, nejlepší doba běhu řazení vložením je O(N) a nejhorší doba běhu je O(N^2). Řazení vložením je jeden z adaptivních algoritmů řazení.

Složitost řazení vložení

Níže uvedená diskuse o složitosti zahrnuje jak využití paměti, tak i dobu běhu, takže můžete řazení vkládáním umístit proti alternativám, jako je například Bubble Seřadit a Rychlé třídění.

Složitost vesmíru

Vkládání prvků nevyžaduje k seřazení další prostor. Prostorová složitost je konstantní, tj. O(1), protože se bez ohledu na velikost vstupu používá pouze několik dočasných proměnných.

Časová složitost

Protože řazení vkládáním iteruje po jednom prvku, vyžaduje N-1 průchodů k seřazení N prvků. V každém průchodu může být provedeno nulové prohození, pokud jsou prvky již seřazeny, nebo může být potřeba mnoho prohození, pokud jsou prvky uspořádány sestupně.

• Pro průchod 1 jsou minimální požadované swapy nula a maximální požadované swapy jsou 1.
• Pro průchod 2 jsou minimální požadované swapy nula a maximální požadované swapy jsou 2.
• Pro průchod N je minimální požadovaný swap nula a maximální požadovaný swap je N.
• Minimální swap je nula, takže nejlepší časová složitost je O(N) pro opakování N průchodů.
• Celkový maximální počet swapů je (1+2+3+4+…+N), tj. N(N+1)/2, takže nejhorší časová složitost je O(N^2).

Zde je důležitá časová složitost řazení vkládáním:

• Složitost nejhoršího případu: O(n^2): Řazení pole sestupně, když je požadováno vzestupné pořadí, je nejhorší možný scénář.
• Nejlepší složitost případu: O(n): Nejlepší případ nastává, když je pole již seřazeno; vnější smyčka se spustí n-krát, zatímco vnitřní smyčka se nespustí vůbec. Probíhá pouze n porovnání, takže složitost je lineární.
• Průměrná složitost případu: O(n^2): K tomu dochází, když se prvky pole vyskytují v přerušovaném pořadí, které není ani vzestupné, ani sestupné.

Nejčastější dotazy