8719220778

METODY PROBABILISTYCZNE I STATYSTYKA - INFORMACJE UZUPEŁNIAJĄCE

Przykład 3

Sortowanie przez wybieranie.

Mamy nieposortowany ciąg o n elementach i posortowany o 0 elementach. Szukamy najmniejszego elementu w ciągu nieposortowanym i wstawiamy go na koniec posortowanego ciągu, tyle razy, aż posortowany ciąg będzie miał n elementów, a nieposortowany 0. Taki stan uzyskamy wtedy, gdy wszystkie n elementów z nieposortowanego przerzucimy w posortowany. Musimy zatem n razy wyszukać najmniejszy element w ciągu - a wyszukiwanie najmniejszego elementu, jak wiemy z 1. przykładu, ma złożoność O(n) (liniową). Zatem wykonanie n razy operacji o złożoności n wymaga n*n operacji, czyli ma złożoność kwadratową 0(n*n) = 0(n²).

Najczęściej algorytmy mają złożoność czasową proporcjonalną do funkcji:

•    log(n)- złożoność logarytmiczna

•    n - złożoność liniowa

•    nlog(n) - złożoność liniowo-logarytmiczna

•    n² - złożoność kwadratowa

•    n^k - złożoność wielomianowa

•    2" - złożoność wykładnicza

•    n! - złożoność wykładnicza, ponieważ n!>2ⁿ już od n=4 1.3. Przykładowe wyznaczanie złożoności obliczeniowej ¹

Ocenimy złożoność obliczeniową sortowania przez wstawianie, które polega na pobieraniu kolejnych elementów ciągu i poszukaniu dla niego odpowiedniego miejsca na liście elementów uporządkowanych. Gdy miejsce zostanie znalezione, to elementy listy się rozsuwa i w tak ustalone miejsce „wkłada” ostatnio pobrany element.

Algorytm sortowania przez wstawianie można porównać do sposobu układania kart pobieranych z talii. Najpierw bierzemy pierwszą kartę. Następnie pobieramy kolejne, aż do wyczerpania talii. Każdą pobraną kartę porównujemy z kartami, które już trzymamy w ręce i szukamy dla niej miejsca przed pierwszą kartą starszą (młodszą w przypadku porządku malejącego). Gdy znajdziemy takie miejsce, rozsuwamy karty i nową wstawiamy na przygotowane w ten sposób miejsce (stąd pochodzi nazwa algorytmu - sortowanie przez wstawianie, ang. In-sertion Sort). Jeśli nasza karta jest najstarsza (najmłodsza), to umieszczamy ją na samym końcu. Tak porządkujemy karty. A jak przenieść tę ideę do świata komputerów i zbiorów liczbowych?

Przykład

Ciąg liczb do sortowania: 12,14,11,16,13 Realizacja:

1) 12 14 11 16113 - element ostatni jest początkiem listy uporządkowanej

2)    wybiera się element leżący tuż przed elementem ostatnim (liczba 16 - na miejscu czwartym) i porównuje się z elementem listy (13), element 16 > 13 zatem liczbę 13 przesuwa się na miejsce czwarte, a na zwolnione miejsce piąte wstawia się liczbę 16. Po tym kroku mamy więc 12 14 11 I 13 16

3)    wybiera się następny element (11), i porównuje z elementami listy. Ponieważ 11 < 13 to liczba 11 pozostaje na swoim, trzecim miejscu. Zatem otrzymujemy 12 14 I 11 13 16.

1

http://www.gamedev.p1/files/articles/megatutorial/M B.pdf http://xion.oro.p1/files/texts/mgt/html/M B.html http://pl.wikipedia.org/wiki/Sortowanie przez wstawianie

Data ostatniej aktualizacji: piątek, 29 października 2010