İçeriğe atla

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:

  1. 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.
  2. Sıralanacak dizinin üzerinden geçerek bütün öğeleri ilgili güvercin yuvasına yerleştir.
  3. 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[i]] := b[a[i]]+1

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

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Birleştirmeli sıralama</span>

Birleşmeli Sıralama, bilgisayar bilimlerinde derecesinde karmaşıklığa sahip bir sıralama algoritmasıdır. Girdi olarak aldığı diziyi en küçük hale gelene kadar ikili gruplara böler ve karşılaştırma yöntemi kullanarak diziyi sıralar.

<span class="mw-page-title-main">Sıralama algoritması</span>

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.

<span class="mw-page-title-main">Seçmeli sıralama</span>

Seçmeli Sıralama, bilgisayar bilimlerinde kullanılan 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.

<span class="mw-page-title-main">Hızlı sıralama</span>

Hızlı sıralama, 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.

<span class="mw-page-title-main">Yığın sıralaması</span>

Yığın Sıralaması, 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.

<span class="mw-page-title-main">Eklemeli sıralama</span> sıralama algoritma

Eklemeli Sıralama, 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:

Cüce sıralaması, 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.

<span class="mw-page-title-main">Kabarcık sıralaması</span>

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.

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üphane 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.
<span class="mw-page-title-main">Kova sıralaması</span>

Kova Sıralaması, sıralanacak bir diziyi parçalara ayırarak sınırlı sayıdaki kovalara 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.

<span class="mw-page-title-main">Kabuk sıralaması</span>

Shell sıralaması, 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:

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.

Rahat Sıralama (İngilizcesi: Smoothsort) bilgisayar bilimlerinde kullanılan yığın sıralaması algoritmasının türevi olan bir sıralama algoritmasıdır. 1981 yılında Edsger Dijkstra tarafından geliştirilmiştir. Yığın sıralamasına benzer biçimde rahat sıralamanın en kötü durumdaki karmaşıklığı O(n log n)'dir. Rahat sıralamanın yığın sıralamasına göre üstünlüğü ise başlangıçta neredeyse sıralı olan bir diziyi sıralarken karmaşıklığının O(n) düzeyine inmesidir. Uygulamasındaki karmaşıklığı nedeniyle rahat sıralama çok nadiren kullanılır.

Tarak 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.

Bilgisayar bilimlerinde değişik amaçlarla pek çok algoritma kullanılır. Aşağıda Vikipedi'de bulunan algoritmaların listesi verilmiştir.

İplik sıralaması bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Sıralanacak olan dizinin, sıralanmış alt dizilerinin oluşturularak bu alt dizilerin birleştirilmesi yoluyla sonucun oluşturulması mantığına dayanır. Algoritmanın her bir aşamasında ana dizinin üzerinden geçilir ve bu diziden zaten sıralanmış olan bir dizi eleman çıkarılır. Çıkarılan bu eleman dizileri daha sonra birleştirilir.

Saçma sıralama veya rastgele sıralama, bilgisayar bilimlerinde yalnızca eğitim amaçlı olarak kullanılan verimsiz bir sıralama algoritması. 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.

İçgözlemle sıralama 1997 yılında David Musser tarafından tasarlanmış bir sıralama algoritmasıdır. Algoritma verilen bir diziyi sıralamaya hızlı sıralama algoritmasıyla başlar ancak özyineleme derinliği önceden belirlenen bir değeri aştığında yığın sıralamasına döner. İki algoritmanın iyi yönlerini birleştiren içgözlemle sıralama algoritmasının karmaşıklığı en kötü durumda O(n log n)'dir. Olağan veri yükleri üzerinde kullanıldığında başarımı hızlı sıralamanın başarımına yakındır. Kullandığı iki algoritma karşılaştırma ile sıraladığından içgözlemle sıralama da karşılaştırma ile sıralayan bir algoritma olarak sınıflandırılır.

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 ögelerin sayısını gösterir. Yeni dizideki öge 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.

<span class="mw-page-title-main">Basamağa göre sıralama</span> bilgisayar bilimlerinde sayıları basamaklarının üzerinde işlem yaparak sıralayan bir algoritma

Basamağa göre sıralama 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.