Sıralama Algoritmaları

Suskun · 28 Mrt 2012

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.

Suskun · 28 Mrt 2012

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[0..size-1]) {
i := 1
j := 2
while i < size - 1
if a[i-1] >= a
i := j
j := j + 1
else
swap a[i-1] and a
i := i - 1
if i = 0
i := 1
}

Algoritmanın Java Uygulaması

void gnomeSort(int a[]) {
int i = 1;
int j = 2;
while (i < a.length - 1) {
if (a[i - 1] >= a) {
i = j;
j++;
}
else {
int temp = a;
a = a[i - 1];
a[i - 1] = temp;
i--;
if (i == 0) {
i = 1;
}
}
}

Genişletmek için tıklayın...

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
j = i-1
while j >= 0 and A[j] > value
A[j + 1] = A[j]
j = j-1
A[j+1] = value

Genişletmek için tıklayın...

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 [0...length(a)-1]
b[a] := b[a]+1

(* copy the results back to a *)
j := 0
for i in [0...length(b)-1]
repeat b times
a[j] := i
j := j+1

Genişletmek için tıklayın...

Suskun · 28 Mrt 2012

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

Suskun · 28 Mrt 2012

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 ) \to ( 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 ) \to ( 1 4 5 2 8 )
( 1 4 5 2 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 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 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 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 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 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

Suskun · 28 Mrt 2012

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 erengencturk.net
*/

#include <stdio.h>

#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:\n");
for(i=0;i<ELEMENTS;i++)
printf("%d ",X);

shellsort(X,ELEMENTS);
printf("\nSORTED ARRAY\n");
for(i=0;i<ELEMENTS;i++)
printf("%d ",X);

}

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

public static void shellSort(int[] a) {
for (int increment = a.length / 2; increment > 0;
increment = (increment == 2 ? 1 : (int) Math.round(increment / 2.2))) {
for (int i = increment; i < a.length; i++) {
int temp = a;
for (int j = i; j >= increment && a[j - increment] > temp; j -= increment){
a[j] = a[j - increment];
a[j - increment] = temp;
}
}
}
}

Genişletmek için tıklayın...

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

Genişletmek için tıklayın...

Suskun · 28 Mrt 2012

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

Suskun · 28 Mrt 2012

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 into buckets[msbits(array, k)]
for i = 0 to n - 1 do
next-sort(buckets)
return the concatenation of buckets[0], ..., buckets[n-1]

Suskun · 28 Mrt 2012

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.

Suskun · 28 Mrt 2012

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.

Suskun · 28 Mrt 2012

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.

Sıralama Algoritmaları

Suskun

V.I.P

Suskun

V.I.P

Suskun

V.I.P

Suskun

V.I.P

Suskun

V.I.P

Suskun

V.I.P

Suskun

V.I.P

Suskun

V.I.P

Suskun

V.I.P

Suskun

V.I.P

Benzer konular