Sallayıcı Sıralaması (Shaker Sort)

Yazan : Şadi Evren ŞEKER

Veri sıralama için kullanılan ve kabarcık sıralamasının (bubble sort) neredeyse aynısı olan sıralama algoritmasıdır (sort algorithm). Kabarcık sıralamasından tek farkı, kabarcık sıralaması tek yönlü olarak kabarcığı hareket ettirirken, sallayıcı sıralaması bir sağdan bir soldan iki yönden de sıralamaktadır. Bu sebeple çift yönlü kabarcık sıralaması (bidirectional bubble sort) ismi de verilmektedir.

Algoritmanın çalışması kısaca aşağıdaki örnek üzerinde anlatılmıştır:

Sıralanacak olan sayılarımız

5,7,2,9,6,1,3

olarak verilmiş olsun. Bu sayıların üzerinden bir kere geçiyoruz ve geçerken aldığımız ikilileri küçük-büyük sırasına sokarak ilerliyoruz:

1. adım : 5,7,2,9,6,1,3
2. adım : 5,2,7,9,6,1,3
3. adım : 5,2,7,9,6,1,3
4. adım : 5,2,7,6,9,1,3
5. adım : 5,2,7,6,1,9,3
6. adım : 5,2,7,6,1,3,9

Yukarıdaki 5 adımlık birinci geçişin normal bir kabarcık sıralamasından farkı yoktur ve normalde kabarcık sıralamasında bu işlem devam ederek sıralama işlemi bitene kadar tekrarlanır. Ancak sallama sıralamasında ikinci geçişte tekrar dizinin en solundaki 5 sayısından başlamak yerine, dizinin sonundaki 9 sayısından başlanır be büyükten küçüğe sıralanır:

1. adım : 5,2,7,6,1,3,9
2. adım : 5,2,7,6,1,3,9
3. adım : 5,2,7,1,6,3,9
4. adım : 5,2,1,7,6,3,9
5. adım : 5,1,2,7,6,3,9
6. adım : 1,5,2,7,6,3,9

Yukarıdaki geçişe dikkat edilirse ilk geçişin tersine sondan başa doğru kabarcık hareket ettirilmiştir. Özünde kabarcık sıralaması gibi çalışan sallayıcı sıralama algoritması sırasıyla bir soldan bir sağdan sıralama işlemine devam etmekte ve hiç sayı değişmeyene kadar işlemi tekrarlamaktadır. Algoritmanın performansı O(n²) olarak kabarcık sıralaması ile aynıdır. Kodu aşağıdaki şekilde yazılabilir:

 do {
    exchange = 0;
    for(i = count - 1; i > 0; --i) {
      if(items[i - 1] > items[ i ]) {
        t = items[i - 1];
        items[i - 1] = items[ i ];
        items[ i ] = t;
        exchange = 1;
      }
    }

    for(i = 1; i < count; ++i) {
      if(items[i - 1] > items[ i ]) {
        t = items[i-1];
        items[i - 1] = items[ i ];
        items[ i ] = t;
        exchange = 1;
      }
    }
  } while(exchange);

/* değişim olmayana kadar devam et */

« Linear Programming (Doğrusal Programlama) | String Tokenizer ( Dizgi Parçalayıcı ) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Sallayıcı Sıralaması (Shaker Sort)' isimli yazı 18 Dec 2008 tarihinde, saat: 21:09 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 891 defa okunmuştur.

Benzer yazıları C/C++, algoritma analizi (teory of algorithms), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar