Quick Sort

O quick sort é o método de ordenação mais eficiente pra grande maioria dos casos. Sendo seu pior caso O(n²), mas que raramente ocorre. Geralmente ele ocorre como um O(n log n). O quick sorte faz uso de um pivô, que pode ser definido de maneiras diferentes. A forma que se define o vetor influência em sua eficiência. Uma das formas que o pivô pode ser definido é pelo elemento do meio do vetor. Os elementos menores que o pivô são movidos para direita dele e os maiores para sua esquerda, dessa forma se divide o vetor em esquerda e direita. Este mesmo processo é aplicado novamente em esquerda e direita recursivamente, até que o vetor seja totalmente ordenado. Implementação do Quick Sort em C:

int quickSort(int Vet[],int inicio, int fim) {
int i, j, pivot, aux;
    i = inicio;
    j = fim;
    pivot = Vet[(inicio + fim)/2];
    do {
        while (Vet[i] < pivot && i < fim) i++;
        while (pivot < Vet[j] && j > inicio) j--;
        if (i<=j){
            if (i<j){
                aux = Vet[i];
                Vet[i] = Vet[j];
                Vet[j] = aux ;
            }
            i++;
            j--;
        }
    }while (i<=j);
    if(inicio < j) quickSort (Vet, inicio, j);
    if(i< fim ) quickSort (Vet, i, fim);
    return 0;
}

Observe que para chamar o Quick sort é necessário informar o inicio e o fim, sendo que nos outros podemos definir apenas o tamanho. Isso deve acontecer pois, quando ele for chamado recursivamente os valores do inicio e fim será diferente, nesta etapa que ocorre a divisão do vetor. Por isso é dito que ele usa o método dividir para conquistar. Abaixo, a mesma implementação com a chamada da função no main:

#include <stdio.h>
int quickSort(int Vet[],int inicio, int fim) {
int i, j, pivot, aux;
    i = inicio;
    j = fim;
    pivot = Vet[(inicio + fim)/2];
    do {
        while (Vet[i] < pivot && i < fim) i++;
        while (pivot < Vet[j] && j > inicio) j--;
        if (i<=j){
            if (i<j){
                aux = Vet[i];
                Vet[i] = Vet[j];
                Vet[j] = aux ;
            }
            i++;
            j--;
        }
    }while (i<=j);
    if(inicio < j) quickSort (Vet, inicio, j);
    if(i< fim ) quickSort (Vet, i, fim);
    return 0;
}

int main()
{
    int vet[10] = {9,8,6,1,5,2,6,4,0,6}, i;
    quickSort(vet, 0, 9);
    //imprime vetor ordenado
    printf("Vetor ordenado: ");
    for(i = 0; i < 10; i++)
        printf("%d, ",vet[i]);
}