terça-feira, 29 de outubro de 2013

Quick Sort (em c)

Quicksort is a very efficient sorting algorithm. It has two phases:
- the partition phase and
-the sort phase,
Most of the work is done in the partition phase. it works out where to divide the work.
The sort phase simply sorts the two smaller problems that are generated in the partition phase.
Complexity: O(n.log n)




void quick_sort(int n, int* v)
{
    if(n<=1)
        return;
    else
    {
        int x=v[0];
        int e=1;
        int d=n-1;

        do
        {
            while(e<n && v[e] <=x) e++;
            while(v[d]>x)d--;
            if(e<d)//faz a troca
            {
                int temp=v[e];
                v[e]=v[d];
                v[d]=temp;
                e++;
                d--;
            }
        }
        while(e<=d); //troca o pivot
        v[0]=v[d];
        v[d]=x;
        //ordena sub vectores restantes
        quick_sort(d,v);
        quick_sort(n-e,&v[e]);
    }

}

Sem comentários:

Enviar um comentário