Beszúrás rendezése: Algoritmus C-vel, C++, Java, Python Példák

Mi az a beillesztési rendezés?

A beszúrásos rendezés egyike az összehasonlító rendezési algoritmusoknak, amelyek az elemek rendezésére szolgálnak úgy, hogy egyszerre csak egy elemet iterálnak, és az elemet a megfelelő pozícióba helyezik.

Minden elem egymás után kerül beillesztésre egy már rendezett listába. A már rendezett lista mérete kezdetben egy. A beillesztési rendezési algoritmus biztosítja, hogy az első k elem a k-adik iteráció után legyen rendezve.

A beillesztési rendezési algoritmus jellemzői

A beillesztési rendezés algoritmusának a következő fontos jellemzői vannak:

• Ez egy stabil rendezési technika, így nem változtatja meg az egyenlő elemek egymáshoz viszonyított sorrendjét.
• Hatékony kisebb adatkészleteknél, de nem hatékony nagyobb listáknál.
• A beszúrásos rendezés adaptív, ami csökkenti a lépések teljes számát, ha részlegesen van rendezve. Sor bemenetként szolgál a hatékonyság érdekében.

Hogyan működik az Insert Operamunka?

A Beillesztési rendezés algoritmusban a beszúrási művelet a rendezetlen elemek rendezésére szolgál. Segít új elem beszúrása egy már rendezett listába.

A beillesztési művelet pszeudokódja:

Tekintsünk egy N elemből álló A listát.

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   

A fenti példában egy új 6 elemet kell beilleszteni egy már rendezett listába.

Step 1) Összehasonlítva az A[5] bal szomszédos elemével, 9 > 6, felcseréljük a 9-es és a 6-os helyzetét. Most a 6. elem átkerül A[4]-be.

Step 2) Most összehasonlítjuk A[4]-et és A[3]-t, és azt találjuk, hogy A[3] > A[4], ismét felcseréljük a 6-ot és a 8-at.

Step 3) Hasonlítsa össze az A[3]-t és az A[2]-t, mivel A[2] > A[3] felcseréli a 7 és a 6 helyzetét.

Step 4) Összehasonlítjuk A[1]-et és A[2]-t, és mivel A[1] < A[2], azaz a bal szomszédos elem már nem nagyobb. Most arra a következtetésre jutunk, hogy a 6-os helyesen lett beszúrva, és itt leállítjuk az algoritmust.

Hogyan működik a beszúrásos rendezés

A fent tárgyalt beszúrási művelet a beillesztési rendezés gerince. A beszúrási eljárás minden elemen lefut, és a végén megkapjuk a rendezett listát.

A fenti példaábra bemutatja a beillesztési rendezés működését az adatstruktúrában. Kezdetben csak egy elem van a rendezett allistában, azaz 4. Az A[1], azaz a 3 beszúrása után a rendezett allista mérete 2-re nő.

C++ Program a beillesztési rendezéshez

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

output:

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

C Beillesztési rendezés kódja

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

output:

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 a beillesztési rendezéshez

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

output:

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

A beillesztési rendezés tulajdonságai

Íme a beillesztési rendezés fontos tulajdonságai:

• Online: A beillesztési rendezés fogadáskor rendezheti az elemeket. Vagyis ha már rendeztünk egy elemlistát, és a listákhoz még néhány elemet csatoltunk, akkor nem kell újra lefuttatni a teljes rendezési eljárást. Ehelyett csak az újonnan hozzáadott elemeket kell iterálnunk.
• A helyén: A beillesztési rendezési algoritmus térbeli összetettsége állandó, és nem igényel extra helyet. Ez az algoritmus a helyükre rendezi az elemeket.
• Stabil: A beszúrásos rendezésnél nem cseréljük fel az elemeket, ha azok értéke egyenlő. Például két elem, az x és az y egyenlő, és az x a rendezetlen listákban y előtt jelenik meg, majd a rendezett listában x az y előtt. Ez stabillá teszi a beillesztési rendezést.
• Adaptív: A rendezési algoritmus adaptív, ha kevesebb időbe telik, ha a bemeneti elemek vagy elemek részhalmaza már rendezve van. Ahogy fentebb tárgyaltuk, a beillesztési rendezés legjobb futási ideje O(N), a legrosszabb futási idő pedig O(N^2). A beszúrásos rendezés az adaptív rendezési algoritmusok egyike.

A beillesztési rendezés összetettsége

Tér komplexitás

A beillesztési rendezés nem igényel extra helyet az elemek rendezéséhez, a tér összetettsége állandó, azaz O(1).

Idő komplexitás

Mivel a beszúrási rendezés minden elemet egyidejűleg iterál, N-1 lépésre van szükség az N elem rendezéséhez. Minden egyes lépésnél nulla cserét hajthat végre, ha az elemek már rendezve vannak, vagy cserélhet, ha az elemek csökkenő sorrendben vannak elrendezve.

• Az 1. átutaláshoz a minimálisan szükséges csereügylet nulla, a maximálisan pedig 1.
• Az 2. átutaláshoz a minimálisan szükséges csereügylet nulla, a maximálisan pedig 2.
• N passz esetén a minimálisan szükséges swap nulla, a maximálisan pedig N.
• A minimális csere nulla, így a legjobb időbonyolultság O(N) N lépés iterációjához.
• Az összes maximális csereügylet (1+2+3+4+..+N) i. N(N+1)/2, a legrosszabb időbonyolítás az O(N^2).

Íme a beillesztési rendezés fontos időbeli összetettsége:

• A legrosszabb eset összetettsége: O(n2): Egy tömb csökkenő sorrendbe rendezése növekvő sorrendben a legrosszabb forgatókönyv.
• Legjobb eset összetettsége: O(n): A legjobb eset bonyolultsága akkor következik be, amikor a tömb már rendezve van, a külső ciklus n-szer fut, míg a belső ciklus egyáltalán nem fut. Csak n számú összehasonlítás van. Tehát ebben az esetben a komplexitás lineáris.
• Átlagos ügykomplexitás: O(n2): Akkor fordul elő, ha egy tömb elemei kevert sorrendben fordulnak elő, ami nem növekvő és nem csökkenő.

Összegzésként

• A beszúrásos rendezés egy rendezési algoritmus, amely az összehasonlításon alapul.
• Ez egy stabil rendezési technika, így nem változtatja meg az egyenlő elemek egymáshoz viszonyított sorrendjét.
• Minden elemnél a beszúrás műveletet használjuk az elem beszúrására a rendezett allistába.
• A beszúrásos rendezés egy helyben történő rendezési algoritmus.
• A beillesztési rendezés legrosszabb és átlagos időbonyolultsága másodfokú, azaz O(N^2).
• A beszúrás rendezése nem igényel segédterületet.