Quicksort – Wikipédia a enciclopédia livre

Prévia do material em texto

Quicksort
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
Quicksort
Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Quick sort)
O algoritmo Quicksort é um método de ordenação
muito rápido e eficiente, inventado por C.A.R. Hoare
em 1960 , 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 facil e rapidamente. Foi publicado em
1962 após uma série de refinamentos.
O Quicksort é um algoritmo de ordenação por
comparação não-estável.
Índice
1 O algoritmo
2 Complexidade
3 Implementações
3.1 Pseudocódigo
3.2 Pascal
3.3 PHP 5 - OO
3.4 Delphi (Método Recursivo)
3.5 Visual Basic
3.6 Javascript
3.7 Python
3.8 Assembly x86-gas-Linux
3.9 Haskell
3.10 Erlang
3.11 Lisp
3.12 Perl
3.13 Ruby
3.14 Groovy
3.15 ML
3.16 PHP
3.17 PHP (utilizando pivot)
3.18 C++
3.19 ASP
3.20 C
3.21 JAVA
[1]
[2]
Algumas etapas do algoritmo
Quicksort.
3.22 C#
3.23 Assembly x86
3.24 Prolog
3.25 Lua
4 Comparação com outros algoritmos de
ordenação
5 Veja também
6 Referências
7 Ligações externas
O algoritmo
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. 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 lg n) no melhor caso e caso
médio e θ(n ) no pior caso;
Complexidade de espaço: θ(lg n) no melhor caso e no caso
médio e θ(lg n) no pior caso. R. Sedgewick desenvolveu uma
versão do Quicksort com partição recursão de cauda que tem
complexidade θ(n ) no pior caso.
Implementações
Pseudocódigo
[3]
2
2
2
2
2
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 
 
Pascal
program quicksort;
uses crt;
const
 left=1;
 right=10;
 type
 vetor = array [left..right]of integer;
procedure ordena(var vet:vetor; left:integer; right:integer);
var i,j,aux,meio:integer;
begin
 i:=left;
 j:=right;
 meio:=vet[(left + right) div 2];
 while(i < j)do begin
 while(vet[i] < meio)do begin
 i:=i + 1;
 end;
 while(vet[j] > meio)do begin
 j:=j - 1;
 end;
 if(i <= j)then begin
 aux:= vet[i];
 vet[i]:=vet[j];
 vet[j]:=aux;
 i:=i + 1;
 j:=j - 1;
 end;
 end;
 if(j > left)then begin
 ordena(vet, left, j);
 end;
 if(i < right)then begin
 ordena(vet, i, right);
 end;
end;
var
 vet:vetor;
 i:integer;
begin
 vet[1]:=2;vet[2]:=4;vet[3]:=7;vet[4]:=5;vet[5]:=8;vet[6]:=10;vet[7]:=3;vet[8]:=1;vet[9]:=6;vet[10]:=9;
 for i:= 1 to 10 do begin
 write(vet[i],' ');
 end;
 writeln();
 writeln();
 ordena(vet, left, right);
 for i:= 1 to 10 do begin
 write(vet[i],' ');
 end;
 readkey;
end.
PHP 5 - OO
class QuickSortUtil {
 
 private static function partition(&$array, $f, $l, $property) {
 $pivot = $array[$f]->$property;
 while ($f < $l) {
 while ($array[$f]->$property < $pivot) $l++;
 while ($array[$l]->$property > $pivot) $f--;
 $temp = $array[$f];
 $array[$f] = $array[$l];
 $array[$l] = $temp;
 }
 return $f;
 }
 
 public static function sort(&$array, $property, $f=null, $l=null) {
 if(is_null($f)) $f = 0;
 if(is_null($l)) $l = count($array)-1;
 if ($f >= $l) return;
 $pivot_index = self::partition($array, $f, $l, $property);
 self::sort($array, $property, $f, $pivot_index);
 self::sort($array, $property, $pivot_index+1, $l);
 } 
 
}
Delphi (Método Recursivo)
procedure QuickSort(var A: array of Integer);
 
 procedure QuickSort(var A: array of Integer; iLo, iHi: Integer);
 var
 Lo, Hi, Mid, T: Integer;
 begin
 Lo := iLo;
 Hi := iHi;
 Mid := A[(Lo + Hi) div 2];
 repeat
 while A[Lo] < Mid do Inc(Lo);
 while A[Hi] > Mid do Dec(Hi);
 if Lo <= Hi then
 begin
 T := A[Lo];
 A[Lo] := A[Hi];
 A[Hi] := T;
 Inc(Lo);
 Dec(Hi);
 end;
 until Lo > Hi;
 if Hi > iLo then QuickSort(A, iLo, Hi);
 if Lo < iHi then QuickSort(A, Lo, iHi);
 end;
 
begin
 QuickSort(A, Low(A), High(A));
end;
 
{Chamando em um evento de onClick}
procedure TForm1.Button1Click(Sender: TObject);
var
 arr: array[0..100] of integer;
 I: Integer;
begin
 for I:=Low(arr) to High(arr) do
 arr[I]:=Random(High(Integer));
 
 Quick_Sort(arr);
end;
Visual Basic
Sub QuickSort(ByRef vetor() As Long, ByVal inicio As Long, ByVal final As Long, ByRef iteracoes 
 Dim pivo As Long
 Dim i As Long
 Dim j As Long
 iteracoes = iteracoes + 1
 If final > inicio Then
 i = inicio
 j = final
 pivo = vetor(Fix((inicio + final) / 2))
 While i <= j
 While vetor(i) < pivo
 i = i + 1
 Wend
 While pivo < vetor(j)
 j = j - 1
 Wend
 If i <= j Then
 Call Troca(vetor(i), vetor(j))
 i = i + 1
 j = j - 1
 End If
 Wend
 Call QuickSort(vetor, inicio, j, iteracoes)
 Call QuickSort(vetor, i, final, iteracoes)
 End If
 
End Sub
 
Sub Troca(ByRef val1 As Long, ByRef val2 As Long)
 Dim aux As Long
 aux = val1
 val1 = val2
 val2 = aux
End Sub
Javascript
function quickSort(vet, esq, dir){
 var ce = esq;
 var cd = dir;
 var meio = parseInt((ce + cd)/ 2); 
 while(ce < cd){
 while(vet[ce] < vet[meio]){
 ce++; 
 }
 while(vet[cd] > vet[meio]){
 cd--;
 }if(ce <= cd){
 var temp = vet[ce];
 vet[ce] = vet[cd];
 vet[cd] = temp;
 ce++;
 cd--;
 } 
 } 
 if(cd > esq)
 quickSort(vet, esq, cd); 
 
 if(ce < dir)
 quickSort(vet, ce, dir); 
}
 
var vet = [4,10,3,9,7,1,12]; //adicionando elementos 
document.write(vet.join(" ")+"<br/>");
var esq = 0;
var dir = vet.length - 1; //indice máximo do array
quickSort(vet, esq, dir); 
document.write(vet.join(" "));
Python
Versão simples
def quicksort(v):
 if len(v) <= 1:
 return v # uma lista vazia ou com 1 elemento ja esta ordenada
 less, equal, greater = [], [], [] # cria as sublistas dos maiores, menores e iguais ao pivo
 pivot = v[0] # escolhe o pivo. neste caso, o primeiro elemento da lista
 for x in v:
 # adiciona o elemento x a lista corespondeste
 if x < pivot: 
 less.append(x)
 elif x == pivot:
 equal.append(x)
 else:
 greater.append(x)
 return quicksort(less) + equal + quicksort(greater) # concatena e retorna recursivamente
 # .. as listas ordenadas
Versão in-place
def partition(v, left, right):
 i = left
 for j in range(left + 1, right + 1):
 if v[j] < v[left]: # Se um elemento j for menor que o pivo
 i += 1 # .. incrementa-se i
 v[i], v[j] = v[j], v[i] # .. e troca o elemento j de posicao o elemento i
 v[i], v[left] = v[left], v[i] # O pivo e' colocado em sua posicao final
 return i
 
def quicksort(v, left, right):
 if right > left: # Verifica se a lista tem 2 ou mais itens
 pivotIndex = partition(v, left, right) # Pega a posicao do pivo
 quicksort(v, left, pivotIndex - 1) # Ordena recursivamente os itens menores que o pivo
 quicksort(v, pivotIndex + 1, right) # Ordena recursivamente os itens maiores que o pivo
 
''' 
Exemplo de uso
>>> a = [4, 2, 4, 6, 3, 2, 5, 1, 3]
>>> quicksort(a, 0, len(a)-1)
>>> print a
>>> [1, 2, 2, 3, 3, 4, 4, 5, 6]
'''
Assembly x86-gas-Linux
/*void quicksort_as (int *x, int n);*/
.globl quicksort_as
quicksort_as:
 pushl %ebp
 movl %esp, %ebp
 /* 8(%ebp)= ponteiro do arranjo */
 /* 12(%ebp)= num de elementos */
 movl 12(%ebp), %eax
 dec %eax
 movl $4, %ebx
 mul %ebx
 pushl %eax
 pushl $0
 pushl 8(%ebp)
 call quicksort_as_
 leave
 ret
quicksort_as_:
 pushl %ebp
 movl %esp, %ebp
 /* 8(%ebp)= ponteiro do arranjo */
 /* 12(%ebp)= esq */
 /* 16(%ebp)= dir */
 movl 12(%ebp), %ecx
 movl %ecx, %edx
 movl 8(%ebp), %eax
 movl 8(%ebp), %eax
 addl %ecx, %eax
 movl 16(%ebp), %ecx
 movl 8(%ebp), %ebx
 addl %ecx, %ebx
 /* agora %eax aponta p/ x[esq] e %ebx x[dir]*/
 addl %edx, %ecx /*%ecx eh esq + dir*/
 pushl %eax
 movl %ecx, %eax
 movl $2, %ecx
 cltd
 idivl %ecx /* div %eax por 2=%ecx*/
 movl $4, %ecx
 cltd
 idivl %ecx
 mul %ecx
 movl 8(%ebp), %ecx
 addl %eax, %ecx
 movl (%ecx), %ecx
 popl %eax
 /*%ecx = compare(cmp)*/ 
quicksort_imj:
 cmp %eax, %ebx
 jle quicksort_fim
quicksort_inci:
 cmp (%eax), %ecx
 jle quicksort_incj
 addl $4, %eax
 jmp quicksort_inci
quicksort_incj:
 cmp (%ebx), %ecx
 jge quicksort_troca
 subl $4, %ebx
 jmp quicksort_incj
quicksort_troca:
 cmp %eax, %ebx
 jl quicksort_fim
 movl (%ebx), %edx
 pushl (%eax)
 movl %edx, (%eax)
 popl (%ebx)
 addl $4, %eax
 subl $4, %ebx
 jmp quicksort_imj
quicksort_fim:
 /*salvando registradores na pilha p/ fazer chamada de função*/
 pushl %eax
 pushl %ebx
 /*passando parametros p/ chamada recursiva*/
 subl 8(%ebp), %eax
 cmp %eax, 16(%ebp)
 jle quicksort_2a_rec
 pushl 16(%ebp)
 pushl %eax
 pushl 8(%ebp)
 call quicksort_as_
 addl $12, %esp
quicksort_2a_rec:
 /*recuperando registradores apos chamada de funcao*/
 popl %ebx
 popl %eax
 subl 8(%ebp), %ebx
 cmp %ebx, 12(%ebp)
 jge quicksort_final
 /*passando parametros p/ chamada recursiva*/
 pushl %ebx
 pushl 12(%ebp)
 pushl 8(%ebp)
 call quicksort_as_
quicksort_final:
 leave
 ret
Haskell
 sort :: (Ord a) => [a] -> [a]
 sort [] = []
 sort (pivot:rest) = (sort [y | y <- rest, y < pivot])
 ++ [pivot] ++ 
 (sort [y | y <- rest, y >=pivot])
Erlang
Uma versão similar a Haskell, utilizando list comprehensions:
quicksort([]) -> [];
quicksort([Pivot|Rest]) ->
 quicksort([Smaller || Smaller <- Rest, Smaller =< Pivot])
 ++ [Pivot] ++
 quicksort([Larger || Larger <- Rest, Larger > Pivot]).
Uma versão com melhor performance utilizando tail recursive:
qsort([]) -> [];
qsort(L=[_|_]) -> qsort(L, []).
 
qsort([], Acc) -> Acc;
qsort([Pivot|Rest], Acc) ->
 partition(Pivot, Rest, {[], [Pivot], []}, Acc).
 
partition(_, [], {Smaller, Equal, Larger}, Acc) ->
 qsort(Smaller, Equal ++ qsort(Larger, Acc));
partition(Pivot, [H|T], {Smaller, Equal, Larger}, Acc) ->
 if H < Pivot ->
 partition(Pivot, T, {[H|Smaller], Equal, Larger}, Acc);
 H > Pivot ->
 partition(Pivot, T, {Smaller, Equal, [H|Larger]}, Acc);
 H == Pivot ->
 partition(Pivot, T, {Smaller, [H|Equal], Larger}, Acc)
 end.
Lisp
(defun partition (fun array)
 (list (remove-if-not fun array) (remove-if fun array)))
 
(defun sort (array)
 (if (null array) nil
 (let ((part (partition (lambda (x) (< x (car array))) (cdr array))))
 (append (sort (car part)) (cons (car array) (sort (cadr part)))))))
Perl
Versões anteriores ao Perl 5.6 utilizavam o algoritmo quicksort para implementar a função sort
(http://perldoc.perl.org/functions/sort.html) , então o código em Perl pode resumir-se a:
my @ordenada = sort @lista;
Como a implementação do quicksort pode assumir tempos quadráticos para algumas entradas, o algoritmo foi
substituído na versão 5.8 pelo mais estável mergesort, cujo pior caso é θ(n lg n). Ainda assim, é possível forçar
o uso do quicksort através do pragma 'sort' (http://perldoc.perl.org/sort.html) :
[4]
2
use sort '_quicksort';
my @ordenada = sort @lista;
Uma implementação em Perl puro (mais lenta que o 'sort' embutido) pode ser:
sub quicksort {
 my @lista = @_;
 my (@menores, @iguais, @maiores);
 
 return @lista if @lista < 2;
 foreach (@lista) {
 if ($_ < $lista[0]) {
 push @menores, $_;
 }
 elsif ($_ == $lista[0]) {
 push @iguais, $_;
 }
 else {
 push @maiores, $_;
 }
 }
 return quicksort(@menores), @iguais, quicksort(@maiores);
}
Já uma versão menor (e certamente menos legível) poderia ser:
sub quicksort {
 return @_ if @_ < 2;
 my (@iguais, @maiores, @menores);
 push @{ (\@iguais, \@menores, \@maiores)[ $_[0] <=> $_ ]}, $_ for @_;
 quicksort(@menores), @iguais, quicksort(@maiores);
}
Ruby
def sort(array)
 return array if array.size <= 1
 pivot = array[0]
 return sort(array.select { |y| y < pivot }) +
 array.select { |y| y == pivot } + 
 sort(array.select { |y| y > pivot })
end
Groovy
def sort(list) {
 if (list.isEmpty()) return list
 anItem = list[0]
 def smallerItems = list.findAll{it < anItem}
 def equalItems = list.findAll{it = anItem}
 def largerItems = list.findAll{it > anItem}
 sort(smallerItems) + equalItems + sort(largerItems)
}
ML
fun filter nil elem cmp = nil
 | filter (x::xl) elem cmp =
 if (cmp(x, elem))
 then x:: filter xl elem cmp
 else filter xl elem cmp;
fun quicksort nil = nil
 | quicksort (pivot::xl) =
 let
 val small = filter xl pivot (op <);
 val medium = pivot :: filter xl pivot (op =);
 val large = filter xl pivot (op >);
 in
 (quicksort small) @ medium @ (quicksort large)
 end;
PHP
<?php
/*********************************************************************
*Obs.: a implementação usa parâmetros por referência, isto é, o vetor *passado será modificado.
*********************************************************************/
 
function quicksort(&$vet, $ini, $fim)
{
 $i = $ini;
 $j = $fim;
 $dir = 1;
 
 while ($i < $j)
 {
 if ($vet[$i] > $vet[$j])
 {
 $aux = $vet[$i];
 $vet[$i] = $vet[$j];
 $vet[$j] = $aux;
 
 $dir = - $dir;
 }
 
 if ($dir == 1)
 $j--; 
 else
 $i++;
 }
 
 $k = $i;
 if($ini < $f)
 quicksort($vet, $ini, $k-1);
 
 if($i < $fim)
 quicksort($vet, $k+1, $fim);
 
}
quicksort($vet,0,count($vet));
?>
PHP (utilizando pivot)
<?php
/* Função utilizando pivot */
function quicksort(&$vet,$ini,$fim)
{
 $i = $ini;
 $f = $fim;
 
 $pivo = $vet[(int)(($ini+$fim)/2)];
 
 while($i < $f)
 {
 while($vet[$i] < $pivo)
 $i++;
 
 while($vet[$f] > $pivo)
 $f--;
 
 if($i <= $f)
 {
 $aux = $vet[$i];
 $vet[$i] = $vet[$f];
 $vet[$f] = $aux;
 $i++;
 $f--;
 }
 }
 if($ini < $f)
 quicksort($vet,$ini,$f);
 
 if($i < $fim)
 quicksort($vet,$i,$fim);
}
?>
C++
#include <algorithm>
#include <iterator>
#include <functional>
using namespace std;
 
template <typename T>
void sort(T begin, T end) {
 if (begin != end) {
 T middle = partition (begin, end, bind2nd(less<iterator_traits<T>::value_type>(), *begin
 sort (begin, middle);
 sort (max(begin + 1, middle), end);
 }
}
ASP
<%
Response.Write("QuickSort Algorithm")& vbNewLine
 
Sub QuickSort(vec,loBound,hiBound)
 Dim pivot,loSwap,hiSwap,temp
 
 '== Two items to sort
 if hiBound - loBound = 1 then
 if vec(loBound) > vec(hiBound) then
 temp=vec(loBound)
 vec(loBound) = vec(hiBound)
 vec(hiBound) = temp
 End If
 End If
 
 '== Three or more items to sort
 pivot = vec(int((loBound + hiBound) / 2))
 vec(int((loBound + hiBound) / 2)) = vec(loBound)
 vec(loBound) = pivot
 loSwap = loBound + 1
 hiSwap = hiBound
 
 do
 '== Find the right loSwap
 while loSwap < hiSwap and vec(loSwap) <= pivot
 loSwap = loSwap + 1
 wend
 '== Find the right hiSwap
 while vec(hiSwap) > pivot
 hiSwap = hiSwap - 1
 wend
 '== Swap values if loSwap is less then hiSwap
 if loSwap < hiSwap then
 temp = vec(loSwap)
 vec(loSwap) = vec(hiSwap)
 vec(hiSwap) = temp
 End If
 loop while loSwap < hiSwap
 
 vec(loBound) = vec(hiSwap)
 vec(hiSwap) = pivot
 
 '== Recursively call function .. the beauty of Quicksort
 '== 2 or more items in first section
 if loBound < (hiSwap - 1) then Call QuickSort(vec,loBound,hiSwap-1)
 '== 2 or more items in second section
 if hiSwap + 1 < hibound then Call QuickSort(vec,hiSwap+1,hiBound)
 
End Sub 'QuickSort
 
Sub PrintArray(vec,lo,hi)
 '== Simply print out an array from the lo bound to the hi bound.
 Dim i
 For i = lo to hi
 Response.Write vec(i)
 Next
End Sub 'PrintArray
 
Randomize
 
Dim x(9)
 
For z = 0 to 9
 x(z) = int(Rnd*1000)
 If (Rnd < 0.5) then x(z) = x(z)-1000
Next
 
Response.Write ("Here is a jumbled array:") & vbNewLine
Call PrintArray(x,0,9)
 
Call QuickSort(x,0,9)
 
Response.Write("Now the array is sorted!")& vbNewLine
Call PrintArray(x,0,9)
 
Response.Write(vbNewLine)
%>
C
void swap(int* a, int* b) {
 int tmp;
 tmp = *a;
 *a = *b;
 *b = tmp;
}
 
int partition(int vec[], int left, int right) {
 int i, j;
 
 i = left;
 for (j = left + 1; j <= right; ++j) {
 if (vec[j] < vec[left]) {
 ++i;
 swap(&vec[i], &vec[j]);
 }
 }
 swap(&vec[left], &vec[i]);
 
 return i;
}
 
void quickSort(int vec[], int left, int right) {
 int r;
 
 if (right > left) {
 r = partition(vec, left, right);
 quickSort(vec, left, r - 1);
 quickSort(vec, r + 1, right);
 }
}
Implementação quicksort testado com ate 1000000 de elementos para dados crescente, decrescente e
aleatório
void swap(int *a, int i, int j) {
 int t = a[i];
 a[i] = a[j];
 a[j] = t;
}
 
int partition(int *a, int left,int right,int pivot)
{
 int pos, i;
 swap(a, pivot, right);
 pos = left;
 for(i = left; i < right; i++)
 {
 if (a[i] < a[right])
 {
 swap(a, i, pos);
 pos++;
 }
 }
 swap(a, right, pos);
 return pos;
}
 
void quick(int *a, int left, int right)
{
 if (left < right)
 {
 int pivot = (left+right)/2;
 int pos = partition(a,left,right,pivot);
 quick(a,left,pos-1);
 quick(a,pos+1,right);
 }
}
Implementaçao usando 'fat pivot':
void sort(int array[], int begin, int end) {
 int pivot = array[begin];
 int i = begin + 1, j = end, k = end;
 int t;
 
 while (i < j) {
 if (array[i] < pivot) i++;
 else if (array[i] > pivot) {
 j--; k--;
 t = array[i];
 array[i] = array[j];
 array[j] = array[k];
 array[k] = t; }
 else {
 j--;
 swap(array[i], array[j]);
 } }
 i--;
 swap(array[begin], array[i]); 
 if (i - begin > 1)
 sort(array, begin, i);
 if (end - k > 1)
 sort(array, k, end); 
}
Lembrando que quando você for chamar a função recursiva terá que chamar a mesma da seguinte forma
ordenar_quicksort_nome(0,n-1). O 0(zero) serve para o início receber a posição zero do vetor e o fim será o
tamanho do vetor -1.
void ordenar_quicksort_nome(int ini, int fim)
{
 int i = ini, f = fim;
 char pivo[50];
 strcpy(pivo,vetor[(ini+fim)/2]);
 if (i<=f)
 {
 while (strcmpi(vetor[i],pivo)<0) i++;
 while (strcmpi(vetor[f],pivo)>0) f--;
 if (i<=f)
 {
 strcpy (aux_char,vetor[i]);
 strcpy (vetor[i],vetor[f]);
 strcpy (vetor[f],aux_char);
 i++; f--;
 }
 }
 if (f>ini) ordenar_quicksort_nome(ini,f);
 if (i<fim) ordenar_quicksort_nome(i,fim);
}
JAVA
 public static void quick_sort(int []v,int ini, int fim) {
 int meio;
 
 if (ini < fim) {
 meio = partition(v, ini, fim);
 quick_sort(v, ini, meio);
 quick_sort(v, meio + 1, fim);
 }
 }
 
 public static int partition(int []v, int ini, int fim) {
 int pivo, topo, i;
 pivo = v[ini];
 topo = ini;
 
 for (i = ini + 1; i <= fim; i++) {
 if (v[i] < pivo) {
 v[topo] = v[i];
 v[i] = v[topo + 1];
 topo++; 
 }
 }
 v[topo] = pivo;
 return topo;
 }
C#
static class QuickSort 
{
 public static void Ordenar(int[] vetor) {
 Ordenar(vetor, 0, vetor.Length - 1);
 }
 
 private static void Ordenar(int[] vetor, int inicio, int fim) {
 if (inicio < fim) {
 int posicaoPivo = Separar(vetor, inicio, fim);
 Ordenar(vetor, inicio, posicaoPivo - 1);
 Ordenar(vetor, posicaoPivo + 1, fim); 
 }
 }
 
 private static int Separar(int[] vetor, int inicio, int fim) {
 int pivo = vetor[inicio];int i = inicio + 1, f = fim;
 while (i <= f) {
 if (vetor[i] <= pivo) 
 i++;
 else if (pivo < vetor[f])
 f--;
 else {
 int troca = vetor[i];
 vetor[i] = vetor[f];
 vetor[f] = troca;
 i++;
 f--;
 }
 }
 vetor[inicio] = vetor[f];
 vetor[f] = pivo;
 return f;
 }
}
Assembly x86
 qsort: @ Takes three parameters:
 @ a: Pointer to base of array a to be sorted (arrives in r0)
 @ left: First of the range of indexes to sort (arrives in r1)
 @ right: One past last of range of indexes to sort (arrives in r2)
 @ This function destroys: r1, r2, r3, r4, r5, r7
 stmfd sp!, {r4, r6, lr} @ Save r4 and r6 for caller
 mov r6, r2 @ r6 <- right
 qsort_tailcall_entry:
 sub r7, r6, r1 @ If right - left <= 1 (already sorted),
 cmp r7, #1
 ldmlefd sp!, {r1, r6, pc} @ Return, moving r4->r1, restoring r6
 ldr r7, [r0, r1, asl #2] @ r7 <- a[left], gets pivot element
 add r2, r1, #1 @ l <- left + 1
 mov r4, r6 @ r <- right
 partition_loop:
 ldr r3, [r0, r2, asl #2] @ r3 <- a[l]
 cmp r3, r7 @ If a[l] <= pivot_element,
 addle r2, r2, #1 @ ... increment l, and
 ble partition_test @ ... continue to next iteration.
 sub r4, r4, #1 @ Otherwise, decrement r,
 ldr r5, [r0, r4, asl #2] @ ... and swap a[l] and a[r].
 str r5, [r0, r2, asl #2]
 str r3, [r0, r4, asl #2]
 partition_test:
 cmp r2, r4 @ If l < r,
 blt partition_loop @ ... continue iterating.
 partition_finish:
 sub r2, r2, #1 @ Decrement l
 ldr r3, [r0, r2, asl #2] @ Swap a[l] and pivot
 str r3, [r0, r1, asl #2]
 str r7, [r0, r2, asl #2]
 bl qsort @ Call self recursively on left part,
 @ with args a (r0), left (r1), r (r2),
 @ also preserves r6 and
 @ moves r4 (l) to 2nd arg register (r1)
 b qsort_tailcall_entry @ Tail-call self on right part,
 @ with args a (r0), l (r1), right (r6)
Prolog
partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
 ( X @< Pivot ->
 Smalls = [X|Rest],
 partition(Xs, Pivot, Rest, Bigs)
 ; Bigs = [X|Rest],
 partition(Xs, Pivot, Smalls, Rest)
 ).
quicksort([]) --> [].
quicksort([X|Xs]) --> 
 { partition(Xs, X, Smaller, Bigger) },
 quicksort(Smaller), [X], quicksort(Bigger).
Lua
function quickSort(v, ini, fim)
 i, j = ini, fim
 pivo = v[math.floor((ini + fim)/2)]
 while i <= j do
 while (v[i] < pivo) do i=i+1 end
 while (v[j] > pivo) do j=j-1 end
 if (i<=j) then 
 v[i], v[j] = v[j], v[i] 
 i, j = i+1, j-1
 end
 end
 if j > ini then quickSort(v, ini, j) end
 if i < fim then quickSort(v, i, fim) end
end
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 uma algoritmo mais lento que o Quicksort, embora
tenha sido muito debatido essa afirmação. No Quicksort permanece o caso do pior caso, à excepçã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 bastantes 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.
Veja também
Ordenação de vetor
Merge sort
Heapsort
Selection sort
Bubble sort
Busca linear
Referências
1. ↑ AZEREDO, Paulo A.. Métodos de Classificação de Dados e Análise de suas Complexidades. Rio de
Janeiro: Campus, 1996. ISBN 85-352-0004-5
2. ↑ An Interview with C.A.R. Hoare (http://cacm.acm.org/magazines/2009/3/21782-an-interview-with-car-
hoare/fulltext) . Communications of the ACM, March 2009 ("premium content").
3. ↑ BAASE, Sara. Computer Algorithms: Introduction to Design and Analysis (em inglês). 2ª ed. Reading,
Massachusetts: Addison-Wesley, 1988. 53 p. ISBN 0-201-06035-3
4. ↑ Documentação oficial da função 'sort' em Perl (http://perldoc.perl.org/functions/sort.html) . perl.org. Página
visitada em 2008-10-20.
Ligações externas
Rápida aula de Quicksort (http://www.ime.usp.br/~pf/algoritmos/aulas/quick.html)
Animação do processo de ordenação pelo Quicksort (http://www.cs.ubc.ca/spider/harrison/Java/sorting-
demo.html)
Explanação video de Quicksort usando cartões e de código em C++
(http://www.datastructures.info/what-is-quicksort-and-how-does-it-work-quick-sort-algorithm/)
QuickSort Code (http://www.algorithm-code.com/wiki/Quick_Sort)
Obtida de "http://pt.wikipedia.org/w/index.php?title=Quicksort&oldid=33213416"
Categoria: Algoritmos de ordenação
Navigation menu
Esta página foi modificada pela última vez à(s) 15h17min de 7 de dezembro de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.