Quick Sort Algoritması C Kodu
Quick Sort Algoritmasının C kodunu bir önceki algoritma dersinde anlattığımız gibi pivot elemanı baştaki eleman olarak seçerek yapacağız. C koduna geçmeden önce özet şeklinde Quick Sort algoritmasının nasıl çalıştığını bir hatırlayalım. Küçükten büyüğe sıralama yaptığımızı varsayalım.
— Dizinin başındaki elemanı pivot olarak seç.
— Pivot elemandan büyük olan elemanları pivotun sağ tarafına, küçük olan elemanlar ise pivotun sol tarafına yerleştiriyoruz.
— Pivot elemanın solunda kalan elemanlar ile sağında kalan elemanları 2 ayrı grup olarak ele alıp ilk iki adımı uyguluyoruz.
— Bu işlemleri pivot elemanların sağ ve sol tarafındaki elemanların sayısı 1′ den büyük olduğu sürece devam ettireceğiz ve en sonunda sıralı dizimizi elde etmiş olacağız.
Quick sort algoritmasının mantığı özet olarak bu şekildedir. Şimdi algoritmanın c kodunu paylaşalım ve daha sonrada kodun analizini yapalım.
Kaynak Kod:
#include
#include
void quickSort(int *,int, int);
int main(){
int *array,i,size;
printf("Dizinin boyutunu giriniz: "); scanf("%d",&size);
array=(int *)malloc(size*sizeof(int));
for(i=0;i
}
printf("Dizinin baslangic durumu: ");
for(i=0;i
}
quickSort(array,0,size-1);
printf("\n\nDizinin son durumu: ");
for(i=0;i
}
return 0;
}
void quickSort(int *array,int first,int last){
int i; // İlk elemanı tutacak sayaç değişkeni
int j; // Son elemanı tutacak sayaç değişkeni
int pivot; // Pivot elemanı tutacak sayaç değişkeni
int tmp; // Yer değiştirme işlemi için kullanılacak değişken
pivot=first; // Pivot ilk eleman seçilir
// Burada yapılan işlem son eleman ilk elemandan büyükse, son eleman ilk elemandan büyük olduğu sürece baştan ve sondan pivottan büyük olan ve
// pivottan küçük olan bir eleman seçilip yer değiştirilir.
if(last>first){
pivot=first;
i=first;
j=last;
while (ii){ // Baştan pivottan büyük olan bir eleman bulunur
i++;
}
while (array[j]>=array[pivot] && j>=first && j>=i){ // Sondan pivottan küçük olan bir eleman bulunur
j--;
}
if (j>i){ // Swap işlemi yapılır
tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
}
// Yeniden pivot seçilir ve bölünen bağlı listenin diğer parçaları tekrar quick sort fonksiyonuna gönderilir
tmp=array[j];
array[j]=array[pivot];
array[pivot]=tmp;
quickSort(array,first,j-1);
quickSort(array,j+1,last);
}
}
Kod Analiz:
— İlk olarak main fonksiyonumuzun içerisinde kullanıcıdan dizinin boyutunu ve dizinin elemanlarını alıp dizinin ilk durumunu ekrana yazdırdık.
— Daha sonra diziyi, ilk elemanı olan 0’ı ve dizinin boyutunun bir azını, burada C dilinde dizi indisleri 0’dan başladığı için böyledir, quickSort fonksiyonuna gönderdik.
— quickSort fonksiyonu içerisinde pivot elemanı ilk eleman olarak seçiyoruz ve daha sonra dizinin ilk elemanının indisi son elemanının indisinden büyükse, yani az önce fonksiyona gönderdiğimiz iki sayı, aşağıdaki işlemleri gerçekleştiriyoruz. Eğer değilse fonksiyon sonlanır.
— i ve j gibi iki sayaç değişkenine dizinin ilk ve son elemanlarının indislerini atadık ve j sayısı i sayısından büyük olduğu sürece aşağıdaki işlemleri yaptık.
— Pivot eleman i. indisteki elemandan büyük olduğu sürece i sayısını arttırdık ve pivot eleman j. indisteki elemandan küçük olduğu sürece j sayısını azalttık. Burada yapılmak istenen, dizinin başından pivottan büyük olan ilk eleman ile dizinin sonundan pivottan küçük olan ilk elemanı bulu yerlerini değiştirmektir. Hatırlayın pivottan küçükleri sola büyükleri sağa alacaktık.
— Daha sonra j sayısı, i sayısından büyükse i. ve j. indisteki elemanları yer değiştiriyoruz. Bu demek oluyorki yukarıdaki işlem başarıyla tamamlanmış ve baştan pivottan küçük bir eleman bulunmuş ve sondanda pivottan küçük bir eleman bulunmuş.
— Bu işlemler j sayısı i sayısından büyük olduğu sürece devam ettikten sonra while sonlanır ve j. indisteki eleman ile pivot eleman yer değiştirilir. Yani pivot kenidisinden büyük ve küçük sayıların ortasına alınır.
— Son olarak ise pivot sağ ve sol tarafında kalan elemanlar tekrar quickSort fonksiyonuna gönderilir ve aynı işlemler tekrarlanır. Bu şekilde sıralı diziyi elde ederiz.
Gördüğümüz gibi Quick Sort algoritmasının C dilinde kodlanması son derece basit. Yaklaşık yorum satırları da dahil 30 satırda algoritmayı kodladık. Şimdi de programımızın çalışır durumdaki ekran görüntülerine 2 örnek için bir göz atalım.
Ekran Görüntüleri:
Kaynak
