ALGORYTMY SORTOWANIA
Bąbelkowe
Zasada działania:
można zaimplementować jako dwie zagnieżdżone pętle typu for, z których każda wykonuje się O(n) razy. Zadaniem tych pętli jest umieszczenie każdego z elementów na właściwej pozycji.
Złożoność obliczeniowa:
Złożoność obliczeniowa sortowania bąbelkowego jest zawsze O(n2) _ każda z pętli wykona się zawsze O(n) razy, chociaż np. w sytuacji wstępnego posortowania danych wejściowych liczbę obiegów pętli wewnętrznej można by zmniejszyć
Przez wstawianie
Zasada działania:
wewnętrzna pętla _szuka_ właściwej pozycji dla bieżącego elementu, ale tylko wśród elementów wcześniej posortowanych:
Złożoność obliczeniowa:
Liczba iteracji pętli wewnętrznej za pierwszym razem (tj. przy pierwszej iteracji pętli zewnętrznej) wynosi maksymalnie 1, za drugim razem _ 2, potem 3, itd. Najwięcej razy wykona się w ostatniej ( (n − 1)-szej) iteracji pętli zewnętrznej _ n − 1 razy.
Zatem, aby wyznaczyć złożoność obliczeniową całej procedury sortowania przez wstawianie, wystarczy policzyć sumę następującego ciągu:
Charakterystyczne cechy:
gdy liczby są już posortowane w algorytmie sortowania przez wstawianie pętla wewnętrzna nie wykona się ani razu w każdej z n−1 iteracji pętli zewnętrznej. Zatem czas działania algorytmu ograniczy się do O(n).
Przez kopcowanie
Zasada działania:
1. Umieść wszystkie dane wejściowe w kopcu. Utwórz pustą tablicę wyjściową o długości n.
2. Pobierz element z korzenia na pierwszą wolną pozycję w tablicy wyjściowej.
3. Umieść w korzeniu (w miejsce pobranego elementu) ostatni element z kopca (rozmiar kopca zmniejsza się o 1). Przywróć właściwość kopca (analogicznie, jak w procedurze usuwania elementu z kopca).
4. Jeśli kopiec nie jest pusty to skocz do Kroku 2; w przeciwnym wypadku STOP _ posortowane dane są w tablicy wyjściowej .
Złożoność obliczeniowa:
w algorytmie kroki 2-4 są powtarzane n razy (w każdej iteracji, kopiec _ początkowo n elementowy _ zmniejsza się o 1). Zatem złożoność całej procedury można wyliczyć jako:
ZłożonośćKroku 1 + n· Złożoność Kroków 2-4.
Złożoność Kroku 1: Utworzenie kopca z n losowych danych to, jak już wspomniano, n-krotne wykonanie operacji wstawienia elementu do kopca. Wychodząc z założenia, że wstawienie elementu do kopca n elementowego zajmuje O(log n) czasu (tyle, ile wynosi wysokość kopca), złożoność Kroku 1 można oszacować jako O(n log n). Oczywiście 2-ga część Kroku 1 _ utworzenie tabl. wyjśc. _ zajmuje O(1). W metodzie tej zakładamy, że od początku kopiec jest wypełniony losowymi danymi. Rozpoczynając od elementu bn/2c przechodzimy przez kolejne elementy aż do pierwszego i za każdym razem wykonujemy operację naprawy części kopca leżącego poniżej (tj. poddrzewa, dla którego bieżący element jest korzeniem), na podobnej zasadzie jak naprawa kopca pousunięciu elementu. W takiej sytuacji można wykazać, że w kopcu jest najwyżej dn/2k+1e element ów mających poniżej siebie k poziomów. Dla każdego takiego elementu operacja naprawy części kopca leżącego poniżej zajmuje O(k) czasu.
(…)
… można też wykonać szybciej w sposób
wstępujący.
Quicksort
Zasada działania:
Kluczowym elementem algorytmu jest procedura Partition. Procedura ta ma za zadanie taki podział obszaru tablicy B od indeksu p do indeksu q, aby przed elementem q znalazły się elementy nie większe od q-tego, a po tym elemencie _ nie mniejsze. Aby posortować całą tablicę B, należy wywołać quicksort(B,1,n). Zatem cała tablica dzielona…
…).
Złożoność obliczeniowa:
Złożoność obliczeniowa procedury Partition wynosi O(n).
złożoność całego algorytmu Zależy to ściśle od dokonywanych podziałów. Jeśli za każdym razem wybierany jest do podziału taki element, który dzieli dany obszar na 2 równe części, to uzyskamy złożoność O(n log n). jeśli do podziału wybierany jest zawsze taki element, że jedna część dzielonego obszaru zawiera 1 element…
…, ile wartości 2, itd. Tablicę wyjściową wypełniamy więc tak, że do pierwszych C[m] komórek wpisujemy, do następnych C[m − 1] komórek _ m − 1, itd., a do ostatnich C[1] komórek wpisujemy wartość 1.
Złożoność obliczeniowa:
Złożoność obliczeniowa algorytmu wynosi O(n +m):
• każdą daną wejściową analizujemy 1 raz,
• za każdym razem inkrementacja wybranej komórki tablicy C zajmuje O(1),
• na koniec wypełnienie…
... zobacz całą notatkę
Komentarze użytkowników (0)