Quicksort

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Quicksort

Animação do algoritmo rearranjando um conjunto de valores consecutivos embaralhados
classe Algoritmo de ordenação
estrutura de dados Array, Listas ligadas
complexidade pior caso
complexidade caso médio
complexidade melhor caso
complexidade de espaços pior caso
otimo Não
estabilidade não-estável
Algoritmos

O algoritmo Quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960[1] , quando visitou a Universidade de Moscovo como estudante. Naquela época, Hoare trabalhou em um projeto de tradução de máquina para o National Physical Laboratory. Ele criou o 'Quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rápido. Foi publicado em 1962 após uma série de refinamentos.[2]

Quicksort é um algoritmo de ordenação por comparação não-estável.

O algoritmo

Algumas etapas do algoritmo Quicksort.

O Quicksort adota a estratégia de divisão e conquista. A estratégia consiste em rearranjar as chaves de modo que as chaves "menores" precedam as chaves "maiores". Em seguida o Quicksort ordena as duas sublistas de chaves menores e maiores recursivamente até que a lista completa se encontre ordenada. [3] Os passos são:

  1. Escolha um elemento da lista, denominado pivô;
  2. Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sublistas não ordenadas. Essa operação é denominada partição;
  3. Recursivamente ordene a sublista dos elementos menores e a sublista dos elementos maiores;

A base da recursão são as listas de tamanho zero ou um, que estão sempre ordenadas. O processo é finito, pois a cada iteração pelo menos um elemento é posto em sua posição final e não será mais manipulado na iteração seguinte.

Complexidade

  • Complexidade de tempo: θ(n log 2 n) no melhor caso e caso médio e θ(n2) no pior caso;
  • Complexidade de espaço: θ(log 2 n) no melhor caso e no caso médio e θ(log 2 n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade θ(n2) no pior caso.

Implementações

Pseudocódigo

procedimento QuickSort(X[], IniVet, FimVet)
var
   i, j, pivo, aux
início
   i <- IniVet
   j <- FimVet
   pivo <- X[(IniVet + FimVet) div 2]
      enquanto(i < j)
       |      enquanto (X[i] < pivo) faça
       |        |   i <- i + 1
       |      fimEnquanto
       |      enquanto (X[j] > pivo) faça
       |        |   j <- j - 1
       |      fimEnquanto
       |      se (i <= j) então
       |        |  aux  <- X[i]
       |        |   X[i] <- X[j]
       |        |   X[j] <- aux
       |        |   i <- i + 1
       |        |   j <- j - 1
       |      fimSe
       fimEnquanto
       se (j > IniVet) então
          |   QuickSort(X, IniVet, j)
       fimSe
       se (i < FimVet) então
       |  QuickSort(X, i, FimVet)
       fimse
fimprocedimento

C

Uma forma de se fazer o quickSort é considerar o primeiro elemento como pivô, sempre organizando o vetor de tal forma que, para ordem crescente, os elementos menores que o pivô sejam postos à sua esquerda e os maiores, à sua direita. O processo utiliza recursão até que se chegue a apenas um elemento do vetor.

//Código para Ordenar um vetor de 10 inteiros.
#include<stdio.h>
#include<stdlib.h>
#define TAM 10

void quick(int vet[], int esq, int dir){
    int pivo = esq,i,ch,j;
    for(i=esq+1;i<=dir;i++){
        j = i;
        if(vet[j] < vet[pivo]){
         ch = vet[j];
         while(j > pivo){    
            vet[j] = vet[j-1];
            j--;
         }
         vet[j] = ch;
         pivo++;        
        }  
    }
    if(pivo-1 >= esq){
        quick(vet,esq,pivo-1);
    }
    if(pivo+1 <= dir){
        quick(vet,pivo+1,dir);
    }
 }

int main(){
    int vet[TAM],i;
    
    for(i=0;i<TAM;i++)
        scanf("%d",&vet[i]);
        
    quick(vet,0,TAM-1);
    
    for(i=0;i<TAM;i++)
        printf("%d ",vet[i]);    
    printf("\n");
    return 0;
}

Comparação com outros algoritmos de ordenação

Quicksort é uma versão optimizada de uma árvore binária ordenada. Em vez de introduzir itens sequencialmente numa árvore explicita, o Quicksort organiza-os correntemente na árvore onde está implícito, fazendo-o com chamadas recursivas à mesma. O algoritmo faz exactamente as mesmas comparações, mas com uma ordem diferente.

O algoritmo que mais se familiariza com o Quicksort é o Heapsort. Para o pior caso neste algoritmo temos . Mas, o Heapsort em média trata-se de um algoritmo mais lento que o Quicksort, embora essa afirmação já tenha sido muito debatida. No Quicksort permanece o caso do pior caso, à exceção quando se trata de usar a variante Intro sort, que muda para Heapsort quando um pior caso é detectado. Caso se saiba à partida que será necessário o uso do heapsort é aconselhável usá-lo directamente, do que usar o introsort e depois chamar o heapsort, torna mais rápido o algoritmo.

O Quicksort também compete com o Mergesort, outro algoritmo de ordenação recursiva, tendo este o benefício de ter como pior caso . Mergesort, ao contrário do Quicksort e do Heapsort, é estável e pode facilmente ser adptado para operar em listas encadeadas e em listas bastante grandes alojadas num tipo de acesso lento a média como um Network-Attached Storage ou num disco. Embora o Quicksort possa ser operado em listas encadeadas, por vezes escolhendo um mau pivô sem acesso aleatório. A maior desvantagem do Mergesort é que quando opera em arrays, requer de espaço para o melhor caso, considerando que o Quicksort com um particionamento espacial e com recursão utiliza apenas de espaço.

Bucket sort com dois buckets é muito parecido ao Quicksort (quase idêntico), o pivô neste caso é garantidamente o valor do meio do vector.

Ver também

Referências

  1. AZEREDO, Paulo A. (1996). Métodos de Classificação de Dados e Análise de suas Complexidades (Rio de Janeiro: Campus). ISBN 85-352-0004-5. 
  2. «An Interview with C.A.R. Hoare». Communications of the ACM, March 2009 ("premium content"). 
  3. BAASE, Sara (1988). Computer Algorithms. Introduction to Design and Analysis (em inglês) 2ª ed. (Reading, Massachusetts: Addison-Wesley). p. 53. ISBN 0-201-06035-3. 

Ligações externas