Analiza złożoności
Lekcja 5 z 11 w kursie Sortowanie bąbelkowe w Coddy.
Analiza złożoności sortowania bąbelkowego.
Złożoność czasowa zależy od liczby wykonanych porównań i zamian.
Musimy wykonać n przebiegów, a w każdym przebiegu wykonujemy (n-1) porównań. gdzie n to liczba elementów na liście.
Łączna liczba porównań=(n-1)+(n-1)+(n-1)....n razy
=n*(n-1)
=n2-n
Złożoność czasowa algorytmu sortowania bąbelkowego wynosi O(n2).
Jeśli chodzi o złożoność pamięciową, algorytm nie wykorzystuje dodatkowej pamięci, sortowanie odbywa się w miejscu, a elementy są porządkowane na oryginalnej liście.
Złożoność pamięciowa algorytmu sortowania bąbelkowego wynosi O(1) (stała).
Wyzwanie
ŁatwyUtwórz funkcję o nazwie count_swaps, która przyjmuje tablicę i jej rozmiar. Wykonaj na tablicy algorytm sortowania bąbelkowego i policz, ile razy wykonano zamianę elementów.
Spróbuj swoich sił
#include <stdio.h>
#include <stdlib.h>
int count_swaps(int* arr, int arr_size, int n) {
// Napisz kod tutaj
return 0;
}
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