Show Menu
Cheatography
  1. Home >
  2. Cheat Sheets >

Sortierverfahren Cheat Sheet (DRAFT) by

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Sortieren durch direktes Einfügen

Beschr­eibung
Dieser Methode liegt folgende Idee zugrunde:
Das zu sortie­rende Array wird gedanklich in einen linken und rechten Teil getrennt.
Der linke Teil ist eine bereits sortierte Sequenz, in die die Elemente des rechten Teils nachei­nander einsor­tiert werden müssen.
Zu Beginn des Sortie­rvo­rgangs besteht der bereits sortierte linke Teil nur aus dem ersten Element des Arrays (jedes Element stellt für sich allein eine sortierte Sequenz der Länge eins dar).
Alle anderen Elemente gehören zum unsort­ierten rechten Teil.
Solange nun der rechte Teil nicht leer ist, wird das jeweils erste Element des rechten Teils in die sortierte Sequenz eingefügt.
Einfügen heißt dabei, das Element solange mit seinem linken Nachbarn zu vertau­schen, bis dieser entweder kleiner ist oder der linke Rand des Arrays erreicht wird (dieses Element ist dann das kleinste bisher gefund­ene).
Beispi­elf­unktion
 
void Insert­Sor­t(int *Array, int Anzahl) 
 { 
    int i; // erstes Element im unsort­ierten Teil 
    int j; // Laufindex zum Einsor­tieren 
    int temp; // fuer Austausch zweier Elemente 
  
    for (i = 1; i < Anzahl; i++) 
    { 
       j = i; 
       while (j > 0 && *(Array + j) < *(Array + j - 1)) 
       { 
          temp = *(Array + j); 
          *(Array + j) = *(Array + j - 1); 
          *(Array + j - 1) = temp; 
          j--; 
       } 
    } 
 }

Sortieren durch direktes Einfügen