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[editar | editar código-fonte]

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[editar | editar código-fonte]

  • 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[editar | editar código-fonte]

Pseudocódigo[editar | editar código-fonte]

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[editar | editar código-fonte]

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.

 1 //Código para Ordenar um vetor de 10 inteiros.
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #define TAM 10
 5 
 6 void quick(int vet[], int esq, int dir){
 7     int pivo = esq, i,ch,j; //Declaração das variavés e inicialização do pivo com o primeiro algarismo da sequencia
 8     for(i=esq+1;i<=dir;i++){//Percorre todos os espaços do vetor
 9         j = i;//atribuição de valor
10         if(vet[j] < vet[pivo]){//verifica se o vetor da posição pivo é maior que de outra posição
11          ch = vet[j];//ch recebe o valor que é menor
12          while(j > pivo){    //repeti enquanto o j que é a posição do algarismo menor que o pivo ficar na posição 0
13             vet[j] = vet[j-1];//reorganiza a posição de vetores
14             j--;//decremento para a organização
15          }
16          vet[j] = ch;// atribuição da variavel menor que o pivo na posição inicial
17          pivo++;// aumenta a posição do pivo em uma unidade
18         }  
19     }
20     if(pivo-1 >= esq){// verifica se o valor do pivo é maior que o final do vetor.
21         quick(vet,esq,pivo-1);//final da execursão da função
22     }
23     if(pivo+1 <= dir){//verifica se o valor do pivo é menor, indicando que ainda estar dentro das limitações do vetor
24         quick(vet,pivo+1,dir);//chama a função para eecutar novamente
25     }
26  }
27 
28 int main(){
29     int vet[TAM],i;//Declara a variavel i e o vetor vet com 10 posições de 0 a 9.
30     printf("Digite 10 numeros"); //Imprime na tela a mensagem.
31     for(i=0;i<TAM;i++)//Percorrertodo os espaços do vetor
32         scanf("%d",&vet[i]);//armazena os dados coletados todo no vetor
33     quick(vet,0,TAM-1);//Chama a função quick com os tres parametros: o vetor, 0 o inicio do vetor e o fim.    
34     for(i=0;i<TAM;i++)//percorre o vetor
35         printf("%d ",vet[i]);   //imprime o vetor reorganizado
36     printf("\n");
37     return 0;
38 }

Python Quicksort também pode ser implementado de formar Recursiva.

 1 def quickSort(vetor,inicio,fim):
 2     if(inicio < fim):
 3         q = pQSort(vetor,inicio,fim) #q[0] = pivo; q[1] = inicio; q[2] = fim
 4         quickSort(vetor, q[1],q[0]-1) #(vetor, inicio, pivo-1)
 5         quickSort(vetor, q[0]+1,q[2]) #(vetor, pivo+1, fim)
 6              
 7 def pQSort(vetor,inicio,fim):
 8     pivo = vetor[fim]
 9     i = inicio-1
10 
11     for j in range(inicio,fim):
12         if(vetor[j] <= pivo):
13             i += 1
14             vetor[i],vetor[j] = vetor[j],vetor[i]
15 
16     vetor[i+1],vetor[fim] = vetor[fim],vetor[i+1]
17     return i+1,inicio,fim

Comparação com outros algoritmos de ordenação[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]