Algorithmensammlung: Sortierverfahren: Combsort

Combsort

Combsort ist ein Sortieralgorithmus der relativ schnell arbeitet. Zur Funktionsweise siehe Combsort.

Implementierungen

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.

Java

public static <T extends Comparable<T>> List<T> Combsort(List<T> liste) {
	List<T> liste2 = new ArrayList<T>(liste.size());				// kopieren der Liste
	for (T element : liste) {
		liste2.add(element);
	}
	
	int schritt = liste2.size();
	boolean vertauscht = false;
	do {
		vertauscht = false;
		if (schritt > 1) {
			schritt = (int) (schritt / 1.3);				// Schrittweite ggf. verringern
		}
		for (int i = 0; i < liste2.size() - schritt; i++) {
			if (liste2.get(i).compareTo(liste2.get(i + schritt)) > 0) {	// wenn Tausch notwendig, ...
				T tmp = liste2.get(i);					// ... tauschen ...
				liste2.set(i, liste2.get(i + schritt));
				liste2.set(i + schritt, tmp);
				vertauscht = true;					// ... und merken, dass getauscht wurde
			}
		}
	} while (vertauscht || schritt > 1);
	return liste2;
}

Bei dieser Implementierung handelt es sich um eine generische Implementierung, bei der keine primitiven Datentypen verwendet werden können.

Python

Python 2

def combsort(seq):
    liste = list(seq)  # Service fuer unveraenderliche Sequenzen (z.B. Tuples und Strings)
    schritt = len(liste)
    
    while True:
        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__': # Tests
    print combsort([])
    print combsort((6,8,3,5,9,7,6.2,7,6,2,-1))
    print combsort(["Meyer","Kohl","Schmidt","Meyer","Lehmann"])
    print combsort("thequickbrownfoxjumpsoverthelazydog")

Python 3

def combsort(seq):
    liste = list(seq)  # Service fuer unveraenderliche Sequenzen (z.B. Tuples und Strings)
    schritt = len(liste)
    
    while True:
        vertauscht = False
        if schritt > 1: schritt = int(schritt / 1.3)                      # Schrittweite ggf. verringern
        for i in range(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__': # Tests
    print(combsort([]))
    print(combsort((6,8,3,5,9,7,6.2,7,6,2,-1)))
    print(combsort(["Meyer","Kohl","Schmidt","Meyer","Lehmann"]))
    print(combsort("thequickbrownfoxjumpsoverthelazydog"))