Sıralama işlemleri programlama yaparken ya da algoritma geliştirirken
elimizdeki verilerilerin sıralanması ve gerekli olduğunda bir veriyi arayıp
bulmak temel görevlerimizin başında gelir. Bu işlemler birçok uygulamada
kullanılmasının yanı sıra, derleyicilerde, yorumlayılarda, database yönetim
sistemlerinde, işletim sistemlerinin temel işlevlerinde sıklıkla
kullanılmaktadır. Sıralanmış veriler üzerinde arama işlemlerimiz çok daha kolay
olacağı için önce verilerimizi sıralamalı daha sonra arama işlemlerimizi bu
sıralı veriler üzerinde gerçekleştirerek daha hızlı ve etkin çözüm
üretebiliriz.
Sıralama, elde bulunan benzer verilerin belirlenmiş bir yöntem
ile artan veya azalan şekilde düzenlenmesi veya düzenleme sürecidir
diyebiliriz. Sıralama işlemi için seçtiğimiz yöntemler birbirine göre
farklılıklar gösterir. Mesela bir sıralama yöntemi genel olarak iyi olabilir
ama bazı durumlarda başka bir yöntem bundan daha iyi olabilmektedir. Bu nedenle
de bir sıralama yöntemi her zaman mükemmel bir çözüm olmayabilir. Örneğin,
verilerimiz disk üzerinde bulunuyor olsun ve bu verilerimizi sıraladığımzı
düşünelim. Kullanacağımız sıralama yönteminde dikkat etmemiz gereken en önemli
unsur, yöntemin verileri çok sık yer değiştirmemesi olacaktır. Nitekim disk
üzerinde verilerin yerini değiştirmek belleğe göre daha yavaş olacak ve
verilere erişmek daha uzun zaman alacaktır.Bellek üzerinde yapılacak sıralama
yönteminin seçiminde dikkat edilecek unsur ise yöntemin az bellek bölgesi
kullanmasıdır. Eğer uygulamamız kısıtlı belleğe sahip bir ortamda çalışacak ise
bu unsur daha da önemli olacaktır. Bu nedenle bir programcı sıralama
yöntemlerini iyi bilerek hangi durumlarda hangi yöntemi seçeceğini iyi
belirlemelidir. Şimdi seçecegimiz yöntemi belirlerken nelere dikkat
edeceklerimize değinelim.
Sıralama işlemlerinde hız, üzerinde işlem yapılacak verilerin birbirleri ile
karşılaştırılma sayısı ve işlem sırasında bu verilerin yer değiştrilme sayısına
bağlı olarak artar ya da azalır. Tabiki veriler arasındaki yer değiştirme
işlemleri, karşılaştırma işlemlerinde daha fazla zaman alacaktır. Bu durumda
seçeceğimiz yöntemin ortalama olarak verileri ne kadar hızlı sıraladığı bizim
için önemlidir. Diğer bir dikkat etmemiz gereken nokta ise sıralama işleminde
hangi durumlar ile karşılacağımızı belirleyerek en iyi ve en kötü durumlar ile
hangi sıklıkla karşılaşacağımızı daha önceden hesaplayabilmeliyiz. Çünkü bir
sıralama yöntemi normal durumlar için iyi ama kötü durumlar için vasat bir
performans gösterecektir. Sıralanacak verimizin durumuna göre yöntemin
davranışı diğer bir husustur. Elimizde sıralı bir veri olduğunda seçeceğimiz
yöntem en az, tersten sıralı ise en çok, orta bir karışıklığa sahip ise
ortalama seviyede çalışması doğru yöntemin seçilmesinde etken olacaktır.
Sefer Algan’ın
Klasik Sıralama algoritmaları isimli makalesinde sıralama algoritmaları
incelenmişti. Bu makalede C dünyasında sıklıkla kullanılan ama her zaman tercih
edilmemesi gereken Quick sort (hızlı sıralama) sıralama yöntemini
inceleyeceğiz. C.A.R Hoare tarafından bulunan ve adlarılan Quick sort, bilinen
birçok genel amaçlı sıralama yönteminden (Buble sort, selection sort, insertion
sort) daha iyidir. Quick sort böl ve yönet mantığına dayanmaktadır.
İşleyiş, önce veri kümesinden, diğer değerlerle karşılaştırmak için bir değer
seçmek (buna comparand denir ) ve diziyi ikiye bölme şeklindedir. Bölme işlemi,
seçtiğimiz değerden - ki bu değer genellikle dizinin ortasındaki eleman olarak
seçilir. Eğer seçilemiyorsa ilk elemanı seçebiliriz ve bu şekilde de yöntem
doğru bir şekilde çalışır - küçük olanlar sol tarafa, büyük olanlar ise sağ
tara yerleştirilerek yapılır. Sağ ve sol alt veri kümelerine tekrar aynı
işlemler yapılarak verileri sıralarız. Burdan da Quick sort yönteminin kendi
kendini çağıran (recursive) bir fonksiyon ile oluşturulacağını anlayabiliriz.
Diyelim ki elimizde A={12,3,7,6,4,8,2} şeklinde bir dizi var. 6 yi diğer
elemanlar ile karşılaştırmak için seçelim. 6 dan küçük olanlar sol tarafa büyük
olanlar ise sağ tarafa gelecek şekilde iki altküme oluşturursak; Asol = {3,4,2}
ve Asağ = {12,7,8} altkümelerini elde ederiz. Şimdi Quick sort yöntemini bu iki
altküme üzerinde uygulayacağız. Bu yöntem artık hiçbir altküme oluşamayacak
duruma gelinceye kadar devam eder. Bu anlattıklarımız koda dönüştürecek
olursak, sıralamayı gerçekleştirecek fonksiyonumuz üç adet parametre alacaktır.
ilk parametre sıralanacak dizinin adresi, ikinci parametre sıralanacak dizinin
soldan ilk elemanının indeksi, üçüncü parametre ise dizinin sağdan son elemanın
indeksidir. Elimizde sınıfımızdaki öğrencilerin isimlerinin listesi olsun ve bu
isimleri sıralayan fonksiyonu yazalım :
void quicksort_names_list(char names[][30], int idxleft,
int idxright)
{
int left, right;
char *medium_item, temp[30];
left = idxleft , right = idxright;
medium_item = names[(left + right) / 2];
do { /*Alt kümelere ayırma
işlemleri*/
while ((strcmp(names[left],
medium_item) < 0) && (left < idxright))/*soldaki
küçük eleman*/
++left;
while((strcmp(names[right],
medium_item) > 0) && (right > idxleft))/*Sağdaki
küçük eleman*/
--right;
if (left <= right) {
/*Yer değiştirme işlemi*/
strcpy(temp,
names[left]);
strcpy(names[left], names[right]);
strcpy(names[right],
temp);
++left;
--right;
}
}while(left <= right);
if (idxleft < right)
quicksort_names_list(names, idxleft,
right);/*Sol alt küme için Quick sort işlemi*/
if (idxright > left)
quicksort_names_list(names, left,
idxright);/*Sağ alt küme için Quick sort işlemi*/
}
Fonksiyon ilk çağırımda (eğer dizinin tamamı sıralanmak isteniyor
ise) idxleft değeri 0, idxright değeri ise dizinin eleman sayısından 1 eksik
yani n elemanlı bir dizi için n - 1 değerini alacaktır. Dizideki değerleri bir
değer ile karşılaştırmak için diziden bir elaman seçmemiz gerekli
ve bunu da dizinin ortasındaki eleman olması sağlıyoruz (medium
item). İçteki birinci while döngüsü ile medium_item den küçük ilk
değeri, ikinci while ile de medium_item den büyük ilk değeri
buluyoruz. Daha sonra bulduğumuz bu değerlerin yerini değiştiriyoruz(swap).Alt
kümelere ayırma işlemleri bittikten sonra kendi kendini çağırma yöntemi ile
eğer sol ve sağ tarafta birden çok eleman varsa bu alt kümeler sıralama
işlemine tabi tutulacaktır.
Dizilerin yanı sıra, bilgilerimiz(struct) bir yapıda da tutuluyor olabilir.
Yani bir nesneye ait bilgiler birden fazla olabilir. O zaman bu sıralama
işlemlerini nasıl yapacağız? Bildiğimiz gibi yapılarda genellikle birden fazla
üye eleman bulunur. Sıralama işlemini gerçekleştirmek için bu elemanlardan bir
tanesi karşılaştırmak için temel alınır. Örneğin öğrenci bilgilerinin tutan
yapılardan oluşmuş bir listemizin olduğunu düşünelim. Öğrenci yapımızı basit
olarak tanımlayalım :
typedef struct _Student{
char name[30];
int no;
}STUDENT;
Bu yapıyı tahmin edebileceğiniz gibi iki şekilde sıralaya
biliriz. Öğrenci isimlerine göre sıralama ya da öğrenci numaralarına göre
sıralama yapabiliriz. Her iki sıralama içinde ayrı fonksiyonlar yazmak gerekir.
Bir önceki örneğimizde karekter dizileri üzerinde işlem yapan fonksiyonu
hazırlamıştık. Şimdi de int türünden değerler için sıralama yapan sıralama
yapacak fonksiyonunu hazırlayalım :
void quicksort_students_list(STUDENT students[], int
idxleft, int idxright)
{
int left, right;
int medium_item, temp;
left = idxleft , right = idxright;
medium_item = students[(left + right) / 2].no;
do {
while ((students[left].no <
medium_item)) && (left < idxright))
++left;
while((students[right].no >
medium_item)) && (right > idxleft))
--right;
if (left <=
right) {
temp
= students[left].no;
students[left].no = students[right].no;
students[right].no = temp;
++left;
--right;
}
}while(left <= right);
if (idxleft < right)
quicksort_students_list(students,
idxleft, right);
if (idxright > left)
quicksort_students_list(students,
left, idxright);
}
Görüldüğü gibi yöntemde bir değişiklik olamamasına karşın
paramterede farklılık olmuştur.İlk parametre STUDENT yapısı türünden bir dizi
almıştır. Karşılaştırma anahtarı olarak dizideki herbir elemanın no üyesinden
faydalandık. Eğer öğrenci türünden elemanlardan oluşan dizinin isimlere göre
sıralanmasını istiyorsak fonksiyonumuzu yeniden yazmamız ve karekter dizilerine
göre uygun işlemleri yapmamız gerekirdi. Peki ne yapmalıyız ki türden bağımsız
sıralama işlemlerini gerçekleştirebilmeliyiz. Yani öyle bir fonksiyon olmakı ki
yapı türünden, karekter dizisi türünden ya da int türünden diziler verdiğimizde
sıralama işlemini gerçekleştirsin. C’nin standart kütüphanesinde bulunan qsort
fonksiyonu ile bu işlemleri rahatlıkla gereçekleştirebiliriz. Fonksiyonun
prototipi :
void qsort(void *, size_t, size_t, int (*)(const void *,
const void *))
şeklindedir. Fonskiyonun ilk parametresi sıralanmasını
istediğimiz dizinin başlangıç adresi, ikinci paremetre dizinin toplam uzunluğu,
üçüncü parametre dizideki bir elemanın uzunluğu, son parametre ise
karşılaştırmak için kullanacağımız fonksiyonun adresidir (Fonksiyon
göstericileri ile ilgili bilgi için Sefer Algan’ın
Fonksiyon Göstericileri ve Uygulamaları makalesini okuyabilirsiniz).
Karşılaştırma fonksiyonumuz sıralanmasını istediğimiz dizi ile aynı türden iki
göstericiyi parametre olarak almalıdır. Geri dönüş değeri int olmak zorundadır.
Eğer ilk eleman ikinci elemandan büyük ise pozitif herhangi bir değerle, ikici
eleman birinci elamandan büyükse negatif herhangi bir değerle, eğer elemanlar
eşit ise 0 ile geri dönecek şekilde tasarlanmalıdır. Şimdi qsort fonksiyonu ile
yapıları nasıl sıraya dizeceğimizi örnek ile görelim. İlk önce karşılaştırma
fonksiyonumuzu yazalım. Fonksiyon diziyi öğrencilerin nosuna göre sıralasın :
int compare_students(const STUDENT *s1, const STUDENT
*s2)
{
if (s1->no > s2->no)
return 1;
if (s1->no < s2->no)
return -1;
return 0;
}
Fonksiyonumuz daha öncede belirtildiği gibi sıralanacak dizi
türünden iki gösterici almıştır. Geri dönüş değeri int türünden olup, eğer ilk
eleman büyük ise 1 ile, ikinci eleman büyük ise -1, elemanlar eşit ise 0 ile
fonksiyonumuzu sonlandırıyoruz. Eğer isme göre sıralama yapmak isteydik tek bir
satır işimizi görecekti (return srtcmp(s1->name, s2->name) ) .Şimdi
qsort fonksiyonunu nasıl kullanacağımıza bakalım :
{
STUDENT students [] = { {"Hipopotam",12},{"Kedi",11},
{"Esek",1},{"Zurafa",4}};
int i;
qsort(students, 4, sizeof(STUDENT), compare_students);
for(i = 0; i < 4; ++i)
printf("%s\t%d\n", students[i].name,
students[i].no);
}
İlk adımda dört elemanlı öğrenci dizimizi oluşturuyoruz. qsort
fonksiyonunu kullanırken ilk parametreye dizinin başlangıç adresini
geçiriyoruz. İkinci parametre dizinin toplam uzunluğu olması gerektiğinden
dizimiz dört elemanlı olduğundan 4 değerini geçiriyoruz. Üçüncü parametre
dizideki bir elemanın uzunluğu olması gerektiğinden sizeof ile dizideki bir
elemanın uzunluğunu alıp fonksiyona geçiriyoruz. Son parametre de karşılaştırma
foksiyonunun adresi olması gerektiğinden, hazırladığımız compare_students
fonksiyonun adresini fonksiyonun son parametresi olarak kullanıyoruz. Son
adımda sıralanmış diziyi ekrana yazdırıyoruz.
Verileri sıralarken hızın çok önemli bir etken olduğu zamanlarda sıralama
yöntemlerinin önemi bir kez daha karşımıza çıkmaktadır. İyi bir programcı
çalıştığı ortamların durumunu göz önüne alarak hangi yöntemin daha performaslı
olacağını belirleyebilmelidir. Quicksort genel olarak iyi bir performas
sergilese dahi her durumda mükemmel bir çözüm olamayabilir. Özellikle küçük
boyutlu dizilerde kabarcık sıralama yönteminin bile Quick sort yöntemini geride
bırakabileceğini görebiliriz. Bu yüzden hangi herhangi bir yöntemi kullanmadan
önce yöntemin artı ve eksi yönlerini inceleyerek en iyi yöntemi bulmaya
çalışabilmeliyiz.
Mutlu ve sağlıklı günler.
Yazıda geçen örnek kodları buradan indirebilirsiniz.
Makale:
Quicksort (Hızlı Sıralama) Sıralama Yöntemi C ve Sistem Programlama Oğuz Yağmur
|