Strona główna

Sortowania szybkiego jest bardzo wydajny: jego średnia


Pobieranie 30.7 Kb.
Data19.06.2016
Rozmiar30.7 Kb.
Zad.3

Omów dokładnie algorytm sortowania szybkiego – quicksort (również: możliwości wyboru elementu dzielącego i jego wpływ na złożoność algorytmu oraz możliwe implementacje). Podaj jego wady i zalety.


Opis:

Algorytm działa rekursywnie - wybieramy pewien element tablicy, tzw. element osiowy, po czym na początek tablicy przenosimy wszystkie elementy mniejsze od niego, na koniec wszystkie większe, a w powstałe między tymi obszarami puste miejsce trafia wybrany element. Potem sortujemy osobno początkową i końcową część tablicy. Rekursja kończy się, gdy kolejny fragment uzyskany z podziału zawiera pojedynczy element, jako że jednoelementowa podtablica nie wymaga oczywiście sortowania.



Złozonosc algorytmu Quicksort

Zarówno czas działania algorytmu sortowania szybkiego jak równiez

zapotrzebowanie na pamiec sa uzaleznione od postaci tablicy

wejsciowej. Od tego zalezy, czy podziały dokonywane w algorytmie

sa zrównowazone, czy tez nie, a to z kolei zalezy od wybranego klucza

podziału. W przypadku, gdy podziały sa zrównowazone, algorytm

jest równie szybki jak np. sortowanie przez scalanie. Gdy natomiast

podziały sa niezrównowazone, sortowanie moze przebiegac asymptotycznie

tak wolno, jak sortowanie przez wstawianie.

Algorytm sortowania szybkiego jest bardzo wydajny: jego średnia złożoność obliczeniowa jest rzędu . Algorytm ten dość dobrze działa w praktyce, ale ma bardzo złą pesymistyczną złożoność.



Możliwości wyboru elementu:

Najprostsza, "naiwna" metoda podziału – wybieranie zawsze skrajnego elementu tablicy – dla danych już uporządkowanych daje katastrofalną złożoność O(n2). Trywialne na pozór zadanie posortowania posortowanej tablicy okazuje się dla tak zapisanego algorytmu zadaniem skrajnie trudnym. Aby uchronić się przed takim przypadkiem stosuje się najczęściej randomizację wyboru albo wybór "środkowy z trzech". Pierwszy sposób opiera się na losowaniu elementu osiowego, co sprowadza prawdopodobieństwo zajścia najgorszego przypadku do wartości zaniedbywalnie małych. Drugi sposób polega na wstępnym wyborze trzech elementów z rozpatrywanego fragmentu tablicy, i użyciu jako elementu osiowego tego z trzech, którego wartość leży pomiędzy wartościami pozostałych dwu. Można również uzupełnić algorytm o poszukiwanie przybliżonej mediany.



Implementacje:

Pascal


Kod szybkiego sortowania tablicy w Pascalu (z randomizowanym wyborem elementu dzielącego, lecz bez pozostałych usprawnień).

PROCEDURE Quicksort (VAR A : tab; l,r: INTEGER);

VAR

pivot,b,i,j : INTEGER;



BEGIN

IF l < r THEN

BEGIN

pivot := A[random(r-l) + l+1]; { losowanie elementu dzielącego }



i := l-1;

j := r+1;

REPEAT

REPEAT i := i+1 UNTIL pivot <= A[i];



REPEAT j := j-1 UNTIL pivot >= A[j];

b:=A[i]; A[i]:=A[j]; A[j]:=b

UNTIL i >= j;

A[j]:=A[i]; A[i]:=b;

Quicksort(A,l,i-1);

Quicksort(A,i,r)

END

END;


C++


Implementacja w języku C++ przy założeniu, że elementem osiowym jest skrajny element tablicy.

#include // std::swap (funkcja zamieniająca dwie wartości między sobą)

void qsort(int tab[],int lewy,int prawy)

{

if(lewy



{

int m=lewy;

for(int i=lewy+1;i<=prawy;i++)

if(tab[i]

std::swap(tab[++m],tab[i]);

std::swap(tab[lewy],tab[m]);

qsort(tab,lewy,m-1);

qsort(tab,m+1,prawy);

}

}

Zalety:



• działa w miejscu, czyli ”in situ” (uzywa tylko niewielkiego stosu

pomocniczego)

• do posortowania n elementów wymaga srednio czasu proporcjonalnego

do n* logn

• ma wyjatkowo skromna petle wewnetrza

Wady:

jest niestabilny

• zabiera okolo n^2 operacji w najgorszym przypadku

• jest wrazliwy (prosty niezauwazony blad w implementacji moze

powodowac niewlasciwe działanie w przypadku niektórych danych)

Zad. 2


Omów algorytmy usuwania kolizji dla tablic rozproszonych z i bez obszaru nadmiarowego.
Algorytmy rozwiązywania konfliktów bez obszaru nadmiarowego:

Metody liniowe,

Metody kwadratowe;

* Wariant prymitywny,

* Metoda Radkego,

* Metoda Daya,

Metody sześcienne,

Metody losowe,

Metody mieszane.

Metody liniowe:

a (i)= (a(O)+b*i) mod p, gdzie;

a (0) – adres początkowy wyznaczony przez algorytm mieszający,

i – numer próby usunięcia kolizji,

bwspółczynnik

całkowity,

p – długość tablicy.

Wyznacznik b: wszystko jedno, jaki a więc najprościej 1 lub 1.

Wzór redukuje

się zatem do;

a (i) = (a(0)+i) mod p albo a (i) = (a(0) i)

mod p


Zalety:

prostota algorytmu brak skoków na długie dystanse, nie narzuca

długości tablicy.

Wady:


skłonność do tworzenia skupień pierwszego rzędu (modyfikacja; b jako

zmienna, double hashing – czyli b jest inną funkcją mieszającą).

Zalecane:

uważać, aby współczynnik zapełnienia nie przekraczał ok. 80%.



Metody kwadratowe:

Wariant


prymitywny a (i) = (a(0)+b*i+c+i2) mod p , gdzie; b, c –

współczynniki rzeczywiste.

Współczynnik b: wszystko jedno, jaki więc najprościej 0,

Współczynnik c: wszystko jedno, jaki byle nie 0, więc najprościej 1 lub 1.

Wzór

upraszcza się, więc do postaci: a (i)=(a(0)+i2) mod p albo a (i)=(a(0)i2)



mod p

Wady dyskwalifikujące: powtórne badanie działek już przebadanych, pomijanie

niektórych działek, skupiska drugiego rzędu.

Metoda Radkego

Warunek: długość tablicy musi być „liczbą Radkego” tj. liczbą pierwszą

wyrażającą się wzorem 4*i+3 gdzie, i jest dowolną liczbą naturalną.

Algorytm:

a(1)=(a(0)+12) mod p

a(2)=(a(0)12)

mod p

a(3)=(a(0)+22) mod p



a(4)=(a(0)22)

mod p itd.

Uwaga: niech algorytm robi tylko p1

kroków, bo potem powtórne badania będą

musiały

nastąpić.,



Zalety: niezawodność,

Wady: wymuszenie dotyczące długości tablicy, konieczność obliczania (albo

przechowywania i odszukiwania) kwadratów kolejnych

liczb naturalnych, powstawanie skupień drugiego

rzędu.

Metoda Daya (metoda Radkego ulepszona)Metoda opiera się na spostrzeżeniu,

że ciąg liczb kwadratowych (tzn. ciąg kwadratów kolejnych liczb naturalnych) 02 12

22 32 42 itd. Czyli 0, 1, 4, ,9, 16 itd. Daje po zróżnicowaniu ciąg 1, 3, 5, 7, itd. czyli

ciąg kolejnych liczb nieparzystych. Powstaje stąd pomysł, aby kolejne liczby

kwadratowe obliczać nie przez podnoszenie do kwadratu ale przez tworzenie i

sumowanie ciągu kolejnych liczb nieparzystych.

Uwaga: metoda Daya jest modyfikacją metody Radkego.

Metody sześcienne:

Metody te są prawdopodobnie lepsze jeżeli chodzi o ilość skupień ale wymagają

większego nakładu obliczeń. d(i)=(d(0)+i3) mod p; d(i)=(d(0)+(i2 mod p)*i) mod p

Skracanie czasu obliczeń może powstać przy obliczeniu sześcianu metodą reszt

sześciennych.

Metoda losowa.

Metody mieszane

Algorytmy

rozwiązywania konfliktów z obszarem nadmiarowym:

* Z dodatkową tablicą,

* Z listą synonimów (tworzymy dodatkowe pole w rekordzie, aby utworzyć listę).

Zad. 1


Przedstaw podobieństwa i różnice między drzewem BST i RST (podaj przykłady obu drzew – narysuj – dla takich samych kluczy).


Drzewo BST

Drzewo RST

Różnice:

Drzewo BST to binarne drzewo poszukiwań podczas gdy drzewo RST to pozycyjne drzewo poszukiwań. Różni się to tym że:

Drzewo pozycyjne to drzewo przeznaczone do

przechowywania i odszukiwania rekordów, identyfikowanych

przez klucze całkowite, podzielone na zhierarchizowane

klucze częściowe (np. klucz tekstowy podzielony na ciąg kluczy częściowych znakowych).

Można stosować alfabet inny niż dwuliterowy !!!!!!!

Drzewo binarne natomiast to:



Drzewo binarne w teorii grafów to drzewo, w którym stopień każdego wierzchołka jest nie większy od 3.

Wyszukiwanie następuje na podstawie kolejnych bitów słowa, a nie na podstawie wartości elementów jak w BST.



Podobieństwa:

1. Porównywanie całości klucza w każdym węźle (alternatywa do BST).


Przykłady:






©snauka.pl 2016
wyślij wiadomość