Quellartikel
Der Bubble-Sort-Algorithmus – DEV Community
Maximilian
Einleitung
I recently took a data structures and algorithms course as part of my pursuit to learn lower level programming and computer science concepts. As the saying goes, the best way of solidifying your knowledge in something is to teach it, and since I've already filled my quota for boring my partner with coding talk for the month (probably the year), I thought I'd write a series of posts with some of the things I've learned. This is one such post.
Was ist der Bubble-Sort-Algorithmus
Der Bubble-Sort-Algorithmus wird typischerweise dort eingesetzt, wo Einfachheit gegenüber Effizienz bevorzugt wird. Er hat eine Zeitkomplexität von O(n^2), was bei größeren Listen weniger ideal ist.
Wie funktioniert er
Um zu erklären, wie er funktioniert, hier etwas Pseudocode:
for pointer1 in list
for pointer2 in list
if list[j] > list[j + 1]
swap list[j] and list[j + 1]
pointer2++
pointer1++
Die Idee dieses Algorithmus besteht darin, die größeren Elemente in der Liste nach oben bzw. ans Ende zu „bubbeln“. Wir können uns das mit 2 Zeigern vorstellen, pointer1 und pointer2. Wir beginnen damit, beide Zeiger auf das erste Element in der Liste zu setzen. Dann gehen wir mit pointer2 die gesamte Liste durch und tauschen das Element an der Position von pointer2, wenn das Element an Position pointer2 + 1 einen größeren Wert hat. Wir wiederholen diesen Vorgang so lange, bis wir das Ende der Liste erreichen. Dann erhöhen wir pointer1 um 1 und beginnen den Vorgang erneut mit pointer2.
Dir ist vielleicht aufgefallen, dass wir eine Möglichkeit brauchen, um zu vermeiden, bereits sortierte Elemente zu prüfen. Da das Ziel jeder Iteration darin besteht, die größeren Elemente an das Ende der Liste zu verschieben, können wir dies tun, indem wir die Grenze von pointer2 durch den Wert von pointer1 + 1 begrenzen.
Wie setzen wir ihn um
Hier ist eine stark kommentierte Implementierung in Typescript:
function bubbleSort(arr: number[]): void {
// pointer 1
for (let i = 0; i < arr.length; ++i) {
// pointer 2 + limit iterations by pointer1 + 1
for (let j = 0; j < arr.length - 1 - i; ++j) {
// check if current item is larger than the next item
if (arr[j] > arr[j + 1]) {
// temporarily store the current item so we don't lose it
const tmp = arr[j];
// swap the items in the array
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
Sortiert
Dies ist in den meisten Fällen wahrscheinlich kein Standardalgorithmus, aber ich finde, er ist ein schöner und einfacher Einstieg. Ich hoffe, du fandest ihn nützlich oder zumindest ein wenig interessant!