Bubble Sort und Insertion Sort
Einfache Sortierverfahren
Bubble Sort und Insertion Sort ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Einfache Sortierverfahren
Bubblesort und Insertionsort sind die beiden einfachsten vergleichsbasierten Sortierverfahren. Beide haben im schlechtesten Fall die Komplexität O(n²), sind aber leicht zu verstehen und für kleine oder nahezu sortierte Arrays nützlich.
So funktioniert Bubblesort
Bubblesort durchläuft das Array wiederholt und vertauscht benachbarte Elemente, die in der falschen Reihenfolge stehen. Nach jedem vollständigen Durchlauf steigt das größte noch nicht sortierte Element an seine endgültige Position am Ende auf.
Zwei Ganzzahlen vertauschen
Eine wiederverwendbare Tausch-Hilfsfunktion hält den Sortiercode übersichtlich.
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a; *a = *b; *b = t;
}
int main(void) {
int x = 1, y = 2;
swap(&x, &y);
printf("%d %d\n", x, y);
return 0;
}Implementierung von Bubblesort
Verschachtelte Schleifen: Die äußere Schleife zählt die Durchläufe, die innere vergleicht benachbarte Paare und vertauscht sie. Nach Durchlauf i sind die letzten i Elemente sortiert.
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
bubble_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Optimierung durch vorzeitiges Beenden
Wenn ein vollständiger Durchlauf keine Vertauschungen durchführt, ist das Array bereits sortiert und Sie können abbrechen. Dadurch hat Bubblesort bei bereits sortierten Eingaben die Laufzeit O(n).
#include <stdio.h>
void bubble_sort(int a[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0;
for (int j = 0; j < n - 1 - i; j++)
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; swapped = 1;
}
if (!swapped) break;
}
}
int main(void) {
int a[] = {1, 2, 3, 4, 5};
bubble_sort(a, 5);
printf("sorted with early exit\n");
return 0;
}So funktioniert Insertionsort
Insertionsort baut am Anfang einen sortierten Bereich auf. Für jedes neue Element verschiebt es größere sortierte Elemente nach rechts und fügt das neue Element an der richtigen Stelle ein – ähnlich wie beim Sortieren von Spielkarten auf der Hand.
Implementierung von Insertionsort
Übernehmen Sie das Element key = a[i], verschieben Sie anschließend jedes größere Element in a[0..i-1] um eine Position nach rechts und fügen Sie key in die entstandene Lücke ein.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i];
int j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
}
int main(void) {
int a[] = {5, 2, 9, 1, 3};
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Insertionsort bei nahezu sortierten Daten
Insertionsort ist besonders leistungsfähig, wenn das Array fast sortiert ist: Jedes Element bewegt sich nur um wenige Positionen, sodass die Laufzeit gegen O(n) geht. Deshalb wird das Verfahren als abschließender Schritt in hybriden Sortierverfahren eingesetzt.
#include <stdio.h>
void insertion_sort(int a[], int n) {
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && a[j] > key) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
}
int main(void) {
int a[] = {1, 2, 4, 3, 5}; /* one out of place */
insertion_sort(a, 5);
for (int i = 0; i < 5; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Stabilität
Beide Sortierverfahren sind stabil: Gleiche Elemente behalten ihre ursprüngliche relative Reihenfolge, weil nur bei einem strikt größeren Vergleich vertauscht oder verschoben wird. Stabilität ist wichtig, wenn Datensätze nach mehreren Schlüsseln sortiert werden.
Komplexitätsvergleich
Beide Verfahren haben im Durchschnitt und im schlechtesten Fall die Komplexität O(n²), unterscheiden sich in der Praxis aber:
- Bubblesort: viele Vertauschungen, wird in echtem Code selten verwendet
- Insertionsort: weniger Schreibvorgänge, hervorragend für kleine oder nahezu sortierte Arrays
Der Best Case beträgt bei beiden mit Optimierungen O(n).
Operationen zählen
Wir zählen die Vergleiche, die Insertionsort bei einem umgekehrt sortierten Array durchführt – dem schlechtesten Fall.
#include <stdio.h>
int main(void) {
int a[] = {5, 4, 3, 2, 1};
int n = 5; long cmp = 0;
for (int i = 1; i < n; i++) {
int key = a[i], j = i - 1;
while (j >= 0 && (cmp++, a[j] > key)) { a[j+1] = a[j]; j--; }
a[j+1] = key;
}
printf("comparisons = %ld\n", cmp);
return 0;
}Kurzer Test
Testen Sie Ihr Verständnis einfacher Sortierverfahren.
Zusammenfassung
Sie haben zwei einfache Sortierverfahren mit der Komplexität O(n²) kennengelernt.
- Bubblesort vertauscht in jedem Durchlauf benachbarte Paare
- Insertionsort verschiebt Elemente und fügt sie in einen sortierten Bereich am Anfang ein
- Beide Verfahren sind stabil; bei sortierten Eingaben erreichen beide mit Optimierung O(n)
- Für kleine Datenmengen ist Insertionsort die praktisch bessere Wahl
Häufig gestellte Fragen
Ist die Lektion „Bubble Sort und Insertion Sort“ kostenlos?
Ja — der vollständige Text von „Bubble Sort und Insertion Sort“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Bubble Sort und Insertion Sort“?
Einfache Sortierverfahren Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um C Academy zu starten?
Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Bubble Sort und Insertion Sort“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?
Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Bubble Sort und Insertion Sort
- Quicksort
- Mergesort
- qsort verwenden