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 :)

12 Gedanken zu „Elementare Sortierverfahren in C++“

  1. Hi, ich glaube, ich habe einen kleinen Fehler gefunden. Fürne korrekte Ausführung darfs nicht heißen: i < laenge -1 , sondern entweder i < laenge oder i<=laenge-1.

    Wenn du das korrigierst, kannst du bei laenge =10 wie gewünscht zehn Zahlen in den Array reinpacken und diese werden von i=0 bis i<laenge,++, also bis zum zehnten Wert (wg. den 10 Zahlen!) durchlaufen.

    Falls i < laenge -1 bleibt werden lediglich 9 Zahlen durchlaufen, da i < laenge -1 und ++ im Maximalfall sein kann: i = 8 ++ also i = 9. Deshalb würden nur 9 Zahlen durchlaufen werden.

    Vielleich wars nur ein Tippfehler, oder ich stehe auf dem Schlauch. Deine sonstigen Tipps sind klasse!
    Gruß

  2. Nein, das ist schon richtig so. Nach i<=laenge-1 steht feld[i+1], wäre i = laenge-1, so würde man auf ein nicht existierendes Element zugreifen. Das letzte Element ist automatisch sortiert, da es zum letzten Wertepaar gehört.

  3. Ja stimmt, ich war nur verwirrt durch den output, probiere z.B. nach for:

    cout <<feld[i]<<endl;

    dann wird die 10 nicht ausgegeben.

    änderst du i < laenge -1 in i <= laenge -1, dann wird auch die 10 ausgegeben. Dadurch war ich ein bisschen verwirrt…

  4. Ja, um alle Elemente zu durchlaufen schreibt man
    for(size_t i = 0; i < laenge; i++)
    aber hier will man gerade nur alle-1 durchlaufen.
    Jetzt ist es hoffentlich geklärt ;)

  5. Hi, Seite ist gut gestaltet. Glückwunsch!

    zum Bubble-Sort:
    nach der for-Schleife kann man stets laenge dekremtieren (laenge–), damit die bereits sortierten Elemente rechts im Array nicht neu verglichen werden. Das kostet nur unnötig Rechenzeit

  6. laenge an sich kann man nicht dekrementieren, da konstant. Konstante wird aber für die Deklaration des Arrays gebraucht. Konstanten schreibt man übrigens groß.
    Mein Gesamtvorschlag für den Bubble-Sort:

    // 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 };
    
    int laenge = LAENGE; //laenge für Schleife
     
    // sagt uns, ob das feld sortiert ist
    bool sortiert = false;
     
    // feld unsortiert -&gt; weiter machen
    while(!sortiert)
    {
        sortiert = true;
     
        // das komplette feld durchlaufen
        for(int i = 0; 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;
             }
        }
        laenge--; //die "weiter rechts" liegenden Elemente sind bereits einsortiert!
    }
    

Schreibe einen Kommentar