1. * 5651 Sayılı Kanun'a göre TÜM ÜYELERİMİZ yaptıkları paylaşımlardan sorumludur.
    * Telif hakkına konu olan eserlerin yasal olmayan şekilde paylaşıldığını ve yasal haklarının çiğnendiğini düşünen hak sahiplerinin İLETİŞİM bölümünden bize ulaşmaları durumunda ilgili şikayet incelenip gereği 1 (bir) hafta içinde gereği yapılacaktır.
    E-posta adresimiz

Sıralama Algoritmaları

Konusu 'BilgiBANK' forumundadır ve Suskun tarafından 28 Mart 2012 başlatılmıştır.

  1. Suskun

    Suskun V.I.P V.I.P

    Katılım:
    16 Mart 2009
    Mesajlar:
    23.242
    Beğenileri:
    276
    Ödül Puanları:
    6.230
    Yer:
    Türkiye
    Banka:
    2.052 ÇTL
    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ı

    [​IMG]
    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.


    [​IMG]
    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.

    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:

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

    Suskun V.I.P V.I.P

    Katılım:
    16 Mart 2009
    Mesajlar:
    23.242
    Beğenileri:
    276
    Ödül Puanları:
    6.230
    Yer:
    Türkiye
    Banka:
    2.052 ÇTL
    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



    Algoritmanın Java Uygulaması





    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:
    [​IMG]
    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






    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:

     
  3. Suskun

    Suskun V.I.P V.I.P

    Katılım:
    16 Mart 2009
    Mesajlar:
    23.242
    Beğenileri:
    276
    Ödül Puanları:
    6.230
    Yer:
    Türkiye
    Banka:
    2.052 ÇTL
    Hızlı sıralama



    [​IMG]
    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,[​IMG] karmaşıklığıyla, en kötü durumda ise [​IMG] 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



    Ü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
    Yani örnek şu şekle dönüşür : SORTIER L EISPIEB


    3 - Yukarıdaki algoritma göz önünde bulundurulursa;

    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)


    Eğer iki koşul da doğru ise ilk element(0) ile son element(E) yer değiştirilir. ( BERTIER L EISPIOS )


    Eğer iki koşul da doğru ise ilk element(R) ile son element(I) yer değiştirilir. ( BEITIER L EISPROS )


    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)

    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 )


    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)


    Eğer bir koşul yanlış ise soldaki element(E) sola yazılır , sağdaki element(E) sabit kalıyor ( BEIIIER L ETSPROS )

    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

    Eğer bir koşul yanlış ise soldaki element(R) sola yazılır , sağdaki element(E) sabit kalıyor ( BEIIIEE L RTSPROS )

    Aynı işlemleri sağdaki ve soldaki bölümlere ayrı ayrı yapılır.

    Sonuç şöyle :


    Sözde Kodu

    Algoritmanın yalın bir sözde kod olarak gösterimi aşağıdaki gibidir:

     
  4. Suskun

    Suskun V.I.P V.I.P

    Katılım:
    16 Mart 2009
    Mesajlar:
    23.242
    Beğenileri:
    276
    Ödül Puanları:
    6.230
    Yer:
    Türkiye
    Banka:
    2.052 ÇTL

    Kabarcık sıralaması

    [​IMG]
    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ığı [​IMG]'dir. Algoritma ortalama ve en kötü durumda [​IMG] 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:

    end procedure </gösterilebilir:

     
  5. Suskun

    Suskun V.I.P V.I.P

    Katılım:
    16 Mart 2009
    Mesajlar:
    23.242
    Beğenileri:
    276
    Ödül Puanları:
    6.230
    Yer:
    Türkiye
    Banka:
    2.052 ÇTL


    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ı



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

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

     
  6. Suskun

    Suskun V.I.P V.I.P

    Katılım:
    16 Mart 2009
    Mesajlar:
    23.242
    Beğenileri:
    276
    Ödül Puanları:
    6.230
    Yer:
    Türkiye
    Banka:
    2.052 ÇTL
    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:

     
  7. Suskun

    Suskun V.I.P V.I.P

    Katılım:
    16 Mart 2009
    Mesajlar:
    23.242
    Beğenileri:
    276
    Ödül Puanları:
    6.230
    Yer:
    Türkiye
    Banka:
    2.052 ÇTL
    Kova Sıralaması


    [​IMG]
    Elemanlar önce kovalar arasında dağıtılır
    [​IMG]
    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
     
  8. Suskun

    Suskun V.I.P V.I.P

    Katılım:
    16 Mart 2009
    Mesajlar:
    23.242
    Beğenileri:
    276
    Ödül Puanları:
    6.230
    Yer:
    Türkiye
    Banka:
    2.052 ÇTL

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

    Suskun V.I.P V.I.P

    Katılım:
    16 Mart 2009
    Mesajlar:
    23.242
    Beğenileri:
    276
    Ödül Puanları:
    6.230
    Yer:
    Türkiye
    Banka:
    2.052 ÇTL


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

    Suskun V.I.P V.I.P

    Katılım:
    16 Mart 2009
    Mesajlar:
    23.242
    Beğenileri:
    276
    Ödül Puanları:
    6.230
    Yer:
    Türkiye
    Banka:
    2.052 ÇTL


    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.
     

Sayfayı Paylaş