Site hosted by Angelfire.com: Build your free website today!

Shellsort


Der Grundgedanke ist, den Nachteil von Insertion Sort, dass nur benachbarte Elemente ausgetauscht werden können, zu beseitigen, indem man das Feld so umsortiert, dass man ein sortiertes Feld erhält, wenn man jedes h-te Element entnimmt.
Dies kann man dadurch bewältigen, indem man jede 1 bei Insertion Sort durch h, jede 2 durch h+1 usw. ersetzt. Was man für h einsetzt ist nicht festgeschrieben. Es hat sich jedoch das h der folgenden Implementierung als ziemlich geeignet herausgestellt.

Genaue Zahlen zur Laufzeit kann ich nicht geben, da es noch niemanden gelungen ist, Shellsort vollständig zu analysieren. Durch Versuche hat sich jedoch herausgestellt, dass Shellsort auch bei großen Werten für N nur wenig langsamer ist, als Quicksort. 

void cm_Shellsort(itemType feld[], int N) {
     int i, j, h;
     itemType wert;
     for(h=1; h<=N/9; h=3*h+1) ;
     for( ; h>0; h/=3) {
         for(i=h+1; i<=N; i+=1) {
             wert = feld[i];
             j = i;
             while(j>h && feld[j-h] > wert) {
                 feld[j] = feld[j-h];
                 j -= h;
             }
             feld[j] = wert;
         }
     }
}


   Computer    Programmieren (incl. C++ Kurs)    Algorithmen    Bücher    

Zeitschriften    Heavy Metal    Mountainbiking    Meine Katze    

Über mich und die Site    Links    Downloads    Gästebuch    HP mit Umfrage