C#nedir?com
 
YAZAR HAKKINDA
Oğuz Yağmur
Oğuz Yağmur
http://www.oguzyagmur.com
İletişme geçmek için tıklayın.
26 Makalesi yayınlanmakta.
Yazar hakkında detaylı bilgi için tıklayın.
Yayınlanan diğer makaleleri için tıklayın.
İlgili etiketler: degeri dikkat dizideki dizinin durumlar eleman elemanin ikinci islemleri karsilastirma karsilastirmak parametre siralama siralanacak verilerin C / Sys Prog. Oğuz Yağmur
 
YAZI HAKKINDA
Türü : Makale
Serbest Köşede C#nedir?com üyelerinin hazırladıkları yazılar yayınlanır. Bu yazılar editör incelemesine girmeden yayınlanır.
Seviyesi : Orta
Kategori : C / Sys Prog.
Yayınlanma Tarihi : 9.12.2006
Okunma Sayısı : 37382
Yorum Sayısı : 0     yorum yaz
Site İçi AramaSİTE İÇİ ARAMA
Üye Girişini AçÜye GİRİŞİ
Üye girişi için tıklayın.
Kullanıcı Adı
Şifre
 
Beni her zaman hatırla
Bir hafta boyunca kullanıcı bilgilerinizi kullanıcı çıkışı yapana kadar hatırlar. (Paylaşılan bilgisayarlarda önerilmez.)
 
Şifremi / Kullanıcı Adımı unuttum.
 
.net TV RSS Serbest KÖŞE (?)
Serbest Köşede C#nedir?com üyelerinin hazırladıkları yazılar yayınlanır. Bu yazılar editör incelemesine girmeden yayınlanır.
emre TAŞ
XML - Deniz Kılınç
emre TAŞ
yazının devamı >
emre TAŞ
Decompiling and Reverse Engineering .Net Radyo
emre TAŞ
yazının devamı >
emre TAŞ
Masaüstü mü ? İnternet Mi? .Net Radyo
emre TAŞ
yazının devamı >
emre TAŞ
.Net Kavramları - .Net Radyo
emre TAŞ
yazının devamı >
emre TAŞ
Yeni Başlayanlar için - .Net Radyo
emre TAŞ
yazının devamı >
Makale Gönder Bende Yazmak İstiyorum
.net TV RSSBlogroll
Burak Selim Şenyurt
Asp.Net Core'da Bir WebSocket Macerası 24.10.2017
Burak Selim Şenyurt
.NET Core 2.0 ile Basit Bir Web API Geliştirmek 24.10.2017
Turhal Temizer 'in Blogu
ChatBot UI Sample 24.10.2017
Turhal Temizer 'in Blogu
C# – IRR Function 24.10.2017
  Diğer Herşey
Sponsorlar
BT Akademi
Medya Portakal
Video Hosting Sponsoru
Csharpnedir.com bir Ineta üyesidir
Uzman Abi
Her Yönüyle C# - Sefer Algan
Quicksort (Hızlı Sıralama) Sıralama Yöntemi
 
Kapat
Sayfayı Yazdır Sık Kullanılanlara Ekle Arkadaşıma Gönder MySpace Del.Ico.Us Digg Facebook Google Mixx Reddit StumbleUpon
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
  • Yazılan Yorumlar
  • Yorum Yaz
Bu konu hakkında yayınlanan yorum bulunmamaktadır.
"Yorum Yaz" tabını kullanarak sizde yorumlarınızı yazabilirsiniz.
Yorum yazabilmek için üye girişi yapmalısınız. Üye girişi için tıklayın.
Üye değilseniz Üyel Ol linkine tıklayarak üyeliğinizi hemen başlatabilirisniz.
 
  • Bu Konuda Son 10
  • Eklenen Son 10
  • Bu Konuda Geçmiş 10
Bu Konuda Yazılmış Yazılmış 10 Makale Yükleniyor
Son Eklenen 10 Makale Yükleniyor
Bu Konuda Yazılmış Geçmiş Makaleler Yükleniyor