Algoritma GeliştirmeC++ programlama

Tarak Sıralama Algoritması(Comb Sort)

image_pdfimage_print

Comb Sort yani “Tarak Sıralaması” adından da anlaşılacağı gibi karşılaştırmalı bir sıralama algoritmasıdır. Aslına bakarsak kabarcık sıralaması ile hızlı sıralama karışımı diyebiliriz.Nisan 1991’de Stephen Lacey ve Richard Box tarafından duyurulmuştur. Tarak sıralaması tıpkı kendisi gibi karşılaştırmalı bir sıralama algoritması olan Kabarcık sıralamasından daha iyidir. Kabarcık sıralamasında sayılar bir yanındaki sayı ile karşılaştırılır ve ona göre yer değişimi yapılır.Karşılaştırma mesafesi 1’dir. Tarak sıralaması da aynı bu mantıkla çalışır ama yer değişimi yanındaki sayılar ile değilde daha uzaktaki sayılar ile yapılır.Bu uzaklık büyük bir sayı ile başlar ve her seferinde “shrink factor” dediğimiz 1.247330950103979 -çoğunlukla daha kolay olsun diye 1.3’e yuvarlanır- sayısı oranınca ta ki algoritma basitçe kabarcık sıralamadaki uzaklığa yani 1 olana kadar küçültülür. Tarak sıralamasının bu şekilde olmasının ana fikri ise listenin sonundaki küçük değerli öğeleri önce bularak listeden çıkarıp daha hızlı çalışmaktır. Kabarcık sıralamanın en büyük sorunu listenin sonunda olan küçük sayıları bulması için çok zaman harcamasıdır. Tarak sıralaması ile daha hızlı sonuç elde edilir.
Aşağıdaki gibi bir dizimiz olduğunu varsayalım ve küçükten büyüğe doğru sıralamaya çalışalım. İşte başlıyoruz…


İlk önce dizinin boyutunun “shrink factor” dediğimiz 1.247330950103979 sayısına bölünmesi gerekir biz yuvarlayıp 1.3 sayısına böleceğiz. Bölümün tam kısmını alırız. 5/1,3 = 3,8. Tam kısmı 3.
İlk elemanı seçeriz ve 3 fazlası olan eleman ile karşılaştırırız.

Sonra ikinci elemanı seçeriz ve +3 fazlası olan eleman ile karşılaştırırız.

Ardından üçüncü elemanı seçeriz. +3 fazlası dizinin uzunluğunu aştığı için işlem yapılamaz. Boşluk sayısını tekrar 1,3’e böler ve tam kısmını alırız. 3 / 1,3 = 2,3 Tam kısmı 2 olarak alırız. Birinci elemanı seçer ve +2 fazlası olan elemanla karşılaştırırız.

İkinci elemanı seçeriz ve +2 fazlası olan elemanla karşılaştırırız. Sonra diğer elemanları seçer +2 fazlası olan elemanlar ile dizinin sonuna kadar karşılaştırırız.

Dizinin sonuna geldiğimizde tekrar boşluk sayısını 1,3’e böleriz.. 2 / 1,3 = 1,5 tam kısmı alırız. 1. elemanı seçer ve 1 fazlası olan yani bir sonraki elemanla karşılaştırırız.Sonra ikinci elemanı sonraki elemanla. Diğer elemanları da bir sonraki elemanlarla karşılaştırırız.


Ve nihayetinde dizimiz sıralanmış olur.

Hazırlayan: Ömer Koyuncu

Kaynakça:

  1. http://www.ibasoglu.com/
  2. http://bilgisayarkavramlari.sadievrenseker.com/
  3. https://en.wikipedia.org/
0
0

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir