Sıralama Algoritmaları

Hızlı sıralama




Hızlı Sıralama'nın uygulanması sırasındaki davranışı Yatay çizgiler seçilen pivot elemanları gösterir

Hızlı Sıralama (İngilizcesi: Quicksort) günümüzde yaygın olarak kullanılan bir sıralama algoritmasıdır Hızlı sıralama algoritması n adet sayıyı, ortalama bir durumda, karmaşıklığıyla, en kötü durumda ise karmaşıklığıyla sıralar Algoritmanın karmaşıklığı aynı zamanda yapılan karşılaştırma sayısına eşittir

Tarihi

Hızlı Sıralama algoritması 1960 yılında küçük bir İngiliz şirketi olan Elliot Brothers'ta çalışan C A R Hoare tarafından geliştirilmiştir

Algoritma

Hızlı sıralama algoritması, sıralanacak bir sayı dizisini daha küçük iki parçaya ayırıp oluşan bu küçük parçaların kendi içinde sıralanması mantığıyla çalışır

Algoritmanın adımları aşağıdaki gibidir:

Sayı dizisinden herhangi bir sayıyı pivot eleman olarak seç

Sayı dizisini pivottan küçük olan tüm sayılar pivotun önüne, pivottan büyük olan tüm sayılar pivotun arkasına gelecek biçimde düzenle (pivota eşit olan sayılar her iki yana da geçebilir) Bu bölümlendirme işleminden sonra eleman sıralanmış son dizide olması gerektiği yere gelir Algoritmanın bu aşamasına bölümlendirme aşaması denir

Pivotun sol ve sağ yanında olmak üzere oluşan iki ayrı küçük sayı dizisi, hızlı sıralama algoritması bu küçük parçalar üzerinde yeniden özyineli olarak çağrılarak sıralanır

Algoritma içinde sayı kalmayan (eleman sayısı sıfır olan) bir alt diziye ulaştığında bu dizinin sıralı olduğunu varsayar

Örnek

TEKRARLA

Ara index_sol için

sortFeld[index_sol] ≥ sortFeld[Pivot]

Ara index_sağ için

sortFeld[index_sağ] ≤ sortFeld[Pivot]

EĞER index_sol ve index_sağ bulundu ise

SONRA Değiştir

sortFeld[index_sol] ile sortFeld[index_sağ]

YOKSA

Bir element kaydır

SON EĞER

Koşul tamamlanıncaya kadar

Üstteki algoritmaya göre asagidaki örnek :

SORTIERBEISPIEL

1 - Pivot(karşılaştırma) elementini bulmak için :

İlkönce harfler sayılır Eger toplam tek ise (1) ekleyip ikiye bölünür (15 + 1) / 2 = 8

toplam çift ise ikiye bölünür

2 - Bu durumda Pivot element B oluyor SORTIER B EISPIEL

B


urada ilk harf olan 'S' son harf olan 'L' ve orta harf olan 'B' karşılaştırılır

İçlerinde ortanca olan değer her zaman orta değerdir



Yani örnek şu şekle dönüşür : SORTIER L EISPIEB

3 - Yukarıdaki algoritma göz önünde bulundurulursa;

Kontrol ediliyor : Soldaki element(S) Pivot(L) den büyük mü? ( Evet )

Sağdaki element(B) Pivot(L) den küçük mü? ( Evet )



Eğer iki koşul da doğru ise ilk element(S) ile son element(B) yer değiştirilir ( BORTIER L EISPIES ) (Algoritmaya göre sadece ikisi 'evet' ise değişim gerçekleşir)

Soldaki element(0) Pivot(L) den büyük mü? ( Evet )

Sağdaki element(E) Pivot(L) den küçük mü? ( Evet )



Eğer iki koşul da doğru ise ilk element(0) ile son element(E) yer değiştirilir ( BERTIER L EISPIOS )

Soldaki element(R) Pivot(L) den büyük mü? ( Evet )

Sağdaki element(I) Pivot(L) den küçük mü? ( Evet )



Eğer iki koşul da doğru ise ilk element(R) ile son element(I) yer değiştirilir ( BEITIER L EISPROS )

Soldaki element(T) Pivot(L) den büyük mü? ( Evet )

Sağdaki element(P) Pivot(L) den küçük mü? ( Hayır )



Eğer bir koşul yanlış ise soldaki element(T) sabit kalıyor , sağdaki element(P) yi direk sağa yazılır ( BEIIER L EISPROS ) (DİKKAT : 'T' algoritmaya şu an dahil değil, ta ki ikisi de 'evet' oluncaya kadar)

Soldaki element(T) Pivot(L) den büyük mü? ( Evet )

Sağdaki element(S) Pivot(L) den küçük mü? ( Hayır )



Eğer bir koşul yanlış ise soldaki element(T) sabit kalıyor , sağdaki element(S) yi direk sağa yazılır ( BEIIER L EISPROS )

Soldaki element(T) Pivot(L) den büyük mü? ( Evet )

Sağdaki element(I) Pivot(L) den küçük mü? ( Evet )



Eğer iki koşul da doğru ise element(T) ile element(I) yer değiştirilir ( BEIIIER L ETSPROS ) (Şimdi 'T' yazılabilir, ikisi de evet)

Soldaki element(E) Pivot(L) den büyük mü? ( Hayır )

Sağdaki element(E) Pivot(L) den küçük mü? ( Evet )



Eğer bir koşul yanlış ise soldaki element(E) sola yazılır , sağdaki element(E) sabit kalıyor ( BEIIIER L ETSPROS )

Soldaki element(R) Pivot(L) den büyük mü? ( Evet )

Sağdaki element(E) Pivot(L) den küçük mü? ( Evet )



Eğer bir koşul da doğru ise soldaki element(R) ile sağdaki element(E) sabit kalıyor ( BEIIIEE L RTSPROS )

Son aşama

Soldaki element(R) Pivot(L) den büyük mü? ( Evet )

Sağdaki element(E) Pivot(L) den küçük mü? ( Evet )



Eğer bir koşul yanlış ise soldaki element(R) sola yazılır , sağdaki element(E) sabit kalıyor ( BEIIIEE L RTSPROS )

B - E - I - I - I - E - E - L - R - T - S - P - R - O - S



Aynı işlemleri sağdaki ve soldaki bölümlere ayrı ayrı yapılır

Sonuç şöyle :

B E E E I I I L O P R R S S T



Sözde Kodu

Algoritmanın yalın bir sözde kod olarak gösterimi aşağıdaki gibidir:

function quicksort(array)

var list less, equal, greater

if length(array) ≤ 1

return array

select a pivot value pivot from array

for each x in array

if x < pivot then append x to less

if x = pivot then append x to equal

if x > pivot then append x to greater

return concatenate(quicksort(less), equal, quicksort(greater))