İçeriğe atla

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

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.

Diğer Sıralama Algoritmaları

Dış bağlantılar

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">PageRank</span>

PageRank, Google tarafından geliştirilen ve web sayfalarının önemini belirlemek için kullanılan bir algoritmadır. İnternet üzerindeki bağlantıların analiz edilmesiyle hesaplanan Pagerank değeri Google Arama sonuçlarında sayfaların sıralanması için kullanılan faktörlerden biridir.

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

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

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.

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.

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

İç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.