Technischer Projektleiter
Comb sort – Kamm-Sortierung in Java
Sortieralgorithmen werden verwendet, um die Elemente eines Arrays oder einer Liste in aufsteigender oder absteigender numerischer oder lexikografischer Reihenfolge neu zu ordnen. Die Sortierung ist sehr wichtig für die optimale Leistung anderer Algorithmen, die sortierte Eingabedaten benötigen. Es gibt eine Reihe von verschiedenen Sortieralgorithmen. Die Auswahl eines geeigneten Algorithmus hängt von Faktoren wie der Größe und den Eigenschaften der Eingabedaten, dem verfügbaren Speicher und den Zeit- und Platzanforderungen ab. Um Ihnen die Auswahl zu erleichtern, werden wir in unserer Serie die bekanntesten Datensortieralgorithmen nacheinander vorstellen, ihre Prinzipien, Vor- und Nachteile erklären und sie in Java programmieren. Heute werden wir uns Comb sort ansehen.
Comb sort Algoritmus
Comb sort ist ein Sortieralgorithmus, der von dem polnischen Informatiker Włodzimierz Dobosiewicz erfunden wurde, um Sortieralgorithmen zu verbessern, die auf der Methode der Elementersetzung basieren. Wenn Du unseren Artikel über Bubble Sort gelesen hast, weißt du bereits, dass sein größtes Manko darin besteht, dass es beim Sortieren von Elementen Szenarien gibt, die sich nicht für den Algorithmus eignen. Zum Beispiel. Kleine Elemente, die sich am Ende des Arrays befinden, sind bei der aufsteigenden Sortierung problematisch und große Elemente, die sich am Anfang des Arrays befinden, sind bei der absteigenden Sortierung problematisch, weil es ziemlich viele Iterationen braucht, bis ein bestimmtes Element während der Sortierung neu positioniert wird. Die Kamm-Sortierung löst dieses Problem, indem sie genau solche problematischen Elemente am Anfang der Sortierung auswählt und sie bevorzugt austauscht.
Comb sort – Funktionsprinzip
Die Grundidee von Comb sort besteht darin, dass kleine Werte am Ende der Liste (sogenannte Schildkröten) schnell eliminiert werden, denn bei der bubble sort wird die Sortierung erheblich verlangsamt, indem eine Lücke (oder ein Grat) verwendet wird, die nach und nach kleiner wird. Große Werte am Anfang der Liste stellen bei der Sortierung nach Blasen und Stegen kein Problem dar. Wenn zwei beliebige Elemente in der Blasensortierung verglichen werden, haben sie immer einen Abstand von 1. Der Grundgedanke hinter von comb sort ist, dass der Abstand viel größer als 1 sein kann und dass er keine feste Konstante sein muss, sondern sich nach Iterationen ändern kann. Die Lücke beginnt mit einem großen Wert, der in der Regel der Länge des sortierten Arrays entspricht, und verringert sich dann um einen bestimmten Faktor (in der Regel um 1,3). Dieser Vorgang wird so lange wiederholt, bis die Lücke den Wert 1 erreicht. Dann verhält sich der Algorithmus wie eine normale Bubble-Sortierung, aber zu diesem Zeitpunkt ist das Array bereits teilweise geordnet, so dass die letzte Iteration effizienter ist. In Experimenten hat sich gezeigt, dass ein zu kleiner Lückenwert den Algorithmus verlangsamt, da er unnötig viele Vergleiche durchführt, während ein zu großer Lückenwert nicht effizient mit Schildkröten umgehen kann, so dass viele Durchläufe mit einer Lücke von 1 erforderlich sind.
Vorteile des Comb sort Algorithmus:
- ist leicht zu verstehen und umzusetzen,
- benötigt keinen zusätzlichen Speicher für die Sortierung,
- löst das Problem der kleinen Werte am Ende der Liste,
- ist im Durchschnitt schneller als Bubble sort.
Der Nachteil des Comb sort Algorithmus:
- Die Zeitkomplexität ist jedoch immer noch O(n²), was ihn zu einem langsamen Algorithmus für einen großen Datensatz macht,
- ist nicht stabil.
Comb sort Zeitbedarf
| Algorithmus | Methode | Zeitliche Komplexität | Speicher | Stabil | ||
| schlechteste | durchschnittlich | beste | ||||
| Comb sort | Austausch | O(n²) | O(n²) | O(n log n) | O(1) | Nein |
Comb sort Animation, Visualisierung, gif
Eine Visualisierung des Comb-Sort-Algorithmus sieht so aus: 
Quelle: commons.wikimedia.org/wiki/Category:Animations_of_sort_algorithms
Eine Animation des Comb sort Algorithmus findest du zum Beispiel auf dieser Seite.
Comb sort Implementierung – Beispiel in Java
Lass uns diesen Algorithmus mit einer dynamischen Lücke in Java programmieren. CombSort.java
package sorting;
public class CombSort {
private boolean change;
private int temp;
private int gap;
public void sort(int data[])
{
change = false;
// gap init
gap = data.length;
int i = 0;
while (gap != 1 || change) {
change = false;
// calculate new gap
gap /= 1.33;
if(gap <= 1)
gap = 1;
System.out.println(++i + ". iteration (gap = " + gap + ")");
for (int j = 0; j + gap < data.length; j++) {
if (data[j] > data[j + gap]) {
temp = data[j];
data[j] = data[j + gap];
data[j + gap] = temp;
change = true;
printArray(data);
}
}
// If no two elements swapped, then end the sort method
if (!change)
return;
}
}
// Function to print an array
public void printArray(int data[])
{
for (int i = 0; i < data.length; i++)
System.out.print(data[i] + " ");
System.out.println();
}
}
Main.java
import sorting.CombSort;
public class Main {
public static void main(String[] args) {
int dataToSort[] = { 6, 5, 4, 2, 3, 1, 7 };
CombSort combSort = new CombSort();
System.out.print("Input: ");
combSort.printArray(dataToSort);
combSort.sort(dataToSort);
System.out.print("Sorted: ");
combSort.printArray(dataToSort);
}
} Die Ausgabe dieses Beispiels ist: 
Wir haben die obigen Beispieldateien in Form von Code vorbereitet, den du direkt in Java ausführen kannst. Comb sort Code in Java herunterladen. Wenn du ein Java Programmierer bist und nach Arbeit suchst, schau dir unsere Mitareiterbenefits an und reagiere auf die neuesten Stellenangebote.
