Třídění vložení: Algoritmus s C, C++, Java, Python Příklady

Co je řazení vložení?

Řazení vložení je jedním z algoritmů řazení pro porovnání, které se používají k řazení prvků iterací po jednom prvku a umístěním prvku na správnou pozici.

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í vložení zajišťuje, že prvních k prvků je seřazeno po k-té iteraci.

Charakteristika algoritmu řazení vložení

Algoritmus pro řazení vložení má následující důležité vlastnosti:

• Je to stabilní technika třídění, takže nemění relativní pořadí stejných prvků.
• Je efektivní pro menší soubory dat, ale není efektivní pro větší seznamy.
• Řazení vložení je adaptivní, což snižuje celkový počet kroků, pokud je seřazeno částečně. Řada je poskytován jako vstup, aby byl efektivní.

Jak funguje Insert Operapráce?

V algoritmu řazení vložení se operace vložení používá k řazení netříděných prvků. Pomáhá vložit nový prvek do již seřazeného seznamu.

Pseudokód operace vložení:

Uvažujme seznam A N prvků.

A[N-1] is the element to be inserted in the 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 má být nový prvek 6 vložen do již seřazeného seznamu.

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], opět prohodíme pozici 6 a 8.

Krok 3) Nyní porovnejte A[3] a A[2], protože A[2] > A[3] vymění pozici 7 a 6.

Krok 4) Porovnáme A[1] a A[2] a jako A[1] < A[2], tj. levý sousední prvek již není větší. Nyní dojdeme k závěru, že 6 je vložena správně, a zde algoritmus zastavíme.

Jak funguje řazení vložení

Operace vkládání diskutovaná výše je páteří řazení vkládání. Procedura vložení se provede na každém prvku a nakonec dostaneme seřazený seznam.

Výše uvedený příklad ukazuje fungování řazení vložení 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.

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

#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 Kód pro řazení vložení

#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í

#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í:

• Online: Třídění vložení může prvky třídit tak, jak je přijímá. To znamená, že pokud jsme již seřadili seznam prvků a přidali k seznamům nějaké další prvky, pak nemusíme spouštět celý postup řazení znovu. Místo toho musíme pouze opakovat nově přidané prvky.
• Na místě: Prostorová složitost algoritmu řazení vložení je konstantní a nevyžaduje další prostor. Tento algoritmus třídí prvky na místě.
• Stabilní: Při řazení vložením nezaměňujeme prvky, pokud jsou jejich hodnoty stejné. Například dva prvky, x a y, jsou stejné a x se objeví před y v nesetříděných seznamech, pak se v seřazeném seznamu objeví x před y. Díky tomu je řazení vložení stabilní.
• Adaptivní: A algoritmus třídění je adaptivní, pokud to trvá méně času, pokud jsou vstupní prvky nebo podmnožina prvků již seřazeny. Jak jsme diskutovali výše, nejlepší doba provozu při řazení je O(N) a nejhorší doba provozu je O(N^2). Vložení řazení je jedním z adaptivních třídicích algoritmů.

Složitost řazení vložení

Složitost vesmíru

Řazení vložení nevyžaduje další prostor pro řazení prvků, složitost prostoru je konstantní, tj. O(1).

Časová složitost

Protože řazení vložení iteruje každý prvek současně, vyžaduje N-1 průchodů k seřazení N prvků. Pro každý průchod může provést nulové záměny, pokud jsou prvky již setříděny, nebo záměnu, pokud jsou prvky uspořádány v sestupném pořadí.

• 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í swapy jsou (1+2+3+4+..+N) i. N(N+1)/2, nejhorší časová složitost je O(N^2).

Zde je důležitá časová složitost řazení vložení:

• Složitost nejhoršího případu: O(n2): Seřazení pole v sestupném pořadí, když je ve vzestupném pořadí, je nejhorší scénář.
• Nejlepší složitost případu: O(n): Složitost v nejlepším případě nastane, když je pole již seřazeno, vnější smyčka běží nkrát, zatímco vnitřní smyčka se nespustí vůbec. Existuje pouze n počet srovnání. Takže v tomto případě je složitost lineární.
• Průměrná složitost případu: O(n2): Stává se to, když se prvky pole vyskytují v neuspořádaném pořadí, které není ani vzestupné, ani sestupné.

Shrnutí

• Vložení řazení je metoda algoritmu řazení, která je založena na porovnání.
• Je to stabilní technika třídění, takže nemění relativní pořadí stejných prvků.
• U každého prvku se operace vložení používá k vložení prvku do seřazeného podseznamu.
• Řazení vložení je algoritmus řazení na místě.
• Nejhorší a průměrná časová složitost řazení je kvadratická, tj. O(N^2).
• Třídění vložení nevyžaduje žádný pomocný prostor.