Algorithmensammlung: Sortierverfahren: Combsort
Aus Wikibooks
Algorithmensammlung: Sortierverfahren
-
- Combsort
- Quicksort
- Heapsort
- Selectionsort
Inhaltsverzeichnis |
[Bearbeiten] Combsort
Combsort ist ein Sortieralgorithmus der relativ schnell arbeitet. Zur Funktionsweise siehe 
Combsort.
[Bearbeiten] Implementierungen
[Bearbeiten] C
Das Integer-Array mit der Länge len wird nach dem Beenden der Funktion aufsteigend sortiert sein.
void Combsort (int *Array, int len) { int h; int luecke = len/2; // Zu Beginn ist die Lücke über den halben Array. _Bool b; for (;;) { b = 0; // b bleibt auf false, wenn kein einziges Mal etwas falsch ist. for (int i = 0; i<len; i++) { if (luecke+i >= len) // Schutz vor Speicherfehlern { break; } if (Array[i] > Array[i+luecke]) // überprüft ob die zwei Elemente falsch herum sind { h = Array[i]; // wenn ja -> vertauschen Array[i] = Array[i+luecke]; Array[i+luecke] = h; b = 1; } } luecke = luecke/1.3; // Lücke verkleinern für nächsten Durchlauf if (luecke < 1) { luecke = 1; } if (b == 0 && luecke == 1) // Aufhören wenn die Lücke bei 1 ist und kein einziges Mal getauscht wurde. { break; } } }
Vergleichswerte: Bei einer Arraygröße von 30000 Zahlen ca. je nach System 4 bis 10 Millisekunden.
[Bearbeiten] Python
def compsort(seq): liste = list(seq) # Service für unveränderliche Sequenzen (z.B. Tuples und Strings) schritt = len(liste) while 1: vertauscht = False if schritt > 1: schritt = int(schritt / 1.3) # Schrittweite ggf. verringern for i in xrange(len(liste) - schritt): if liste[i] > liste[i + schritt]: # wenn Tausch notwendig, ... liste[i],liste[i + schritt] = liste[i + schritt],liste[i] # ... tauschen ... vertauscht = True # ... und merken, dass getauscht wurde # wenn bei Schrittweite 1 nichts mehr getauscht wurde, sind wir fertig # (und auch wenn Schrittweite 0 ist, weil die Liste leer war) if not vertauscht and schritt <= 1: break return liste if __name__ == '__main__': print compsort([]) print compsort((6,8,3,5,9,7,6.2,7,6,2,-1)) print compsort(["Meyer","Kohl","Schmidt","Meyer","Lehmann"]) print compsort("thequickbrownfoxjumpsoverthelazydog")
