In diesem Artikel möchte ich dir gerne einmal die wohl drei gängigsten Sortieralgorithmen zeigen, ein bisschen erklären und sie miteinander vergleichen. Dabei werde ich vor allem den Quelltext für die verschiedenen Anwendungsbeispiele zeigen, da dieser oft hilfreicher ist als Umschreibungen und Erklärungen ;-).
Inhalt
Meistens sind die Implementierungen in Java mit Arrays ein wenig einfacher als mit Listen, da es sich dabei ja auch um statische anstatt dynamische Datenstrukturen handelt. Die Laufzeiten werde ich dir aber auch noch am Ende zeigen.
Insertion Sort
Beim Insertion Sort (oder auch „Sortieren durch Einfügen“) wird grob gesagt immer das erste Element von einer unsortierten Liste herausgenommen und dann an der passenden Stelle in eine sortierte Liste eingefügt.
Die durchschnittliche Laufzeit ist dabei quadratisch, also O(n²) ist die quadrierte Anzahl der zu sortierenden Elemente.
Array
public int[] insertionSort(int[] a) {
int temp;
for(int i = 0; i < a.length; i++) {
for(int j = a.length - 1; j > 0; j--) {
if(a[j - 1] > a[j]) {
temp = a[j];
a[j] = a[j - 1];
a[j - 1] = temp;
}
}
}
return a;
}
Code-Sprache: Java (java)List
public List<Integer> insertionSort(List<Integer> l) {
List<Integer> sl = new List<Integer>();
while(!l.isEmpty()){
l.toFirst();
sl.toFirst();
int cur = l.getContent();
while(sl.hasAccess() && sl.getContent() < cur) {
sl.next();
}
if(sl.hasAccess()) {
sl.insert(cur);
} else {
sl.append(cur);
}
l.remove();
}
return sl;
}
Code-Sprache: Java (java)Selection Sort
Beim Selection Sort (oder auch „Sortieren durch Auswählen“) wird immer das kleinste Element der unsortierten Liste ausgewählt und dieses dann an die sortierte Liste angehangen.
Die Laufzeit ist dabei im Schnitt ebenfalls quadratisch, also O(n²) ist die quadrierte Anzahl der zu sortierenden Elemente.
Array
public int[] selectionSort(int[] a) {
int temp1, temp2;
for(int i = a.length - 1; i > 0; i--) {
temp1 = 0;
for(int j = 1, j <= i; j++) {
if(a[j] > a[temp1]) {
temp1 = j;
}
}
temp2 = a[temp1];
a[temp1] = a[i];
a[i] = temp2;
}
return a;
}
Code-Sprache: Java (java)List
public List<Integer> selectionSort(List<Integer> l) {
List<Integer> sl = new List<Integer>();
sl.toFirst();
while(!l.isEmpty()){
l.toFirst();
int min = l.getContent();
while(l.hasAccess()) {
if(l.getContent() < min) {
min = l.getContent();
}
l.next();
}
sl.append(min);
while(l.hasAccess()) {
if(l.getContent() == min) {
l.remove();
}
l.next();
}
}
return sl;
}
Code-Sprache: Java (java)Bubble Sort
Beim Bubble Sort (oder auch „Sortieren durch Vertauschen“) wird ein Element immer mit seinem Nachbarelement verglichen und getauscht, wenn es entsprechend größer ist. Das wird so lange wiederholt bis bei einem kompletten Durchlauf der Liste kein Tausch mehr stattgefunden hat.
Die durchschnittliche Laufzeit ist dabei quadratisch, also O(n²) ist die quadrierte Anzahl der zu sortierenden Elemente.
Array
public int[] bubbleSort(int[] a) {
int temp;
for(int i = 1; i < a.length; i++) {
for(int j = 0, j < a.length - i; j++) {
if(a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
return a;
}
Code-Sprache: Java (java)List
public List<Integer> bubbleSort(List<Integer> l) {
int temp1, temp2;
boolean changed = false;
do {
l.toFirst();
temp1 = l.getContent();
l.next();
while(temp1 > l.getContent() && l.hasAccess()) {
temp2 = l.getContent();
l.remove();
l.insert(temp2);
l.insert(temp1);
changed = true;
}
} while(l.hasAccess() && changed == true)
return l;
}
Code-Sprache: Java (java)Ich hoffe, dass ich dir damit ein wenig helfen konnte. Falls du Fehler oder Optimierungspotenzial im Quellcode feststellen solltest, kannst du natürlich gerne einen Kommentar schreiben ;-).
