Beszúró rendezési 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 elemek rendezésére szolgálnak úgy, hogy egyszerre egy elemen iterálnak, és az elemet a megfelelő helyre helyezik egy már rendezett régión belül.

Minden elem szekvenciálisan beszúródik egy már rendezett listába. A már rendezett lista mérete kezdetben egy. A beszúrásos rendezési algoritmus biztosítja, hogy az első k elem a külső ciklus k-adik iterációja után rendezve legyen.

Mivel a beszúrásos rendezés inkrementálisan építi fel az eredményt, intuitív módon tanítható, könnyen hibakereshető, és erős alapot biztosít nagyon kis bemenetekhez, ahol a bonyolultabb algoritmusok többletterhelést jelentenének mérhető nyereség nélkül.

A beillesztési rendezési algoritmus jellemzői

A beszúrásos rendezés algoritmusa a következő fontos jellemzőkkel rendelkezik, amelyek magyarázzák a viselkedését valós munkaterhelések esetén:

• Ez egy stabil rendezési technika, így nem változtatja meg az egyenlő elemek egymáshoz viszonyított sorrendjét.
• Kisebb adathalmazok esetén hatékony, de nem túl hatásos nagyobb listák esetén, ahol a kvadratikus növekedés dominál.
• A beszúrásos rendezés adaptív, ami csökkenti a lépések teljes számát, ha a bemenet részben rendezett. Sor bemenetként szolgál a hatékonyság növelése érdekében, mivel a véletlen hozzáférés állandó idejű eltolásokat tesz lehetővé a belső ciklus alatt.
• Ez egy helybeni algoritmus, így nem igényel a bemeneti mérettel arányos kiegészítő tárhelyet.

Ezeket a tulajdonságokat szem előtt tartva a következő szakasz ismerteti az algoritmus minden menetét működtető alapvető beszúrási műveletet.

Hogyan működik az Insert Operamunka?

A beszúrásos rendezési algoritmusban a beszúrási műveletet rendezetlen elemek rendezésére használják. Segít egy új elem beszúrásában egy már rendezett listába, miközben megőrzi a rendezett régió meglévő sorrendjét.

A beszúrási művelet pszeudokódja:

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

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

A fenti példában egy új, 6-os elemet illesztünk be egy már rendezett listába. A következő lépések szükségesek. traca belső ciklust, ahogy az új elem balra vándorol a megfelelő pozíciója felé.

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 az A[4]-et és az A[3]-at, és azt kapjuk, hogy A[3] > A[4], tehát ismét felcseréljük a 6-os és a 8-as számok helyét.

Step 3) Most hasonlítsuk össze az A[3] és A[2] értékeket. Mivel A[2] > A[3], felcseréljük a 7 és a 6 helyét.

Step 4) Összehasonlítjuk az A[1] és A[2] értékeket. Mivel A[1] < A[2], a bal oldali szomszédos elem már nem nagyobb. Arra a következtetésre jutunk, hogy a 6-os szám helyesen lett beillesztve, és itt leállítjuk a belső ciklust.

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

A fent tárgyalt beszúrási művelet a beszúrásos rendezés gerincét képezi. A beszúrási eljárást minden elemen végrehajtjuk, és a végén megkapjuk a rendezett listát, mivel a rendezett régió minden külső menetben egy elemmel növekszik.

A fenti ábra a beszúrásos rendezés működését mutatja be egy adatstruktúrában. Kezdetben csak egy elem található a rendezett részlistában, azaz 4. Az A[1] beszúrása után, azaz 3, a rendezett részlista mérete 2-re nő, és az algoritmus ezt a mintát folytatja, amíg minden elem el nem került.

A koncepcionális folyamattal a következő szakaszok a konkrét megvalósításokat mutatják be C++, C és Python így összehasonlíthatod a ciklusstruktúrákat a különböző nyelveken.

C++ Program a beillesztési rendezéshez

Az C++ Az alábbi implementáció két egymásba ágyazott ciklust használ: a külső ciklus kiválasztja a következő rendezetlen elemet, a belső ciklus pedig balra tolja, amíg meg nem találja a megfelelő pozíciót.

#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 Code beszúrásos rendezéshez

Ugyanez a logika közvetlenül fordítható C-re. A szabvány printf A hívások lecserélik a stream kimenetét, de a belső cikluson belüli swap minta megegyezik a C++ változat.

#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

Python támogatja a tuple swap-otping egyetlen kifejezésben, így a belső ciklus kompaktabb, mint a C és C++ hasonló algoritmusok, miközben megőrzik ugyanazt az algoritmikus viselkedést.

#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 beszúrásos rendezés fontos tulajdonságai, amelyek segítenek eldönteni, hogy mikor ez a megfelelő eszköz:

• Online: A beszúrásos rendezés képes az elemek fogadásának megfelelően rendezni. Ha már rendeztünk egy elemlistát, és további elemeket fűzünk hozzá a listához, akkor nem kell újra lefuttatnunk a teljes rendezési eljárást. Ehelyett csak az újonnan hozzáadott elemeken iterálunk.
• A helyén: A beszúrásos rendezési algoritmus helykomplexitása állandó, és nem igényel extra helyet. Ez az algoritmus a helyükön rendezi az elemeket.
• Stabil: A beszúró rendezés során nem cseréljük fel az elemeket, ha értékük egyenlő. Például, ha két elem, x és y, egyenlő, és x az y előtt szerepel a rendezetlen listában, akkor a rendezett listában x továbbra is az y előtt fog szerepelni. Ez stabillá teszi a beszúró rendezést.
• Adaptív: A rendezési algoritmus adaptív, ha kevesebb időt vesz igénybe, ha a bemeneti elemek vagy az elemek egy részhalmaza már rendezve van. Amint azt fentebb tárgyaltuk, a beszúrásos rendezés legjobb futási ideje O(N), a legrosszabb pedig O(N^2). A beszúrásos rendezés az adaptív rendezési algoritmusok egyike.

A beillesztési rendezés összetettsége

Az alábbi bonyolultsági tárgyalás mind a memóriahasználatot, mind a futási időt lefedi, így a beszúrásos rendezést olyan alternatívákkal szemben is elhelyezheti, mint például a Bubble Rendezés és a Gyors rendezés.

Tér komplexitás

A beszúrásos rendezés nem igényel extra helyet az elemek rendezéséhez. A helykomplexitás állandó, azaz O(1), mivel a bemeneti mérettől függetlenül csak néhány ideiglenes változót használunk.

Idő komplexitás

Mivel a beszúrásos rendezés egyszerre egy elemet iterál, N elem rendezéséhez N-1 menetre van szükség. Minden menetben nulla cserét végezhet, ha az elemek már rendezve vannak, vagy sok cserére lehet szükség, 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.
• A maximális csereszám (1+2+3+4+…+N), azaz N(N+1)/2, tehát a legrosszabb időbonyolultság O(N^2).

Íme a beszúrásos rendezés fontos időbonyolultsága:

• A legrosszabb eset összetettsége: O(n^2): Egy tömb csökkenő sorrendbe rendezése, amikor növekvőnek kell lennie, a legrosszabb eset.
• Legjobb eset összetettsége: O(n): A legjobb eset akkor fordul elő, amikor a tömb már rendezett; a külső ciklus n-szer fut le, míg a belső ciklus egyáltalán nem. Csak n összehasonlítás van, így a bonyolultság lineáris.
• Átlagos ügykomplexitás: O(n^2): Ez akkor fordul elő, ha a tömb elemei összekeveredett sorrendben szerepelnek, amely se nem növekvő, se nem csökkenő.

GYIK