quicksort

bilinen hızlı sıralama algoritmalarından birisidir.

c implementasyonu aşağıdadır.

--spoiler--
void swap(int vector[], int x, int y)
{
int temp = vector[x];
vector[x] = vector[y];
vector[y] = temp;
}

void qsort(int vector[], int left, int right)
{
int i, last;

if( left >= right )
return; // dizi en az iki eleman içermiyorsa hiçbirşey yapma.

swap(vector, left, (left + right) / 2);
last = left;

for(i = left + 1; i <= right; i++)
if( vector[i] < vector[left] )
swap(vector, ++last, i);

swap(vector, left, last);
qsort(vector, left, last -1);
qsort(vector, last + 1, right);
}
--spoiler--

çoğu durumda yeteri kadar hızlı olmasa da küçük data setlerde register ve cacheleri verimli kullandığı için gayet hızlıdır. tabii data setler alıp başını gidince sıçışa geçer.

kabaca dizinin ortasındaki elemanı pivot eleman yaparak 2 minik dizi oluşturur ve bunları kendi aralarında sıralar

bunu kullanan bunu da kullandı:

(bkz: radix sort)