8719220770

METODY PROBABILISTYCZNE I STATYSTYKA - INFORMACJE UZUPEŁNIAJĄCE

Element d[i] zapamiętujemy w zmiennej piwot, a do d[i\ zapisujemy ostatni element partycji. Dzięki tej operacji piwot został usunięty ze zbioru.

Ustawiamy zmienną; na początek partycji. Zmienna ta zapamiętuje pozycję podziału partycji. W pętli sterowanej zmienną i przeglądamy kolejne elementy od pierwszego do przedostatniego (ostatni został umieszczony na pozycji piwotu, a piwot zapamiętany). Jeśli i-ty element jest mniejszy od piwotu, to trafia on na początek partycji - wymieniamy ze sobą elementy na pozycjach /-tej iy-tej. Po tej operacji przesuwamy punkt podziałowy partycji ;.

Po zakończeniu pętli element z pozycji ;-tej przenosimy na koniec partycji, aby zwolnić miejsce dla piwotu, po czym wstawiamy tam piwot. Zmienna ;' wskazuje zatem wynikową pozycję piwotu. Pierwotna partycja została podzielona na dwie partycje:

• partycja lewa od pozycji lewy do; -1 zawiera elementy mniejsze od pikotu

• partycja prawa od pozycji; + 1 do pozycji prawy zawiera elementy większe lub równe piwotowi.

Sprawdzamy, czy partycje te obejmują więcej niż jeden element. Jeśli tak, to wywołujemy rekurencyjnie algorytm sortowania szybkiego przekazując mu granice wyznaczonych partycji. Po powrocie z wywołań rekurencyjnych partycja wyjściowa jest posortowana rosnąco. Kończymy algorytm.

Dla algorytmu sortowania szybkiego:

1. Wyznaczyć optymistyczną, pesymistyczną i średnią złożoność obliczeniową.

2. Wyznaczyć liczbę wykonywanych iteracji dla powyższych przypadków.

3. Obliczyć wartości powyższych wskaźników dla n = 10.

4. Porównać obliczone wartości z wynikami symulacji¹² liczby porównań w której dla n = 10 niezależnie od posortowania danych otrzymano taką samą liczbę porównań, równą 45. Natomiast dla danych losowych otrzymano: 23, 30, 23, 22, 21, 21, 28, 21, 27, 24.

5. Dla otrzymanych wyników symulacji ocenić korelację pomiędzy liczbą porównań - L i liczbą sortowanych, przypadkowo ustawionych danych - N:

L	24	29	41	46	62	67	85	100	120	136
N	10	12	14	16	18	20	22	24	26	28

Zadanie 3

Otrzymano wyniki dot. liczby iteracji w procesie obliczeniowym realizowanym według dwóch algorytmów. Zweryfikować hipotezę o takiej samej wydajności obliczeniowej tych algorytmów.

Zadanie 4

Otrzymano wyniki dot. czasu trwania obliczeń tym samym programem na dwóch typach komputerów. Zweryfikować hipotezę o takiej samej wydajności czasowej tych komputerów. Zadanie 5

Otrzymano wyniki dot. czasu trwania obliczeń na tym samym komputerze dwoma programami napisanymi według tego samego algorytmu. Zweryfikować hipotezę o takiej samej wydajności obliczeniowej tych programów.

Zadanie 6

Otrzymano wyniki dot. czasu trwania obliczeń na tym samym komputerze dwoma programami napisanymi według dwóch różnych algorytmów. Zweryfikować hipotezę o takiej samej wydajności obliczeniowej par (algorytm, program).

¹² http://www.home.umk.p1/~abak/wdimat/s/OuickSorl.htrnl

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