Sıralama Algoritmaları

Sıralama algoritmaları
Sıralama algoritması
Ağaç sıralaması
Basamağa göre sıralama
Birleştirmeli sıralama
Cüce sıralaması
Eklemeli sıralama
Güvercin yuvası sıralaması
Hızlı sıralama
Kabarcık sıralaması
Kabuk sıralaması
Kokteyl sıralaması
Kova sıralaması
Kütüphane sıralaması
Rahat sıralama
Sabır sıralaması
Sayarak sıralama
Saçma sıralama
Seçmeli sıralama
Sıralama
Tarak sıralaması
Yığın sıralaması
İplik sıralaması
İçgözlemle sıralama

Sıralama algoritması

Yığın Sıralaması'nın rastgele üretilmiş sayıları nasıl sıraladığını gösteren örnek Algoritmanın ilk aşamasında dizinin öğeleri yığın yapısını oluşturmak için yeniden düzenlenir

Sıralama algoritması, bilgisayar bilimlerinde ya da matematikte kullanılan, verilen bir listenin elemanlarını belirli bir sıraya sokan algoritmadır En çok kullanılan sıralama türleri, sayı büyüklüğüne göre sıralama ve alfabetik sıralamadır Sıralama işleminin verimli yapılması, arama ve birleştirme algoritmaları gibi çalışması için sıralanmış dizilere gereksinim duyan algoritmaların başarımının yüksek olması için önemlidir Sıralama algoritmaları bilgisayarlarda tutulan verilerin düzenlenmesini ve insan kullanıcı tarafından daha rahat algılanmasını da sağlar

Sıralama algoritmaları, tanımı çok yalın olmasına karşın çözümü çok karmaşık olan bir işi gerçekleştirdikleri için, üzerinde en fazla araştırma yapılan bilgisayar bilimi konularından biridir Çoğu kişi sıralama sorununu çözülmüş bir sorun olarak görse de, yeni sıralama algoritmaları üzerinde araştırmalar sürmektedir Örneğin kütüphane sıralaması ilk olarak 2004 yılında ortaya atılmıştır Sıralama algoritmaları, sayılarının çok olması ve değişik yaklaşımlar sunmaları nedeniyle özellikle giriş düzeyindeki bilgisayar bilimleri derslerinde büyük O gösterimi ve veri yapıları gibi temel algoritma kavramlarının açıklanması amacıyla yaygın biçimde kullanılırlar



Birleştirmeli sıralama'nın rastgele üretilmiş sayıları gösteren noktaları nasıl sıraladığını gösteren örnek

Bilgisayar bilimlerinde kullanılan sıralama algoritmaları genellikle aşağıdaki ölçütlere göre sınıflandırılır:

Hesaplama karmaşıklığı: Dizideki öğelerin karşılaştırılmasının en iyi, ortalama ve en kötü başarımının dizinin boyutu (n) cinsinden gösterilmiş halidir Olağan uygulamalarda sıralama algoritmalarının iyi durum başarımı O(n log n) ve kötü durum başarımı is Ω(n²)'dir Bir sıralama algoritmasının istenen karmaşıklığı O(n)'dir Yalnızca soyut bir anahtar karşılaştırması yapan bütün sıralama algoritmaları en kötü durumda her zaman Ω(n log n) karşılaştırma yaparlar

Yer Değiştirme Karmaşıklığı (yerinde sıralama algoritmaları için)
Bellek (ve diğer donanım kaynaklarının) Kullanımı: Bazı sıralama algoritmaları dizinin içerdiği öğelerin dizinin saklandığı alanda sıralar Böylece sıralanan öğeler dışında yalnızca O(1) ya da O(log n)'lik bir ek bellek alanı gerekir Bazı algoritmalar ise verinin geçici olarak saklanması için dizinin tutulduğu alanın dışında ek bellek alanlarına gereksinim duyar

Özyineleme: Bazı algoritmalar ya özyinelemeli ya da özyinelemesiz çalışırken, birleştirmeli sıralama gibi bazı algoritmalar iki biçimde de uygulanabilir

Kararlılık
Kaşılaştırma sıralaması olup olmama: Bir karşılaştırma sıralaması sıralanacak veriyi, bir karşılaştırma işlemi kullanarak, karşılaştırarak inceler
Genel Yöntem: Araya sokma, değiştirme, seçme, birleştirme vb Değiştirme sıralamalarına kabarcık sıralaması ve hızlı sıralama örnek olarak gösterilebilir Yığın sıralaması ise seçme sıralamalarındandır

Kararlılık

Kararlı sıralama algoritmaları sıralanacak dizinin içinde değerleri birbirine eşit olan öğerlerin birbirlerine göre olan konulmlarını korur Başka bir deyişle, bir sıralama algoritması kararlı olduğunda, eğer R ve S gibi içerdiği değer aynı olan iki öğe bulunduran asıl dizide, R, S' den önce geliyorsa, sıralanmış dizide de R, S'den önce gelir

Dizinin içinde birbirine eşit değerler içeren öğeler birbirlerinden ayırt edilemiyorsa (örneğin sayılar ya da harfler gibi değerler öğenin kendisini oluşturuyor ise) kararlılık bir sorun değildir Ancak aşağıda gösterildiği gibi sayı çiftleri, her çiftin virgülden önceki sayısına göre sıralanacağı düşünülürse kararlılık sorunu ortaya çıkar

(4, 1) (3, 7) (3, 1) (5, 6)



Bu durumda, 2 değişik sonuç mümkündür; ilk çözüm sıralama anahtarlarının değerleri aynı olan öğelerinin sırasını korur, ikincisi ise korumaz:

(3, 7) (3, 1) (4, 1) (5, 6) (sıra korunmuş)
(3, 1) (3, 7) (4, 1) (5, 6) (sıra değişmiş)



Kararsız sıralama algoritmaları sıralama anahtarlarının değerleri aynı olan öğelerin dizi içindeki sırasını değiştirebilir ancak kararlı sıralama algoritmaları asla değiştirmez Kararsız sıralama algoritmaları özellikle kararlı olacak biçimde uygulanabilir Bunu yapmanın bir yolu yapay olarak anahtar karşılaştırmasını anahtlarının değerleri birbirine eşit olan iki öğenin durumunu belirlemek için asıl listedeki konumlarını ölçüt olarak kullanacak biçimde genişletmektir Ancak asıl dizideki öğre sırasının hatırlanması çoğu zaman ek saklama alanı gerektirir

Ağaç sıralaması

Ağaç sıralaması, bilgisayar bilimlerinde kullanılan, herhangi bir diziden önce bir ikili arama ağacı oluşturup ardından bu ağacın üzerinden geçerek dizinin sıralanmasını sağlayan bir sıralama algoritmasıdır

Basamağa göre sıralama

(İngilizcesi: Radix sort) bilgisayar bilimlerinde sayıları basamaklarının üzerinde işlem yaparak sıralayan bir sıralama algoritmasıdır Sayma sayıları adlar ya da tarihler gibi karakter dizilerini göstermek için kullanılabildiği için basamağa göre sıralama algoritması yalnızca sayma sayılarını sıralamak için kullanılan bir algoritma değildir

Çoğu bilgisayar veri saklamak için ikilik tabandaki sayıların elektronikteki gösterim biçimlerini kullandığı için sayma sayılarının basamaklarını ikilik tabandaki sayılardan oluşan öbekler biçiminde göstermek daha kolaydır Basamağa göre sıralama algoritması en anlamlı basamağa göre sıralama ve en anlamsız basamağa göre sıralama olarak ikiye ayrılır En anlamsız basamağa göre sıralama algoritması sayıları en anlamsız (en küçük, en sağdaki) basamaktan başlayıp en anlamlı basamağa doğru yürüyerek sıralarken en anlamlı basamağa göre sıralama bunun tam tersini uygular

Sıralama algoritmaları tarafından işlenen ve kendi sayı değerlerini gösterebildiği gibi başka tür verilerle de eşleştirilebilen sayma sayılarına çoğu zaman "anahtar" denir En anlamsız basamağa göre sıralamada kısa anahtarlardan uzunlardan önce gelirken aynı uzunluktaki anahtarlar sözlükteki sıralarına göre sıralanırlar Bu sıralama biçimi sayma sayılarının kendi değerlerine göre sıralandıklarında oluşan sırayla aynı sırayı oluşturur Örneğin 1'den 10'a kadar olan sayılar sıralandığında ortaya 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 dizisi çıkacaktır

En anlamlı basamağa göre sıralama sözcükler ya da aynı uzunluktaki sayılar gibi dizgileri sıralamak için uygun olan sözlükteki sıraya göre sıralar Örneğin "b, c, d, e, f, g, h, i, j, ba" dizisi sözlük sırasına göre "b, ba, c, d, e, f, g, h, i, j" olarak sıralanacaktır Eğer sözlük sırası değişken uzunluktaki sayılarda uygulanırsa sayılar değerlerinin gerektirdiği konumlara konulmazlar Örneğin 1'den 10'a kadar olan sayılar sıralandığında, algoritma kısa olan sayıların sonuna boş karakter koyarak bütün anahtarları en uzun anahtarla aynı boyuta getireceğinden sonuç 1, 10, 2, 3, 4, 5, 6, 7, 8, 9 olacaktır

Cüce sıralaması
(İngilizcesi: Gnome sort), bilgisayar bilimlerinde kullanılan araya sokmalı sıralamaya benzer bir sıralama algoritmasıdır Ara sokmalı sıralamadan farkı kabarcık sıralaması yönteminde olduğu gibi, bir elemanın sıralanan dizideki yerine birçok yer değiştirme yoluyla gelmesidir Cüce Sıralaması adı algoritmanın yönteminin mitolojideki Hollanda cücelerinin (gnome) bir dizi çiçek saksısını sıraya diziş biçimine benzemesinden kaynaklanmaktadır

Sözde Kodu

function gnomeSort(a[0size-1]) {

i := 1

j := 2

while i < size - 1

if a[i-1] >= a[i]

i := j

j := j + 1

else

swap a[i-1] and a[i]

i := i - 1

if i = 0

i := 1

}



Algoritmanın Java Uygulaması

void gnomeSort(int a[]) {

int i = 1;

int j = 2;

while (i < alength - 1) {

if (a[i - 1] >= a[i]) {

i = j;

j++;

}

else {

int temp = a[i];

a[i] = a[i - 1];

a[i - 1] = temp;

i--;

if (i == 0) {

i = 1;

}

}

}



Eklemeli Sıralama


(İngilizcesi: Insertion Sort), bilgisayar bilimlerinde kullanılan ve sıralı diziyi her adımda öğe öğe oluşturan bir sıralama algoritmasıdır Büyük dizilerle çalışıldığında hızlı sıralama, birleştirmeli sıralama ve yığın sıralaması gibi daha gelişmiş sıralama algoritmalarından daha verimsiz çalışır Ancak buna karşın bazı artıları da vardır:



Eklemeli Sıralama'nın rastgele üretilmiş sayıları nasıl sıraya dizdiğini gösteren bir örnek

Uygulaması kolaydır

Küçük Veri kümeleri üzerinde kullanıldığında verimlidir

Çoğunluğu zaten sıralanmış olan diziler üzerinde kullanıldığında verimlidir

Karmaşıklığı mathcal{O}(n^2) olan seçmeli sıralama ve kabarcık sıralaması gibi çoğu yalın sıralama algoritmalarından daha verimlidir

Kararlı bir sıralama algoritmasıdır (değeri eşit olan öğelerin asıl listedeki göreceli konumlarını değiştirmez)

Sıralanacak diziyi yerinde sıralar, ek bir bellek alanı gerektirmez

Sıralanacak dizinin hepsinin algoritmanın girdisi olmasına gerek yoktur Dizi parça parça da alınabilir ve sıralama işlemi sırasında diziye yeni veriler eklenebilir

İnsanlar herhangi birşeyi (örneğin, iskambil kartları) sıralarken, çoğu durumda eklemeli sıralamaya benzer bir yöntem kullanırlar

Sözde Kodu

insertionSort(array A)

for i = 1 to length[A-1] do

value = A[i]

j = i-1

while j >= 0 and A[j] > value

A[j + 1] = A[j]

j = j-1

A[j+1] = value



Güvercin yuvası sıralaması


Güvercin yuvası sıralaması, n adet öğeyi N adet "güvercin yuvası" (sıralanacak öğelerin alabileceği olası değerlerin sayısı) ile (Θ(n + N)) karmaşıklığıyla sıralayan bir sıralama algoritmasıdır N O(n) olduğunda algoritma doğrusal zamanda çalışır Bir sıralama algoritmasının dizideki öğeleri sıralamak için her bir öğeye en az bir kere bakması zorunlu olduğundan doğrusal zaman sıralama algoritmasından bağımsız olarak erişilebilecek en iyi sonuçtur

Güvercin yuvası algoritması aşağıdaki biçimde çalışır:

Başlangıçta boş "güvercin yuvalarının" bulunduğu her bir arama anahtarı aralığına bir güvercin yuvası düşecek biçimde bir dizi oluştur

Sıralanacak dizinin üzerinden geçerek bütün öğeleri ilgili güvercin yuvasına yerleştir

Güvercin yuvası disizinin üzerinden sırayla gerçerek boş olmayan bütün yuvalardaki öğeleri asıl diziye aktar

Güvercin yuvası sıralaması hızlı çalışması için gereken durumların nadiren oluşması ve diğer daha esnek ve neredeyse aynı hızda çalışan algoritmaların kullanımı daha kolay olduğu için pek kullanılmaz Özellikle kova sıralaması güvercin yuvası sıralamasının uygulamada daha fazla kullanılan bir türüdür

Sözde kodu

N adet ayrık elemanı sıralayan güvercin yuvası sıralamasının sözde kodu aşağıdaki gibidir:

function pigeonhole_sort(array a[n])

array b[N]

var i,j

zero_var (b) (* zero out array b *)

for i in [0length(a)-1]

b[a[i]] := b[a[i]]+1

(* copy the results back to a *)

j := 0

for i in [0length(b)-1]

repeat b[i] times

a[j] := i

j := j+1

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))

Kabarcık sıralaması



Kabarcık sıralaması'nın rastgele üretilmiş sayıları sıraladığını gösteren bir örnek

Kabarcık Sıralaması, bilgisayar bilimlerinde kullanılan yalın bir sıralama algoritmasıdır Sıralanacak dizinin üzerinde sürekli ilerlerken her defasında iki öğenin birbiriyle karşılaştırılıp, karşılaştırılan öğelerin yanlış sırada olmaları durumunda yerlerinin değiştirilmesi mantığına dayanır Algoritma, herhangi bir değişiklik yapılmayıncaya kadar dizinin başına dönerek kendisini yineler Adına "Kabarcık" sıralaması denmesinin nedeni büyük olan sayıların aynı suyun altındaki bir kabarcık gibi dizinin üstüne doğru ilerlemesidir

Başlangıçta yer yer değiştirme sıralaması olarak adlandırılan kabarcık sıralaması, dizi içindeki büyük elemanların algoritmanın her adımında dizinin sonuna doğru doğrusal olarak ilerlemesini sağlar Bu ilerleme, seçmeli sıralama algoritmasındaki dizideki değeri küçük olan elemanların dizinin başında kümelenmesi yöntemine benzer şekilde gerçekleşir

İnceleme

Kabarcık sıralaması dizinin başından başlar ve dizi elemanlarını sırayla seçer Seçilen dizi elemanı kendinden sonra gelen elemandan büyükse bu iki elemanın yerleri değiştirilir Bu işlem sonucunda dizinin en büyük elemanı dizi sonuna yerleştirildiğinden bir sonraki adımda arama sınırı bir eleman geri çekilir Bu işlem, dizinin sonundaki elemanın karşılaştırılmasına kadar yinelenerek sürdürülür

Algoritmanın Karmaşıklığı

Kabarcık sıralama algoritmasının ortalama ve en kötü durumdaki karmaşıklığı 'dir Algoritma ortalama ve en kötü durumda adet karşılaştırma ve yer değiştirme gerçekleştirir

Algoritmanın Adım Adım İşleyişi

İçeriği "5 1 4 2 8" olan bir dizi kabarcık sıralaması ile en küçükten en büyüğe doğru aşağıdaki biçimde sıralanır Her adımda dizinin kalın olarak işaretlenmiş elemenları karşılaştırılan elemanlardır

Birinci Geçiş:

( 5 1 4 2 8 ) o ( 1 5 4 2 8 ) Burada algoritma ilk iki elemanı karşılaştırır ve yerlerini değiştirir

( 1 5 4 2 8 ) o ( 1 4 5 2 8 )

( 1 4 5 2 8 ) o ( 1 4 2 5 8 )

( 1 4 2 5 8 ) o ( 1 4 2 5 8 ) Burada elemanlar zaten sıralı olduğu için algoritma yerlerini değiştirmez
İkinci Geçiş:

( 1 4 2 5 8 ) o ( 1 4 2 5 8 )

( 1 4 2 5 8 ) o ( 1 2 4 5 8 )

( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

Artık dizi sıralıdır ancak algoritma işlemin bittiğini bilmemektedir Algoritmanın dizinin sıralandığını anlaması için bütün dizinin üzerinden hiçbir değişiklik yapmadan tam bir geçiş yapması gerekir
Üçüncü Geçiş:

( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

( 1 2 4 5 8 ) o ( 1 2 4 5 8 )

Sonuç olarak dizi sıralanmıştır ve algoritma sonlanır

Sözde Kodu

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

procedure bubbleSort( A : sıralanabilir öğe dizisi ) defined as:

do

swapped := false

for each i in 0 to length( A ) - 2 do:

if A[ i ] > A[ i + 1 ] then

swap( A[ i ], A[ i + 1 ] )

swapped := true

end if

end for

while swapped



end procedure </gösterilebilir:

procedure bubbleSort( A : sıralanabilir öğe dizisi ) defined as:

for each i in 1 to length(A) do:

for each j in length(A) downto i + 1 do:

if A[ j -1 ] > A[ j ] then

swap( A[ j - 1], A[ j ] )

end if

end for

end for

end procedure

Kabuk sıralaması


(İngilizcesi: Shell sort), bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır Eklemeli sıralama algoritmasının aşağıdaki iki gözlem kullanılarak genelleştirilmiş biçimidir:

Eklemeli sıralama, sıralanacak dizi zaten büyük oranda sıralıysa daha verimli çalışır

Eklemeli sıralama, dizideki öğeleri her adımda yalnızca bir sonraki konuma aktardığından verimsizdir

Algoritmanın Geçmişi

Kabuk sıralaması algoritmasının adı algoritmayı bulan kişi olan Donald Shell'den gelmektedir Soyadı İngilizce'de Kabuk anlamına gelen Donald Shell algoritmayı 1959 yılında yayınlamıştır

Uygulamalar

C/C++ dilinde yazılmış kabuk sıralaması

Aşağıda C/C++ dilinde yazılmış, bir sayı dizisini kabuk sıralaması algoritmasını kullanarak sıralayan bir program verilmiştir

/*

SHELL SORT

Written by erengencturknet

*/

#include <stdioh>

#define ELEMENTS 6

void shellsort(int A[],int max)

{

int stop,swap,limit,temp,k;

int x=(int)(max/2)-1;

while(x>0)

{

stop=0;

limit=max-x;

while(stop==0)

{

swap=0;

for(k=0;k<limit;k++)

{

if(A[k]>A[k+x])

{

temp=A[k];

A[k]=A[k+x];

A[k+x]=temp;

swap=k;

}

}

limit=swap-x;

if(swap==0)

stop=1;

}

x=(int)(x/2);

}

}

int main()

{

int i;

int X[ELEMENTS]={5,2,4,6,1,3};

printf("Unsorted Array:
");

for(i=0;i<ELEMENTS;i++)

printf("%d ",X[i]);

shellsort(X,ELEMENTS);

printf("
SORTED ARRAY
");

for(i=0;i<ELEMENTS;i++)

printf("%d ",X[i]);

}



Java dilinde yazılmış kabuk sıralaması

public static void shellSort(int[] a) {

for (int increment = alength / 2; increment > 0;

increment = (increment == 2 ? 1 : (int) Mathround(increment / 22))) {

for (int i = increment; i < alength; i++) {

int temp = a[i];

for (int j = i; j >= increment && a[j - increment] > temp; j -= increment){

a[j] = a[j - increment];

a[j - increment] = temp;

}

}

}

}



Python dilinde yazılmış kabuk sıralaması

def shellsort(a):

def increment_generator(a):

h = len(a)

while h != 1:

if h == 2:

h = 1

else:

h = 5*h//11

yield h

for increment in increment_generator(a):

for i in xrange(increment, len(a)):

for j in xrange(i, increment-1, -increment):

if a[j - increment] < a[j]:

break

a[j], a[j - increment] = a[j - increment], a[j]

return a

Kokteyl sıralaması


Kokteyl sıralaması, bilgisayar bilimlerinde kabarcık sıralaması algoritmasına benzer bir sıralama algoritmasıdır Kabarcık sıralamasından farkı sıralanacak listenin üzerinden tek yöne doğru değil iki yöne de geçerek öğeleri sıralamasıdır Algoritmanın uygulanması kabarcık sıralaması algoritmasının uygulanmasından çok az daha zordur

Sözde kodu

Kokteyl sıralamasının en yalın biçimi her defasında listenin tamamının üzerinden geçer:

procedure cocktailSort( A : list of sortable items ) defined as:

do

swapped := false

for each i in 0 to length( A ) - 2 do:

if A[ i ] > A[ i + 1 ] then // ardışık iki öğenin doğru sırada olup olmadığına bak order

swap( A[ i ], A[ i + 1 ] ) // iki öğenin yerlerini değiştir

swapped := true

end if

end for

if swapped = false then

// eğer değişiklik yapılmadıysa dıştaki döngüden çıkabiliriz

break do-while loop

end if

swapped := false

for each i in length( A ) - 2 to 0 do:

if A[ i ] > A[ i + 1 ] then

swap( A[ i ], A[ i + 1 ] )

swapped := true

end if

end for

while swapped // hiçbir öğe yer değiştirmediyse liste sıralanmıştır

end procedure

Kova Sıralaması


Elemanlar önce kovalar arasında dağıtılır



Daha sonra her kovadaki elemanlar kendi içinde sıralanır

Kova Sıralaması (ya da sepet sıralaması), sıralanacak bir diziyi parçalara ayırarak sınırlı sayıdaki kovalara (ya da sepetlere) atan bir sıralama algoritmasıdır Ayrışma işleminin ardından her kova kendi içinde ya farklı bir algoritma kullanılarak ya da kova sıralamasını özyinelemeli olarak çağırarak sıralanır

Kova sıralaması aşağıdaki biçimde çalışır:

Başlangıçta boş olan bir "kovalar" dizisi oluştur

Asıl dizinin üzerinden geçerek her öğeyi ilgili aralığa denk gelen kovaya at

Boş olmayan bütün kovaları sırala

Boş olmayan kovalardaki bütün öğeleri yeniden diziye al

Sözde kodu

function bucket-sort(array, n) is

buckets ← new array of n empty lists

for i = 0 to (length(array)-1) do

insert array[i] into buckets[msbits(array[i], k)]

for i = 0 to n - 1 do

next-sort(buckets[i])

return the concatenation of buckets[0], , buckets[n-1]

Kütüphane Sıralaması

Kütüphane Sıralaması, ya da diğer bir deyişle aralıklı eklemeli sıralama, eklemeli sıralama algoritmasını art arda yapılan eklemeleri dizideki boşlukları kullanıp hızlandırarak kullanan bir sıralama algoritmasıdır Adının kütüphabe sıralaması olması bir benzetmeden gelmektedir:

Bir kütüphane görevlisinin bir raftaki bütün kitapları A harfiyle başlayanlar sol tarafta kalarak sağa doğru kitapların arasında boşluk kalmayacak biçimde alfabetik sıraya dizmek istediğini varsayalım Eğer görevli B bölümüne ait yeni bir kitabı yerleştirmek isterse kitabın yerini B alanında bulduktan sonra yeni kitaba yer açmak için ilgili kitaptan sonraki bütün kitapları sağa kaydırması gerekir Bu bir eklemeli sıralamadır Ancak, eğer görvli daha önce her bir harften sonra belirli bir boşluk bırakmış olsaydı, yalnızca B harfindeki kitapların yarısını hareket ettirerek bu sıralamayı sağlayabilirdi Kütüphane sıralamasının ana ilkesi budur

Algoritma Michael A Bender, Martín Farach-Colton, ve Miguel Mosteiro tarafından 2004'te geliştirilmiştir Kütüphane sıralaması, aynı kendisinden türetildiği eklemeli sıralama gibi, kararlı bir karşılaştırma sıralamasıdır ve sıralamayı yaptığı sırada sıraladığı diziye yeni elemanlar eklenmesine izin verir Ayrıca kütüphane sıralaması çoğu durumda eklemeli sıralama algoritmasının O(n2) karmaşıklığı yerine hızlı sıralama algoritmasının O(n log n) karmaşıklığına yaklaşmaktadır Tek sorunu ise algoritmanın kullanıdığı aralıklar nedeniyle fazladan yere gereksinim duymasıdır

Sabır sıralaması

Sabır sıralaması bilgisayar bilimlerinde kullanılan ve bir kâğıt oyununa dayanan bir sıralama algoritmasıdır

Kağıt oyunu

Oyun, 1, 2, , n biçiminde numaralandırılmış n adet oyun kağıdından oluşan desteyle oynanır Kağıtlar masanın üzerinde aşadaki kurallara uygun olarak bölümlere ayrılır:

Başlangıçta hiçbir kâğıt yığını yoktur Oynanan ilk kart tek kartta oluşan bir alt deste oluşturur

Oynanan her yeni kart ya en üstte kendisinden daha büyük bir kart bulunan kâğıt yığının en üstüne ya da masadaki tüm yığınların en sağına yeni bir yığın oluşturmak üzere yerleştirilir

Dağıtılacak kâğıt kalmadığı zaman oyun biter

Oyunun amacı oyunu olabilecek en az sayıda kâğıt yığınıyla bitirmektir

Sabır sıralaması

Sabır sıralaması bilgisayar bilimlerinde kullanılan ve bir kâğıt oyununa dayanan bir sıralama algoritmasıdır

Kağıt oyunu

Oyun, 1, 2, , n biçiminde numaralandırılmış n adet oyun kağıdından oluşan desteyle oynanır Kağıtlar masanın üzerinde aşadaki kurallara uygun olarak bölümlere ayrılır:

Başlangıçta hiçbir kâğıt yığını yoktur Oynanan ilk kart tek kartta oluşan bir alt deste oluşturur
Oynanan her yeni kart ya en üstte kendisinden daha büyük bir kart bulunan kâğıt yığının en üstüne ya da masadaki tüm yığınların en sağına yeni bir yığın oluşturmak üzere yerleştirilir
Dağıtılacak kâğıt kalmadığı zaman oyun biter

Oyunun amacı oyunu olabilecek en az sayıda kâğıt yığınıyla bitirmektir

Sayarak sıralama

Sayarak sıralama bilgisayar bilimlerinde kullanılan ve kova sıralaması gibi sıralanacak dizinin içindeki değerlerin aralığının bilinmesi durumunda kullanılabilen bir sıralama algoritmasıdır Sayarak sıralama algoritması dizideki değerlerin aralık bilgilerini yeni bir dizi oluşturmak için kullanır Oluşturulan yeni dizinin her bir satırı ana dizide o satır numarasının değerine sahip öğelerin sayısını gösterir Yeni dizideki öğe değeri sayıları daha sonra ana dizideki tüm değerlerin doğru konuma konulması için kullanılır Sayarak sıralama algoritması güvercin yuvası sıralamasından daha verimsiz bir algoritmadır

C++ ile uygulaması

Aşağıdaki program sayarak sıralama algoritmasının C++ dilinde yazılmış bir uygulamasını göstermektedir

/// countingSort - değerleri tutan bir diziyi sıralamak için
///
/// Algoritmanın verimli çalışması için sıralacak
/// değerlerin aralığı sıralanacak öğelerin sayısından
/// çok daha büyük olmamalıdır
///
/// param nums - girdi - sıralanacak değerler dizisi
/// param size - girdi - dizideki öğelerin sayısı
///
void counting_sort(int *nums, int size)
{
// search for the minimum and maximum values in the input
int i, min = nums[0], max = min;
for(i = 1; i < size; ++i)
{
if (nums[i] < min)
min = nums[i];
else if (nums[i] > max)
max = nums[i];
}

// create a counting array, counts, with a member for
// each possible discrete value in the input
// initialize all counts to 0
int distinct_element_count = max - min + 1;
int[] counts = new int[distinct_element_count];
for(i=0; i<distinct_element_count; ++i)
counts[i] = 0;

// accumulate the counts - the result is that counts will hold
// the offset into the sorted array for the value associated with that index
for(i=0; i<size; ++i)
++counts[ nums[i] - min ];

// store the elements in the array
int j=0;
for(i=min; i<=max; i++)
for(int z=0; z<counts[i-min]; z++)
nums[j++] = i;

delete[] counts;

Saçma sıralama

Saçma sıralama (ya da rastgele sıralama) bilgisayar bilimlerinde yalnızca eğitim amaçlı olarak kullanılan verimsiz bir sıralama algoritmasıdır Bir deste oyun kağıdı saçma sıralama algoritmasıyla sıralanmak istendiğinde, destenin sıralı olup olmadığına bakılır, eğer deste sıralı değilse havaya atılarak yere düşen kartlar toplanarak deste yeniden oluşturulur Bu işlem deste sıralanana kadar sürer

Uygulama

Sözde kodu:

while not InOrder(deck) do Shuffle(deck);



Java

public int[] BogoSort(int[] numbers)
{
Random rnd = new Random();
while(true)
{
boolean sorted = true;
for(int i = 0; i < numberslength-1; i++)
if(numbers[i] > numbers[i+1])
sorted = false;
if (sorted)
return numbers;
for(int i = numberslength - 1; i > 0; i--)
{
int rand = rndnextInt(i);
int temp = numbers[i];
numbers[i] = numbers[rand];
numbers[rand] = temp;
}
}
}



Benzer algoritmalar

Rastgele değiştirmeli sıralama

Rastgele değiştirmeli sıralama, rastgele sayı seçmeye dayalı, saçma sıralamaya benzer bir sıralama algoritmasıdır Eğer sıralanacak dizi sıralı değilse algoritma rastgele iki sayı seçer ve bu iki sayıyı birbiriyle değiştirir Algoritmanın çalışma süresini belirlemek oldukça zordur ve gerçek uygulamalarında sıralanmış bir diziye ulaşamayabilir

Seçmeli Sıralama


Seçmeli Sıralama, bilgisayar bilimlerinde kullanılan karmaşıklığı bir sıralama algoritmasıdır Karmaşıklığı
olduğu için büyük listeler üzerinde kullanıldığında verim sağlamaz ve genel olarak benzeri olan eklemeli sıralamadan daha başarısızdır Seçmeli sıralama yalın olduğu ve bazı durumlarda daha karmaşık olan algoritmalardan daha iyi sonuç verdiği için tercih edilebilir



Seçmeli sıralama algoritması



Seçmeli Sıralama'nın nasıl çalıştığını gösteren görüntü

Yöntem
Seçmeli Sıralama'nın nasıl çalıştığını gösteren görüntü

Algoritma aşağıdaki gibi çalışır:

Listedeki en küçük değerli öğeyi bul
İlk konumdaki öğeyle bulunan en küçük değerli öğenin yerini değiştir
Yukarıdaki adımları listenin ilk elemanından sonrası için (ikinci elemandan başlayarak) yinele

Sözde Kodu

A sıralanacak öğeler kümesi, n ise A'daki öğe sayısıdır Dizi 0 numaralı dizinle başlamaktadır

for i ← 0 to n-2 do
min ← i
for j ← (i + 1) to n-1 do
if A[j] < A[min]
min ← j
swap A[i] and A[min]



Seçmeli Sıralama Algoritmasının Örnek Kodu

public int[] secmeliSiralama(int[] dizi)
{
int enkucuk, yedek;
for (int i = 0; i < diziLength - 1; i++)
{
enkucuk = i;
for (int j = i + 1; j < diziLength; j++)
if (dizi[j] < dizi[enkucuk])
enkucuk = j;
if (enkucuk != i)
{
yedek = dizi[i];
dizi[i] = dizi[enkucuk];
dizi[enkucuk] = yedek;
}
}
return dizi;





6 elemanlı içeriği karışık olarak verilmiş bir bir sayı dizisinin Seçmeli Sıralama algoritması kullanılarak nasıl küçükten-büyüğe doğru sıralandığını göstermektedir 1 adımda dizinin ilk elemanı (6) alınır Bu eleman diğer 5 eleman ile karşılaştırılır Eğer bulunan eleman(1) ilk elemandan küçükse 1elman ile yer değiştirilir 2 adımda dizinin ikinci elemanı(3) alınır Bu eleman kalan 4 eleman ile karşılaştırılır Eğer bulunan eleman(2) ikinci elemandan küçükse 2 eleman ile yer değiştirilir ve bu işlem dizi sonuna kadar devam eder Böylelikle dizi küçükten-büyüğe sıralanmış olur

Sıralama

Sıralama bir dizi elemanı, belirli bir özelliğine göre sıraya dizme işlemine verilen addır Bilgisayar bilimlerinin en çok incelenmiş konularından birisi sıralama algoritmalarıdır

Karışık halde: 9 4 2 8 3 1 5 6 7
Sıraya dizilmiş: 1 2 3 4 5 6 7 8 9



Sıralama, genellikle indekslerde, ansiklopedilerde kullanılır Ayrıca şuralarda da yaygındır: Katalog, bibliyografya, sözlük, kütüphane fişleri, ve bazı arama motorları

Tarrak Sıralaması
Tarrak Sıralaması, ilk defa 1991 yılının Nisan ayında Stephen Lacey ve Richard Box tarafından Byte dergisinde duyurulmuş yalın bir sıralama algoritmasıdır Kendisinden önce duyurulmuş kabarcık sıralaması algoritmasından başarılıdır ve karmaşıklıkta hızlı sıralama algoritmasıyla yarışır Algoritmanın ana fikri listenin sonundaki küçük değerli öğelerin sayısını azaltmaktır Kabarcık sıralaması algoritmasında sıralanacak listenin sonundaki küçük değerli öğelerin varlığı algoritmayı çok yavaşlattığı için tarak sıralamasında bu değerlerin sayısının azaltılması yoluna gidilmiştir

Kabarcık sıralaması algoritmasında iki öğe karşılaştırıldığında aralarındaki mesafe her zaman 1'dir Başka bir deyişle, kabarcık sıralaması her zaman ardışık iki değeri karşılaştırır Taraf sıralaması ise bunun aksine aralarındaki mesafe birden çok daha fazla olan öğeleri karşılaştırabilir (Kabuk sıralaması da aynı düşünceyle tasarlanmıştır ancak kabuk sıralaması kabarcık sıralamasının değil seçmeli sıralamanın bir türevidir)

Sözde Kodu

function combsort11(array input)
gap := inputsize //öğeler arasındaki aralığın başlangıç boyutunu belirle

loop until gap <= 1 or swaps = 0
//yeni bir tarama için aralığın boyutunu güncelle
if gap > 1
gap := gap / 13
if gap = 10 or gap = 9
gap := 11
end if
end if

i := 0
swaps := 0 // Açıklama için kabarcık sıralamasına bakınız

// giriş listesinin üzerinden tek bir "tarama"
loop until i + gap >= arraysize //Benzer yaklaşım için kabuk sıralamasına bakınız
if array[i] > array[i+gap]
swap(array[i], array[i+gap])
swaps := 1 // Aritmetik taşma düzeltmesi için
end if
i := i + 1
end loop

end loop
end function

Yığın Sıralaması

(İngilizcesi: Heapsort), bilgisayar bilimlerinde kullanılan karşılaştırmaya dayalı bir sıralama algoritmasıdır Uygulamada pek çok bilgisayarda hızlı sıralama algoritmasından daha yavaş çalışsa da en kötü durumda O(n log n) çalışma süresi vardır Yığın sıralaması diziyi yerinde sıralar ancak kararlı bir sıralama algoritması değildir

Sözde Kodu

Aşağıda yığın sıralaması algoritmasının sözde kodu verilmiştir swap dizideki iki öğenin yerlerini değiştirmek için kullanılmaktadır

function heapSort(a, count) is
input: an unordered array a of length count

(first place a in max-heap order)
heapify(a, count)

end := count - 1
while end > 0 do
(swap the root(maximum value) of the heap with the last element of the heap)
swap(a[end], a[0])
(decrease the size of the heap by one so that the previous max value will
stay in its proper placement)
end := end - 1
(put the heap back in max-heap order)
siftDown(a, 0, end)

function heapify(a,count) is
(start is assigned the index in a of the last parent node)
start := (count - 1) / 2

while start ≥ 0 do
(sift down the node at index start to the proper place such that all nodes below
the start index are in heap order)
siftDown(a, start, count-1)
start := start - 1
(after sifting down the root all nodes/elements are in heap order)

function siftDown(a, start, end) is
input: end represents the limit of how far down the heap
to sift
root := start

while root * 2 + 1 ≤ end do (While the root has at least one child)
child := root * 2 + 1 (root*2+1 points to the left child)
(If the child has a sibling and the child's value is less than its sibling's)
if child < end and a[child] < a[child + 1] then
child := child + 1 ( then point to the right child instead)
if a[root] < a[child] then (out of max-heap order)
swap(a[root], a[child])
root := child (repeat to continue sifting down the child now)
else
return



heapify fonksiyonu alttan üste doğru bir yığın oluşturmak için kullanılırken yığın özelliği kazandırılmak için öğeler aşağıya doğru incelenir Aşağıda gösterilmiş bir diğer yol kullanılarak yığın üstten alta oluşturulup öğeler yukarı doğru incelenebilir Ancak aşağıdaki uygulama her ne kadar anlaşılması daha kolay olsa da daha yavaştır

function heapify(a,count) is
(end is assigned the index of the first (left) child of the root)
end := 1

while end < count
(sift up the node at index end to the proper place such that all nodes above
the end index are in heap order)
siftUp(a, 0, end)
end := end + 1
(after sifting up the last node all nodes are in heap order)

function siftUp(a, start, end) is
input: start represents the limit of how far up the heap to sift
end is the node to sift up
child := end
while child > start
parent := ⌊(child - 1) ÷ 2⌋
if a[parent] < a[child] then (out of max-heap order)
swap(a[parent], a[child])
child := parent (repeat to continue sifting up the parent now)
else
return