Adaptacyjność
Lekcja 6 z 11 w kursie Sortowanie bąbelkowe w Coddy.
Omówiliśmy złożoność czasową naszego algorytmu sortowania bąbelkowego, która wynosi O(n2) . Ale co, jeśli nasza tablica jest już posortowana? Wtedy również czas wykonania wyniesie O(n2).
Czym jest adaptacyjność?
Algorytm adaptacyjny to algorytm, który zmienia swoje działanie w zależności od podanej sekwencji wejściowej.
Czy zatem sortowanie bąbelkowe jest adaptacyjne?
Tak, możemy sprawić, że nasz algorytm sortowania bąbelkowego będzie adaptacyjny. Musimy napisać algorytm sortowania bąbelkowego z czasem wykonania w najgorszym przypadku równym O(n2) i w najlepszym przypadku równym O(n), aby był adaptacyjny. Najlepszy przypadek oznacza tutaj sytuację, w której tablica jest już posortowana.
Użyjemy zmiennej flagi typu logicznego do kontrolowania pętli while, aby algorytm zakończył działanie wcześniej, jeśli tablica była już posortowana.
while(flag)
{
//code
}
Musimy powtarzać przebieg, aż tablica zostanie posortowana. Wiemy już, jak zliczać liczbę zamian, więc możemy zaimplementować flagę i sprawdzać, czy podczas przebiegu nie trzeba wykonać żadnej zamiany, a następnie przerwać pętlę.
Wyzwanie
ŚredniUtwórz funkcję o nazwie ad_bubblesort, która przyjmuje tablicę i jej rozmiar. Zastosuj adaptacyjny algorytm sortowania bąbelkowego. Pamiętaj, aby użyć zmiennej o nazwie flag do sprawdzania, czy nastąpiły zamiany.
Spróbuj swoich sił
#include <stdio.h>
#include <stdlib.h>
int* ad_bubblesort(int* arr, int arr_size, int n, int* returnSize) {
// Wpisz tutaj kod
*returnSize = n;
return arr;
}
Wszystkie lekcje w sekcji Sortowanie bąbelkowe
1Podstawy sortowania bąbelkowego
WprowadzenieJak działa sortowanie bąbelkoweZamiana sąsiednich elementówAlgorytm sortowania bąbelkowegoPoćwicz samodzielnie: Kompilator C online