Bubblesort (bubble sort) in C und C++
In dieser Lektion implementierst du Bubblesort, indem du immer wieder benachbarte Elementpaare vertauschst, die in falscher Reihenfolge stehen.
Einführung
Bubblesort durchläuft das Array mehrmals, vergleicht jedes Paar benachbarter Elemente und vertauscht sie, wenn sie in falscher Reihenfolge stehen. Nach jedem Durchlauf wandert der größte noch unsortierte Wert ans Ende des Arrays.
Wichtige Punkte
- Teste mit leeren Eingaben, einem einzigen Element, doppelten Werten und bereits sortierten Daten.
- Zuerst richtig machen, dann optimieren.
- Bevorzuge in echtem Code die fertigen Funktionen der Standardbibliothek.
Bubblesort (bubble sort) in C und C++ visualisieren
O(n)Mit Start oder Schritt kannst du jeden Vergleich und jede Datenbewegung verfolgen.
Codebeispiele in C und C++
#include <stdio.h>
int main(void) {
int values[] = {5, 1, 4, 2};
for (int end = 3; end > 0; --end) {
int changed = 0;
for (int index = 0; index < end; ++index) {
if (values[index] > values[index + 1]) {
int temporary = values[index];
values[index] = values[index + 1];
values[index + 1] = temporary;
changed = 1;
}
}
if (!changed) break;
}
for (int index = 0; index < 4; ++index) {
printf("%d ", values[index]);
}
}
1 2 4 5#include <iostream>
#include <vector>
int main() {
std::vector values{5, 1, 4, 2};
for (auto end = values.end(); end != values.begin(); --end) {
bool changed = false;
for (auto item = values.begin(); item + 1 != end; ++item) {
if (*item > *(item + 1)) {
std::iter_swap(item, item + 1);
changed = true;
}
}
if (!changed) break;
}
for (int value : values) {
std::cout << value << ' ';
}
}
1 2 4 5C und C++ im Vergleich
Die Variable changed merkt sich, ob es in einem Durchlauf eine Vertauschung gab. Gab es keine, ist das Array bereits sortiert und die Schleife endet vorzeitig, deshalb braucht ein schon sortiertes Array nur O(n). Im schlechtesten Fall braucht der Algorithmus O(n²) und dient deshalb vor allem zum Lernen. In der Praxis verwendet C++-Code meist std::sort.
Schleifen, Zeiger, Längen und Zwischenpuffer werden ausdrücklich ausgeschrieben.
Iteratoren und Standardalgorithmen trennen die Verarbeitung von der Art, wie die Daten gespeichert sind.
Übungen zur Vertiefung
Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.
- Spiele jeden Vergleich auf Papier durch.
- Teste mit doppelten Werten und mit sehr großen und sehr kleinen Werten.
- Miss die Laufzeit deines Codes und vergleiche sie mit der Standardbibliothek.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
Alle Challenges