Złożoność czasu sortowania bańki
W tym artykule rozważane jest sortowanie rosnące. Ten artykuł ma na celu wskazanie względnej prędkości algorytmu sortowania bańki. Ta względna prędkość jest określana jako złożoność czasu. Kodowanie odbywa się w języku komputerowym C.
Treść artykułu
- Wprowadzenie - patrz wyżej
- Ilustracja sortowania bańki
- Najgorsza wydajność
- Lepsza wydajność do sortowania bańki
- Niektóre przeplatane sekwencja już posortowanych elementów
- Idealny przypadek
- Wniosek
Ilustracja sortowania bańki
Rozważ następującą listę nieprojektowanej:
R x f s u z v jIstnieje 8 elementów, które wymagają 8 kompletnych skanów, w wyniku czego:
R f s u x v j zF r s u v j x z
F r s u j v x z
F r s j u v x z
F r j s u v x z
F J R S u v x z
F J R S u v x z
F J R S u v x z
Ostateczna lista to pełny rodzaj.
Najgorsza wydajność
Kod C do uporządkowania poprzednich ośmiu znaków, wcześniej wyjaśniono:
#włączaćvoid bubbleSort (char arr [], int n)
int licznik = 0;
dla (int i = 0; i < n; i++)
dla (int j = 1; j < n; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
ARR [j - 1] = temp;
licznik+= 1;
printf („%i \ n”, licznik);
Kod wymiany jest w wewnętrznej zagnieżdżonej formie pętli. Licznik liczy liczbę podstawowych operacji. Zewnętrzne pętle na pętle od 0 do 7, i.mi., 8 razy. Wewnętrzne pętle z pętli od 1 do 7, i.mi., 7 razy. Całkowita liczba podstawowych operacji (wewnętrzna podkładka) wynosi 8 x 7 = 56. Wyjście licznika wynosi 56.
Gdyby wewnętrzna zapętlona pętla od 0 do 7, całkowita liczba podstawowych operacji wynosiłaby 8 x 8 = 64. Jest to maksymalna liczba podstawowych operacji dla tego gniazdowania dla pętli. Niech 8 będzie n. Następnie maksymalna liczba takich gniazdowania na pętle wynosi n2.
Najgorsza złożoność czasu dla poprzedniej funkcji jest podana jako,
NA2)
Big O, a następnie jego nawiasy z n2 nazywa się notacją Big-O. Wskazuje względną prędkość kodu. Chociaż w poprzednim kodzie liczba podstawowych operacji wynosi 56, maksymalna możliwa liczba operacji, 82 = 64, jest to, co zostanie podane dla złożoności czasowej.
Odpowiednia główna funkcja C dla poprzedniego kodu to:
int main (int argc, char ** argv)int n = 8;
char arr [] = 'r', „x ',„ f ”,„ s ”,„ u ”,„ z ”,„ v ”,„ j ”;
BubbleSort (arr, n);
dla (int i = 0; i
printf („\ n”);
powrót 0;
Lepsza wydajność do sortowania bańki
Zauważ w poprzedniej ilustracji dla bańki; Po pierwszym skanowaniu najwyższy element jest na prawym końcu. Po drugim skanie najwyższe dwa elementy są na prawym końcu, w kolejności. Po trzecim skanie najwyższe trzy elementy są na prawym końcu, w kolejności i tak dalej. Operacje na tych ekstremalnych elementach w miarę wzrostu można pominąć w kodowaniu. Zwiększyłoby to ogólną prędkość (czas pełnego sortowania). Poniższy zmodyfikowany kod ilustruje to:
void bubbleSort (char arr [], int n)int licznik = 0;
dla (int i = 0; i < n; i++)
dla (int j = 1; j < n-i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
ARR [j - 1] = temp;
licznik+= 1;
printf („%i \ n”, licznik);
Tym razem liczba wyjściowa to 28. Liczba podstawowych operacji wynosi 28, nieco mniej niż połowa 64, czyli 32. Wewnętrzne pętle z pętli od 1 do N - i. W swoim pierwszym skanowaniu mam zero, a n - i = 8.
Teraz,
dziennik2 8 = log2 23
= 3
8 x 3 = 8xlog2 23
= 24
który jest blisko 28. Niech n = 8. Powyższe wyrażenie prawego operandu ostatniego drugiego, staje się n.dziennik2 23, = n.dziennik2 8, ogólnie napisane jako, n log n.
Gdy złożoność czasu znajduje się w pewnym środkowym zakresie, w tym przypadku od 20 do 40, wyraża się ją jako:
O (n log n)
Gdzie n jest liczbą elementów na liście. Tak więc złożoność czasu dla lepszej wydajności sortowania bąbelkowego jest n log n, co oznacza n x log2(N).
Niektóre przeplatane sekwencja już posortowanych elementów
Istnieje osiem skanów na poprzednią ilustrację sortowania bańki. Zauważ, że w szóstym skanie lista została już całkowicie posortowana. Ostatnie dwa rzędy to powtórzenia szóstego rzędu. W przypadku tej konkretnej listy niepohamowanej poprzednie dwa skany nie były konieczne. Dzieje się tak, gdy podana lista nieposortowana ma już posortowane sekwencje przeplatane. Jeśli podana lista jest całkowicie niepotrzebna, ostatni wiersz byłby ostateczną listą posortowaną (nie byłoby to powtórzenie poprzedniego).
Ostatnie rzędy, takie jak dwa ostatnie powyżej, można pominąć w sortowaniu, a więc poprawić wydajność (prędkość). Poniższy kod to ilustruje:
void bubbleSort (char arr [], int n)_Bool zamieniony = 0;
dla (int i = 0; i < n; i++)
zamieniony = 0;
dla (int j = 1; j < n-i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
ARR [j - 1] = temp;
zamieniony = 1;
if (zamieniony == 0)
przerwa;
Idealny przypadek
Idealna wydajność występuje, gdy podana lista jest już całkowicie posortowana. Kod do przetestowania to:
void bubbleSort (char arr [], int n)int licznik = 0;
_Bool zamieniony = 0;
dla (int i = 0; i < n; i++)
zamieniony = 0;
dla (int j = 1; j < n-i; j++)
if (arr [j] < arr[j - 1])
char temp = arr [j];
arr [j] = arr [j - 1];
ARR [j - 1] = temp;
zamieniony = 1;
licznik+= 1;
if (zamieniony == 0)
przerwa;
printf („%i \ n”, licznik);
Wyjście to:
7F J R S u v x z
Aby uzyskać listę wejściową,
F J R S u v x z7 pochodzi z wewnętrznej pętli. Jednak dla złożoności czasowej rozważane jest maksymalnie 8. Złożoność czasu dla doskonałej wydajności wyraża się jako:
NA)
Wniosek
W tym artykule omówiliśmy złożoność czasu sortowania bańki i podkreśliliśmy następujące:
Najgorsze złożoność czasu dla sortowania bąbelkowego jest:
NA2)
Wraz z ulepszeniem kodu staje się złożoność czasu:
O (n log n)
Gdy podana lista jest już całkowicie posortowana, złożoność czasu jest:
NA)