Elementare Sortierverfahren in C++

Inhalt

Einleitung
Selection Sort
Insertion Sort
Bubble Sort

Einleitung

Wer sich etwas mit der Programmierung beschäftigt, der kommt um das Sortieren von Daten nicht herum, wenn es auch nur einfache Highscore-Liste in einem Snake-Clon ist.
Für das Sortieren gibt es viele Algorithmen und ich werde hier einige elementare vorstellen.
Viel Spaß beim Ausprobieren ;)

Selection Sort

Selection Sort – sortieren durch (direktes) Auswählen. Das Sortieren erfolgt nach einem simplen Verfahren: Man sucht das kleinste Element in der Liste und vertauscht es mit dem ersten Element. Als nächstes sucht man ab der zweiten Position (auf der ersten Position steht schon das Kleinste) das kleinste Element und vertauscht es mit dem Element auf der Position zwei. Und so weiter und so fort bis man beim letzten Element angekommen ist, welches automatisch auch das größte Element ist.

// anzahl der elemente im Feld
const unsigned int laenge = 10;

// dieses Feld wird sortiert
int feld[laenge] = { 10,2,7,5,8,3,4,1,9,6 };

// Alle Elemente durchgehen (letztes ausgenommen)
for(unsigned int i = 0; i < laenge-1; i++)
{
    // Position des zurzeit kleinstes Elementes
    unsigned int min_pos = i;

    // unsortierten Teil des Feldes durchlaufen
    // und nach kleinstem Element suchen
    for(unsigned int j = i+1; j < laenge; j++)
        if(feld[j] < feld[min_pos] )
            min_pos = j;

    // Elemente vertauschen
    // Das kleinste Element kommt an das Ende
    // bereits sortierten Teils des Feldes
    int temp = feld[i];
    feld[i] = feld[min_pos];
    feld[min_pos] = temp;
}

Wie man sieht wird jedes Element nur ein Mal vertauscht, dafür werden aber viele Vergleiche durchgeführt, dadurch eignet sich dieses Algorithmus für Datenmengen mit großen Datensätzen und kleinen Schlüsseln.

Insertion Sort

Sortieren durch Einfügen ist ein Sortierverfahren das wahrscheinlich schon jeder benutzt hat – nach diesem Verfahren sortiert man das Spielkartenblatt.
Man beginnt von links nach rechts nacheinander zwei benachbarte Elemente zu vergleichen. Ist ein Element kleiner als sein Vorgänger, so wird das Element zwischengespeichert und alle Elementen die links davon liegen UND größer als das zwischengespeicherte Element sind, werden nacheinander eine stelle nach rechts verschoben. Die Stelle an der das zwischengespeicherte Element sich befand wird dabei überschrieben, dabei entsteht aber eine „Lücke“ direkt vor den verschobenen Elementen. In diese „Lücke“ wird das zwischengespeicherte Element platziert.

// anzahl der elemente im Feld
const unsigned int laenge = 10;

// dieses Feld wird sortiert
int feld[laenge] = { 10,2,7,5,8,3,4,1,9,6 };

// Alle Elemente durchgehen
for(unsigned int i = 1; i < laenge; i++)
{
    // das Element ist kleiner als der Vorgänger
    if(feld[i] < feld[i-1])
    {
        // Position des kleineren Elements merken
        int pos = i;

        // Das kleinere Element zwischenspeichern
        int kopie = feld[pos];

        // Jetzt alle Elemente die größer als "kopie" sind
        // einen platz nach rechts verschieben.
        while(feld[pos-1] > kopie && pos > 0 )
        {
            feld[pos] = feld[pos-1];
            pos--;
        }

        // die Kopie des kleineren Elementes in "die Lücke"
        // die links von den verschobenen Elementen entstanden ist kopieren
        feld[pos] = kopie;
    }
}

Insertion Sort ist gut geeignet für Daten, die schon teilweise sortiert sind.

Bubble Sort

Bubble Sort ist wohl der einfachste Sortieralgorithmus überhaupt. Der Algorithmus durchläuft das Feld in einer Schleife und vergleicht zwei benachbarte Elemente. Sind diese falsch angeordnet, so werden sie vertauscht. Ist man am ende der Liste angelangt, so beginnt man wieder von vorne. Dieser Vorgang wird so lange wiederholt bis das Feld ein Mal durchlaufen wird, ohne dabei ein einzelnes Element auszutauschen.

// anzahl der elemente im Feld
const unsigned int laenge = 10;

// dieses Feld wird sortiert
int feld[laenge] = { 10,2,7,5,8,3,4,1,9,6 };

// sagt uns, ob das feld sortiert ist
bool sortiert = false;

// feld unsortiert -> weiter machen
while(!sortiert)
{
    sortiert = true;

    // das komplette feld durchlaufen
    for(size_t i = 0; i < laenge-1; i++)
    {
        // und schauen ob benachbarte elemente
        // richtig angeordnet sind
        if(feld[i] > feld[i+1])
        {
            // wenn nicht, dann austauschen
            int temp = feld[i];
            feld[i] = feld[i+1];
            feld[i+1] = temp;

            // und merken, dass das feld unsortiert ist
            sortiert = false;

        }
    }
}

Wie immer bin ich für konstruktive Kritik immer offen :)