Complexity Analysis
Lektion 5 von 11 im Kurs Bubble Sort von Coddy.
Komplexitätsanalyse von Bubble Sort.
Die Zeitkomplexität hängt von der Anzahl der durchgeführten Vergleiche & Vertauschungen ab.
Wir müssen n Durchläufe ausführen und in jedem Durchlauf haben wir (n-1) Vergleiche, wobei n die Anzahl der Elemente in der Liste ist.
Gesamtzahl der Vergleiche=(n-1)+(n-1)+(n-1)....n-mal
=n*(n-1)
=n2-n
Die Zeitkomplexität für den Bubble-Sort-Algorithmus beträgt O(n2).
Wenn wir über die Platzkomplexität sprechen, wird im Algorithmus kein zusätzlicher Speicherplatz verwendet, es wird eine In-place-Sortierung durchgeführt und die Elemente werden in der ursprünglichen Liste selbst angeordnet.
Die Platzkomplexität für den Bubble-Sort-Algorithmus beträgt O(1) (Konstant).
Aufgabe
EinfachErstellen Sie eine Funktion namens count_swaps, die ein Array und die Größe des Arrays erhält. Führen Sie den Bubble-Sort-Algorithmus auf dem Array aus und zählen Sie, wie oft Vertauschungen durchgeführt werden.
Probier es selbst
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Code hier schreiben
return 0;
}
Alle Lektionen in Bubble Sort
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm