Sıralama Algoritmaları

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