Quicksort – Wikipédia a enciclopédia livre

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--;
 }