webmaster
 
Konu Kilitli
28-12-2011 00:29:28
 

Quicksort (Hızlı Sıralama) Sıralama Yöntemi

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 +++++++++leri ile ilgili bilgi için Sefer Algan’ın Fonksiyon +++++++++leri ve Uygulamaları makalesini okuyabilirsiniz). Karşılaştırma fonksiyonumuz sıralanmasını istediğimiz dizi ile aynı türden iki +++++++++yi 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 +++++++++ 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.

Bir önceki yazı Hata Tespiti ve Çözümlenmesi hakkında bilgi vermektedir.

Konu Kilitli

"Quicksort (Hızlı Sıralama) Sıralama Yöntemi" konusu hakkında etiketler
addi adlarina algoritma algoritmalari algoritmasi algoritmasini arasindaki ayirma basic bir boyutlu cagirma degisikligi dizi dizilerde dizilerinde dizilerle dizinin durum eger farklar fonksiyon fonksiyonu gelistirilmis gelistirme gore hangi heap hizli ile insert insertion ise isim islemi iyi kabarcik karisiklik karsilastirmalar klasik kullanacagimiz kullanarak kullanildigi kullaniyoruz kumelere listesi mantigi merge metodu nasil neden nedir negatif neye ogrenci ogrencileri olmus olur ornek ornekler program programi programlama python qsort qui quick quicksort quik sayi sayilar sayisi seceriz secmeli siralam siralama siralamasi siralamayi siralanabilir siralanmasi sirasinda sort sorting struct swap tek temel temelleri tersten uygulama uzerinde veri yan yana yapan yaparken yapilari yapilir yazimi yer yerler yontemi yontemleri

Hata Tespiti ve Çözümlenmesi Önceki | Sonraki Bağlı Listeler ve Uygulamaları - 2




Saat: 18:06 - Webmaster Forumu - Rss - Arşiv
İletişim Bilgileri, Contact Us, Kullanım Sözleşmesi, Gizlilik