nw asd w6

background image















































Sortowanie „szybkie”

Quick_Sort

Tony Hoare (1960)

Algorytm sortowania

QuickSort

Cechy algorytmu:



Przeciętna złożoność obliczeniowa O(nlgn),



Pesymistyczna złożoność O(n

2

),



Sortowanie „w miejscu”,



Niestabilny,



Zastosowanie techniki „dziel i zwyciężaj”,



Algorytm rekurencyjny.



Rozproszone sortowanie,



Wpływ danych wejściowych na złożonoość obliczeniową,



Łatwa implementacja,



Sprawdza się w sortowaniu średnich i dużych zbiorów danych.

ASD

LJ

S

background image















































Algorytm sortowania

QuickSort

Podstawowy etap algorytmu:

1.

Wybór elementu osiowego (dzielącego) (

pivotpoint

) v=A[q],

2.

Pogrupowanie elementów tablicy A[lewy.. prawy] w sposób następujący:



żaden z elementów A[lewy], ..., A[q-1] „nie większy” niż v,



żaden z elementów A[q+1], ..., A[prawy] „nie mniejszy” niż v,

ASD

LJ

S

Warianty schematu algorytmu:



Rekurencyjny, nierekurencyjny



Wybór elementu osiowego:



pierwszy, środkowy lub ostatni,



losowy,



mediana z 3.

Algorytm

QuickSort

Zakładając, że wybierany jest element osiowy jako pierwszy element tablicy tj.

v=A[lewy] otrzymujemy podział:

v

lewy

prawy

i

j

elementy ≤ v

elementy ≥ v

v

lewy

prawy

prawy

lewy

Dzielenia tablicy dokonuje procedura podziału (

partition

).

ASD

LJ

S

background image















































Algorytm sortowania

QuickSort

Działanie procedury podziału (element osiowy A[lewy]):

1.

Wybór elementu osiowego np. v=A[lewy] dzielącego tablicę A[lewy..prawy],

2.

Przeglądanie A[lewy+1],;,A[prawy] od strony lewej, dopóki nie zostanie

znaleziony element „większy równy” od v,

3.

Przeglądanie A[lewy+1],;,A[prawy] od strony prawej, dopóki nie zostanie
znaleziony element „mniejszy równy” od v,

4.

Dwa elementy, na których się zatrzymują się indeksy, wymieniane są
miejscami. Przeszukiwanie kontynuuowane jest od lewej a później od prawej,

5.

Kiedy indeksy się spotkają proces podziału kończy się,

6.

Element osiowy v zamieniany jest z ostatnim elementem lewej części tablicy.

ASD

LJ

S

Algorytm sortowania

QuickSort

Mechanizm sortowania:

3

7

4

8

5

2

9

i

6

j

3

2

4

5

7

9

8

6

3 2

9

8

7

5

4

4

3

2

2

3

wartownik

ASD

LJ

S

background image















































Algorytm sortowania

QuickSort

Partition(A,lewy,prawy)

{//użycie wartownika A[prawy+1]=

+∞ ;

v=A[lewy];
i=lewy;
j=prawy+1;
DO{

DO i=i+1; WHILE (A[i]<v);
DO j=j-1; WHILE (A[j]>v);
IF (i<j) swap(A[i],A[j]);

} WHILE(i<j)
A[lewy]=A[j];
A[j]=v;
return(j);

}

QuickSort(A,lewy,prawy)
{

q=Partition (A,lewy,prawy);
IF(q-1>lewy)QuickSort(A,lewy,q-1);
IF(q+1<prawy)QuickSort(A,q+1,prawy);

}

ASD

LJ

S

Mechanizm sortowania:

Algorytm sortowania

QuickSort

QuickSort(A,lewy,prawy)
{

q=Partition (A,lewy,prawy);
IF(q-1>lewy)QuickSort(A,lewy,q-1);
IF(q+1<prawy)QuickSort(A,q+1,prawy);

}

ASD

LJ

S

Partition(A,lewy,prawy)
{

v=A[prawy];
i=lewy-1;
FOR (j=lewy; j≤prawy-1; j=j+1)

IF (A[j]≤v){

i=i+1;
swap(A[i],A[j]);

}

swap(A[i+1],A[prawy]);
return(i+1);

}

background image















































Złożoność algorytmu

QuickSort

Złożoność obliczeniowa algorytmu zależy od zrównoważenia podziałów tablicy:



Podział niezrównoważony



Podział zrównoważony

Podział niezrównoważony (przypadek najgorszy) - żaden element nie zostaje

umieszczony po lewej stronie elementu osiowego przez procedurę podziału.

Podział zrównoważony (przypadek najlepszy) - gdy element osiowy dzieli tablicę

na dwie równe części.

ASD

LJ

S

Złożoność algorytmu

QuickSort

Pesymistyczna złożoność (podział niezrównoważony).

Podział niezrównoważony - gdy procedura Partition tworzy dwie podtablice:



1-elementową



(n-1) elementową

Po prawej stronie, elementu osiowego otrzymujemy tablicę pomniejszoną tylko o

jeden element.

Zakładamy, że podziały niezrównoważone będą wykonywane w każdym kroku

algorytmu.

ASD

LJ

S

background image















































Złożoność algorytmu

Sortowanie tablicy
n -elementowej

Podział tablicy

T(n) = T(1) + T(n-1) + T

part

(n)

Sortowanie
tablicy (n-1)-elementowej

Sortowanie tablicy
1-elementowej
T(1)=0

Złożoność pesymistyczna

:

ASD

LJ

S

Złożoność procedury Partition.

Rozmiar danych wejściowych n=prawy–lewy +1

T

part

(n) = n-1 = Θ(n)

Złożoność algorytmu

Złożoność czasowa procedury Partition.

T(n) = T(n-1) + Θ(n) = T(1) + ∑

n-1

k=1

Θ(k) =

Θ

(1) + ∑

n -1

k=1

Θ(k) = Θ(∑

n-1

k=1

k) = Θ(n

2

)

0

n = 1

T(n-1) + (n-1)

n > 1

T(n) =

Rozmiar danych wejściowych n=prawy–lewy +1

T

part

(n) = n-1 = Θ(n)

Pesymistyczna złożoność sortowania (podział niezrównoważony).

Θ(1)

n = 1

T(n-1) + Θ(n)

n > 1

T(n) =

ASD

LJ

S

background image















































Podział niezrównoważony

Drzewo rekurencji:

1

n-2

1

n-1

1

2

1

n

1

(n-1)

(

n-2

)

(

n-3

)

1

T(n) = 1+ 2+ ... +(n-1) = n(n-1)/2 = Θ(n

2

)

Θ(n

2

)

ASD

LJ

S

Podział zrównoważony

Zrównoważone drzewo podziału:

T(n) = lgn Θ(n) = Θ(n lgn)

n

n/2

n/2

n/4

n/4

n/4

n/4

1

1

1

1

1

1 1

11

1

1 1

1

1

1

lgn
podziałów

Θ(n)

Θ(n)

Θ(n)

Θ(1)

n = 1

2T(n/2) + Θ(n)

n > 1

T(n) =

Rozwiązaniem równania jest T(n) = Θ(n lgn)

ASD

LJ

S

background image















































Złożoność algorytmu

QuickSort

0

dla n = 1

T(n) =

2 T(n/2) + (n – 1)

dla n > 1

T(n) = 2

k

T(n/2

k

) + 2

k-1

(n/2

k-1

-1) + 2

k-2

(n/2

k-2

-1) + ... + 2

1

(n/2 -1) + 2

0

(n -1) =

= (n - 2

k-1

) + (n - 2

k-2

) + ...+ (n - 2

-1

) + (n -1) =

= k n – (1+2+...+2

k-1

) = kn – ((2

k

-1) / (2-1)) = kn – (2

k

– 1) =

= nlgn – (n-1)

T(n) = O(nlgn)

Złożoność algorytmu (podział zrównoważony).

ASD

LJ

S

Złożoność algorytmu

QuickSort

Poprawność rozwiązania:

T(n) = nlgn – n+1

T(2n) = 2n lg(2n) - 2n + 1 = 2n(lg2 + lgn) – 2n + 1 =

= 2nlgn + 1 = 2(nlgn – n +1)+ 2n -2 +1 =

= 2T(n) + 2n -1

T(2n) = 2T(n) + 2n - 1

T(n) = Θ(n lgn)

ASD

LJ

S

background image















































Złożoność algorytmu QuickSort

Przeciętna złożoność obliczeniowa algorytmu.

partition

procedury

realizacji

czas

j

n

T

j

T

n

n

n

T

ave

ave

n

j

ave

+

+

=

=

))

(

)

1

(

(

1

)

1

(

)

(

1

Równanie rekurencyjne:

- prawdopodobieństwo tego, że zwracana przez procedurę partition

wartość jest równa j.

n

1

)

(

log

log

2

)

(

n

O

n

n

e

n

T

ave

+

=

log ≡ log

10

ASD

LJ

S

Wrażliwość algorytmu QuickSort

Pesymistyczna wrażliwość czasowa algorytmu:

∆(n)=O(n

2

- nlgn) = O(n

2

)

Oczekiwana wrażliwość czasowa:

68

.

0

)

(log

)

3

2

7

(

)

(

2

+

=

n

O

n

n

π

σ

ASD

LJ

S

background image















































Sortowanie przez scalanie

Merge_Sort

John von Neumann

Sortowanie przez scalanie

ASD

LJ

S

Cechy algorytmu:



Złożoność obliczeniowa O(nlgn),



Stabilny,



Sortowanie ekstensywne,



Zastosowanie techniki „dziel i zwyciężaj”,



Algorytm rekurencyjny,

background image















































Sortowanie przez scalanie

5

2

4

6

1

3

2

6

5

2

4

6

1

3

2

6

5

2

4

6

1

3

2

6

5

2

4

6

1

3

2

6

2

5

4

6

1

3

2

6

2

4

5

6

1

2

3

6

1

2

2

3

4

5

6

6

1

2

2

3

4

5

6

6

2

4

5

6

1

2

3

6

2

5

4

6

1

3

2

6

5

2

4

6

1

3

2

6

Idea algorytmu mergeSort.

ASD

LJ

S

Sortowanie przez scalanie

Merge (A,lewy,q,prawy)
{ // B-tablica pomocnicza

i=lewy;
j=q+1;
k=1;
WHILE(i≤q and j≤prawy) {

IF(A[i]<A[j]){
B[k]=A[i];
i=i+1;
}ELSE{

B[k]=A[j]);
j=j+1;

}
k=k+1;

}
IF(i>q )

Kopiuj A[j],...,A[prawy] do B[k],...,B[prawy];

ELSE

Kopiuj A[i],...,A[q] do B[k],...,B[prawy];

Kopiuj B[lewy],...,B[prawy] do A[lewy],...,A[prawy];

}

MergeSort (A, lewy, prawy)
{

IF(lewy<prawy){

q:= (lewy+prawy)/2
MergeSort (A,lewy,q)
MergeSort (A,q+1,prawy)
Merge (A,lewy,q,prawy)

}

}

ASD

LJ

S

background image















































Złożoność algorytmu

MergeSort

16

8

8

4

4

4

4

1

1

1

1

1

1 1

11

1

1

1

1

1

1

1

1

10

5

5

3

2

3

2

1

1

1

1

1

2

2

1

1

1

1

1

Drzewa podziału algorytmu Merge_sort.

ASD

LJ

S

Złożoność algorytmu

MergeSort

Θ(1)

dla n = 1

T(n) =

2 T(n/2) + Θ(n)

dla n > 1

0

dla n = 1

T(n) =

2 T(n/2) + (n – 1)

dla n > 1

ASD

LJ

S

background image






































Złożoność algorytmu

MergeSort

Θ(1)

dla n = 1

T(n) =

2 T(n/2) + Θ(n)

dla n > 1

0

dla n = 1

T(n) =

2 T(n/2) + (n – 1)

dla n > 1

T(n) = 2

k

T(n/2

k

) + 2

k-1

(n/2

k-1

-1) + 2

k-2

(n/2

k-2

-1) + ... + 2

1

(n/2 -1) + 2

0

(n -1) =

= (n - 2

k-1

) + (n - 2

k-2

) + ...+ (n - 2

-1

) + (n -1) =

= k n – (1+2+...+2

k-1

) = kn – ((2

k

-1) / (2-1)) = kn – (2

k

– 1) =

= nlgn – (n-1).

T(n) =

Θ

(nlgn)

ASD

LJ

S

Złożoność algorytmu

MergeSort

Poprawność rozwiązania:

T(n) = nlgn – n+1

T(2n) = 2n lg(2n) - 2n + 1 = 2n(lg2 + lgn) – 2n + 1 =

= 2nlgn + 1 = 2(nlgn – n +1)+ 2n -2 +1 =

= 2T(n) + 2n -1

T(2n) = 2T(n) + 2n - 1

T(n) = Θ(n lgn)

ASD

LJ

S


Wyszukiwarka

Podobne podstrony:
nw asd w6
nw asd w13
nw asd w3
nw asd w12
nw asd w8
nw asd w4
nw asd w2
nw asd w10
nw asd w5
nw asd w7
ASD w6
nw asd w9
nw asd w2
ASD W6
nw asd w13

więcej podobnych podstron