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ı 
 Hızlı Sıralama
 Birleştirmeli Sıralama
 Seçmeli Sıralama
 Kokteyl Sıralaması
 Tarak Sıralaması
 Yığın Sıralaması
 Eklemeli Sıralama
 Kabuk Sıralaması

 Dış bağlantılar 
 Citeseer sayfasında algoritmayı anlatan ilk yayın
 xxx.lanl.gov E-Print arşivinden erişilen kütüphane algoritması yayını kütüphane algoritmasını anlatıp karmaşıklığını inceleyen bir sayfa.

Kategori:Sıralama algoritmaları