Quick Sort - Hızlı Sıralama Algoritması
Elinizdeki verilerin küçükten büyüğe doğru sıralanması gerekiyorsa, bunu çeşitli yollardan yapabilirsiniz.
Sayıların dağılımına göre sizin hızını değiştirecek algoritma çeşitlerine Merge Sort, Selection Sort, Insertion Sort, Bubble Sort gibi algoritmalar örnek verilebilir. Detaylı bilgi için : Sıralama Algoritmaları
Elinizde bir dizi halinde bulunan sayılar yada ASCII'de tanımlı char karakterler sizin girdiniz olabilir. Quick Sort, mantıksal olarak alt kümeler yaratıp alt kümeleri kendi aralarında sıralar ve bir üst kümeye geçtiğinde bunu tekrarlar. Üst küme olarak evrensel kümeye ulaştığınızda tüm sayılarınız sıralanmış olur.
Hızlı sıralama algoritması, sıralanacak bir sayı dizisini daha küçük iki parçaya ayırıp oluşan bu küçük parçaların kendi içinde sıralanması mantığıyla çalışır.
Algoritmanın adımları aşağıdaki gibidir:
Sayı dizisinden herhangi bir sayıyı pivot eleman olarak seç.
Sayı dizisini pivottan küçük olan tüm sayılar pivotun önüne, pivottan büyük olan tüm sayılar pivotun arkasına gelecek biçimde düzenle (pivota eşit olan sayılar her iki yana da geçebilir). Bu bölümlendirme işleminden sonra eleman sıralanmış son dizide olması gerektiği yere gelir. Algoritmanın bu aşamasına bölümlendirme aşaması denir.
Pivotun sol ve sağ yanında olmak üzere oluşan iki ayrı küçük sayı dizisi, hızlı sıralama algoritması bu küçük parçalar üzerinde yeniden özyineli olarak çağrılarak sıralanır.
Algoritma içinde sayı kalmayan (eleman sayısı sıfır olan) bir alt diziye ulaştığında bu dizinin sıralı olduğunu varsayar.
Aşağıdaki kod, quicksort'un pointerlar yardımıyla en kısa gösterimlerinden biridir. Kodu inceleyebilirsiniz.
Sayıların dağılımına göre sizin hızını değiştirecek algoritma çeşitlerine Merge Sort, Selection Sort, Insertion Sort, Bubble Sort gibi algoritmalar örnek verilebilir. Detaylı bilgi için : Sıralama Algoritmaları
Elinizde bir dizi halinde bulunan sayılar yada ASCII'de tanımlı char karakterler sizin girdiniz olabilir. Quick Sort, mantıksal olarak alt kümeler yaratıp alt kümeleri kendi aralarında sıralar ve bir üst kümeye geçtiğinde bunu tekrarlar. Üst küme olarak evrensel kümeye ulaştığınızda tüm sayılarınız sıralanmış olur.
Hızlı sıralama algoritması, sıralanacak bir sayı dizisini daha küçük iki parçaya ayırıp oluşan bu küçük parçaların kendi içinde sıralanması mantığıyla çalışır.
Algoritmanın adımları aşağıdaki gibidir:
Sayı dizisinden herhangi bir sayıyı pivot eleman olarak seç.
Sayı dizisini pivottan küçük olan tüm sayılar pivotun önüne, pivottan büyük olan tüm sayılar pivotun arkasına gelecek biçimde düzenle (pivota eşit olan sayılar her iki yana da geçebilir). Bu bölümlendirme işleminden sonra eleman sıralanmış son dizide olması gerektiği yere gelir. Algoritmanın bu aşamasına bölümlendirme aşaması denir.
Pivotun sol ve sağ yanında olmak üzere oluşan iki ayrı küçük sayı dizisi, hızlı sıralama algoritması bu küçük parçalar üzerinde yeniden özyineli olarak çağrılarak sıralanır.
Algoritma içinde sayı kalmayan (eleman sayısı sıfır olan) bir alt diziye ulaştığında bu dizinin sıralı olduğunu varsayar.
Aşağıdaki kod, quicksort'un pointerlar yardımıyla en kısa gösterimlerinden biridir. Kodu inceleyebilirsiniz.
Kaynak Kodu :
//C++ Programming Language
// zafercavdar
#include <stdio.h>
#include <stdlib.h>
int N,A[50];
void oku()
{
FILE *inp=fopen("qsort.in","r");
fscanf(inp," %d",&N);
for(int i=0;i<N;i++)
fscanf(inp," %d",&A[i]);
fclose(inp);
}
int COMP(const void *pa,const void *pb)
{
int *a=(int *)pa;
int *b=(int *)pb;
if(*a<*b)
return -1;
return 1;
}
void sirala()
{
qsort(A,N,sizeof(int),COMP);
}
void yaz()
{
for(int i=0;i<N;i++)
printf("%d- %d\n",i+1,A[i]);
getchar();
}
int main()
{
oku();
sirala();
yaz();
return 0;
}
// zafercavdar
#include <stdio.h>
#include <stdlib.h>
int N,A[50];
void oku()
{
FILE *inp=fopen("qsort.in","r");
fscanf(inp," %d",&N);
for(int i=0;i<N;i++)
fscanf(inp," %d",&A[i]);
fclose(inp);
}
int COMP(const void *pa,const void *pb)
{
int *a=(int *)pa;
int *b=(int *)pb;
if(*a<*b)
return -1;
return 1;
}
void sirala()
{
qsort(A,N,sizeof(int),COMP);
}
void yaz()
{
for(int i=0;i<N;i++)
printf("%d- %d\n",i+1,A[i]);
getchar();
}
int main()
{
oku();
sirala();
yaz();
return 0;
}