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 */