Sortieralgorithmen: Insertion sort

ozelot47(71)

Published in

#de-stem

Words

119

Reading

1 min

Listen

Play

Ein weiterer bekannter Sortieralgorithmus ist der Insertion sort. Dieser Algorithmus ist auch stabil, da im Falle von Duplikaten die Reihenfolge nach der sortierung beibehalten wird. Auch hier wird eine nicht leere Liste von Objekten zum sortieren erwartet.

Die Funktionsweise des Verfahrens ist ähnlich wie die des Selection sort. Zunächst wird ein Element gesucht, was eventuell sortiert werden muss. Danach wird die Liste mit einer weiteren Schleife durchlaufen, um so Werte zu finden, die größer sind als der zu sortierende Wert. Diese Elemente werden dann um eine Position nach rechts gerückt, falls man aufsteigend sortieren möchte.
Die äußere Schleife durchläuft alle Indizes einzelnt, während die innere Schleife für die Verschiebeoperationen zuständig ist.

Insertion sort (c++)

#include 

void insertionSort(){
    const unsigned int SIZE = 10;
    unsigned int list[SIZE] = {56, 81, 3, 17, 35, 11, 8, 3, 17, 34};

    // for each element in the list
    for(unsigned int i = 0; i < SIZE; i++){
        unsigned int valueToSort = list[i];
        unsigned int k = i;

        // find a value to sort
        while( k > 0 && list[k-1] > valueToSort ){
            list[k] = list[k-1];
            k--;
        }
        list[k] = valueToSort;
    }

    for(unsigned int res = 0; res < SIZE; res++){
        std::cout << list[res] << "\n";
    }
}

int main(){
    insertionSort();
    return 0;
}