Quicksort: diferenças entre revisões
Linha 435: | Linha 435: | ||
(sort [y | y <- rest, y >=pivot]) |
(sort [y | y <- rest, y >=pivot]) |
||
</pre> |
</pre> |
||
lololol |
|||
=== [[Erlang]] === |
=== [[Erlang]] === |
Revisão das 22h04min de 6 de novembro de 2012
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 facil e rapidamente. Foi publicado em 1962 após uma série de refinamentos.[2]
O Quicksort é um algoritmo de ordenação por comparação não-estável.
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. [3]Os passos são:
- Escolha um elemento da lista, denominado pivô;
- 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;
- 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 lg2 n) no melhor caso e caso médio e θ(n2) no pior caso;
- Complexidade de espaço: θ(lg2 n) no melhor caso e no caso médio e θ(lg2 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
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 As Long)
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
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])
lololol
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[4], 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 lg2 n). Ainda assim, é possível forçar o uso do quicksort através do pragma 'sort':
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 randômico
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
Referências
- ↑ 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
- ↑ «An Interview with C.A.R. Hoare». Communications of the ACM, March 2009 ("premium content")
- ↑ BAASE, Sara (1988). Computer Algorithms. Introduction to Design and Analysis (em inglês) 2ª ed. Reading, Massachusetts: Addison-Wesley. 53 páginas. ISBN 0-201-06035-3
- ↑ «Documentação oficial da função 'sort' em Perl». perl.org. Consultado em 20 de outubro de 2008