QuickSort

Divide: A[p…r] bos olmayan iki alt diziye
bolunur, A[p…q] ve A[q+1…r] s.t. oyleki
A[p…q] nin her bir elemani A[q+1…r]. Nin
herbir elemanindan kucuk veya kucuk esit.

Conquer: iki alt dizi quicksort e recursive
cagrimla siralanir

Combine: herhangi bir islem yapilmaz
cunku alt diziler kendi aralarinda zaten
sirali
Algoritma Analizi
1
Quicksort (A, p, r)
1. if p < r
2. then q  Partition(A, p, r)
3.
Quicksort(A, p, q)
4.
Quicksort(A, q+1, r)
* In place, not stable
Algoritma Analizi
2
Partition(A, p, r)
1. x  A[p]
2. i  p - 1
3. j  r + 1
4. while TRUE do
5.
repeat j  j - 1
6.
until A[j]  x
7.
repeat i  i + 1
8.
until A[i]  x
9.
if i < j
10.
then exchange A[i]  A[j]
11.
else return j
Algoritma Analizi
3
Example: Partitioning Array
Algoritma Analizi
4
Algorithm Analysis
Quicksort un calisma zamani partition
(bolumleme) nin balanced (dengeli) olup
olmadigina baglidir

Worst-Case Performance (unbalanced):
T(n) = T(1) + T(n-1) + (n)  partitioning takes (n)
= k = 1 to n(k)  T(1) takes (1) time & reiterate
=  (  k = 1 to n k )
= (n2)
* This occurs when the input is completely sorted.
Algoritma Analizi
5
Worst Case Partitioning
Algoritma Analizi
6
Best Case Partitioning
Algoritma Analizi
7
Analysis for Best Case Partition

Eger her tefasinda balanced partition
elde edersek (alt diziler n/2 boyunda), en
iyi performansi elde etmis oluruz.
T(n) = 2T(n/2) + (n)
T(n) = (n log n)
Algoritma Analizi
8
Download

lect08