Adaptivity
Lektion 6 von 11 im Kurs Bubble Sort von Coddy.
Wir haben die Zeitkomplexität für unseren Bubble-Sort-Algorithmus besprochen, die O(n2) beträgt. Aber was ist, wenn unser Array bereits sortiert ist? Dann wird es ebenfalls die Laufzeit von O(n2) beanspruchen.
Was ist Adaptivität?
Ein adaptiver Algorithmus ist ein Algorithmus, der sein Verhalten basierend auf der gegebenen Eingabesequenz ändert.
Ist Bubble Sort also adaptiv?
Ja, wir können unseren Bubble-Sort-Algorithmus adaptiv machen. Wir müssen den Bubble-Sort-Algorithmus mit einer Worst-Case-Laufzeit von O(n2) und einem Best-Case von O(n) schreiben, damit er adaptiv ist. Hier bezieht sich der Best-Case auf den Fall, in dem das Array bereits sortiert ist.
Wir werden eine boolesche Flag-Variable verwenden, um die while-Schleife zu steuern, damit der Algorithmus vorzeitig stoppt, wenn das Array bereits sortiert war.
while(flag)
{
//Code
}
Wir müssen den Durchlauf wiederholen, bis das Array sortiert ist. Wir haben bereits gelernt, wie man die Anzahl der Vertauschungen zählt, also können wir ein Flag implementieren und prüfen, ob im Durchlauf keine Vertauschung erforderlich ist, und dann die Schleife abbrechen.
Aufgabe
MittelErstellen Sie eine Funktion namens ad_bubblesort, die ein Array und die Größe des Arrays erhält. Führen Sie den adaptiven Bubble-Sort-Algorithmus aus. Denken Sie daran, eine Variable namens flag zu verwenden, um auf Vertauschungen zu prüfen.
Probier es selbst
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// Code hier schreiben
*returnSize = n;
return arr;
}
Alle Lektionen in Bubble Sort
1Basics of Bubble Sort
IntroductionWorking of the Bubble SortSwap adjacent elementsBubble Sort Algorithm