Algoritmalar dersinde tuttuğum dersleri burada paylaşmaya karar verdim. Belki burada birilerine faydası olur; olmasa da internete erişebildiğim herhangi bir yerden ben tekrar ederim diye düşünüyorum ve başlıyorum ders notlarıma.
- Bu algoritma dizide yerinde sıralama yapar.
- Verilen bir dizi içerisinde bir pivot değeri belirlenir.
- Bu pivot değeri ile dizideki diğer elemanlar karşılaştırılır ve seçilen bu değerden büyük olanlar pivot değerinin sağında, küçük olanlar ise pivot değerinin solunda olacak şekilde dizi sıralanır.
- Divide and conquer (Böl ve Yönet) felsefesini kullanır.
- En kötü durum analizi (worst case) --> O(n2) 'dir.
- Ortalama durum da (average case) --> O(nlgn) 'de çalışır.
- Bir pivot değer üzerinden diziyi ikiye böler ve alt diziler için recursive(tekrarlı) olarak aynı işlemi yapar.
A[p................r]
Divide:
A [p........r] dizisini, A1 [p.......(q-1)], A [q] 'dan küçük ya da eşit ve A2 [(q+1)......r] 'deki tüm elemanlar A[q] 'dan büyük olsun.
Conquer:
A1 [p.......(q-1)] ve A2 [(q+1).......r] dizilerini quick sort a göre sırala.
Combine:
Hiçbir şey yapma.
ALGORİTMASI:
Quick_Sort(A,p,r)
if (p<r)
then q<= PARTITION(A,p,r)
Quick_Sort(A,p,(q-1))
Quick_Sort(A,(q+1),r)
____________________
PARTITION(A,p,r)
x<- A[r]
i<-- p-1
for j->p to r-1
do if A[j] <= x
then i<--i+1
exchange A[i] <--> A[j]
exchange A[i+1] <--> A[r]
return i+1
_____________________
Hiç yorum yok:
Yorum Gönder