3 Fragen zu Sortieralgorithmus

Bubblesort ist ein einfacher Sortieralgorithmus, der wiederholt benachbarte Elemente einer Liste vergleicht und vertauscht, wenn sie in der falschen Reihenfolge sind. Dies wird so lange wiederholt, bis die Liste sortiert ist. Hier ist ein einfaches Beispiel: Angenommen, es gibt die Liste: [5, 3, 8, 4, 2] 1. **Erster Durchgang:** - Vergleiche 5 und 3. Da 5 > 3, tausche sie: [3, 5, 8, 4, 2] - Vergleiche 5 und 8. Da 5 < 8, nichts tun: [3, 5, 8, 4, 2] - Vergleiche 8 und 4. Da 8 > 4, tausche sie: [3, 5, 4, 8, 2] - Vergleiche 8 und 2. Da 8 > 2, tausche sie: [3, 5, 4, 2, 8] 2. **Zweiter Durchgang:** - Vergleiche 3 und 5. Da 3 < 5, nichts tun: [3, 5, 4, 2, 8] - Vergleiche 5 und 4. Da 5 > 4, tausche sie: [3, 4, 5, 2, 8] - Vergleiche 5 und 2. Da 5 > 2, tausche sie: [3, 4, 2, 5, 8] - Vergleiche 5 und 8. Da 5 < 8, nichts tun: [3, 4, 2, 5, 8] 3. **Dritter Durchgang:** - Vergleiche 3 und 4. Da 3 < 4, nichts tun: [3, 4, 2, 5, 8] - Vergleiche 4 und 2. Da 4 > 2, tausche sie: [3, 2, 4, 5, 8] - Vergleiche 4 und 5. Da 4 < 5, nichts tun: [3, 2, 4, 5, 8] - Vergleiche 5 und 8. Da 5 < 8, nichts tun: [3, 2, 4, 5, 8] 4. **Vierter Durchgang:** - Vergleiche 3 und 2. Da 3 > 2, tausche sie: [2, 3, 4, 5, 8] - Vergleiche 3 und 4. Da 3 < 4, nichts tun: [2, 3, 4, 5, 8] - Vergleiche 4 und 5. Da 4 < 5, nichts tun: [2, 3, 4, 5, 8] - Vergleiche 5 und 8. Da 5 < 8, nichts tun: [2, 3, 4, 5, 8] Jetzt ist die Liste sortiert: [2, 3, 4, 5, 8] Der Algorithmus hat in jedem Durchgang die größten unsortierten Elemente nach hinten "gebubbelt".

Um die Anzahl der Tauschoperationen zu bestimmen, die erforderlich sind, um die Liste [1, 2, 3, 4, 5, 6, 7, 8] zu sortieren, müssen wir zunächst feststellen, ob die Liste bereits sortiert ist. In diesem Fall ist die Liste bereits in aufsteigender Reihenfolge sortiert. Da die Liste bereits sortiert ist, sind keine Tauschoperationen erforderlich. Die Anzahl der Tauschoperationen ist also 0.

Hier ist ein einfaches C-Programm, das den Insertion Sort Algorithmus implementiert: ```c #include <stdio.h> // Funktion zum Durchführen des Insertion Sort void insertionSort(int arr[], int n) { for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; // Verschiebe Elemente des Arrays, die größer als der Schlüssel sind, // um eine Position nach vorne, um Platz für den Schlüssel zu schaffen while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j = j - 1; } arr[j + 1] = key; } } // zum Ausdrucken des Arrays void printArray(int arr[], int n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n"); } int main() { int arr[] = {12, 11, 13, 5, 6}; int n = sizeof(arr) / sizeof(arr[0]); printf("Unsortiertes Array: \n"); printArray(arr, n); insertionSort(arr, n); printf("Sortiertes Array: \n"); printArray(arr, n); return 0; } ``` Dieses Programm definiert eine `insertionSort`-Funktion, die ein Array von Ganzzahlen sortiert. Die `printArray`-Funktion wird verwendet, um das Array vor und nach dem Sortieren auszugeben. Das `main`-Programm initialisiert ein Beispiel-Array, sortiert es und gibt die Ergebnisse aus.