Quicksort: diferenças entre revisões

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
	Esta caixa: ver; discutir;

Explorar interativamente o histórico

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

VisualTexto wiki

Em linha

Revisão das 14h04min de 8 de abril de 2013

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

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])

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 recursividade em cauda:

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

JAVA

        public static void quickSort(int[] v, int inicio, int fim){
	    if(inicio<fim){
		int pivo=inicio, i=fim, vPivo=v[pivo];
		while(pivo<i){
		    if(vPivo>v[i]){
			v[pivo]=v[i];
			pivo=i;
			i=inicio+1;
			while(pivo>i){
                            if(vPivo<v[i]){
				v[pivo]=v[i];
				pivo=i;
				i=fim;
				break;
			     }else
				i++;
			}
		    } else 
			i--;
	       }
	       v[pivo]=vPivo;
	       quicksort(v, inicio, pivo-1);
	       quicksort(v, pivo+1, fim);
	    }
	}

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 ${\mathcal {O}}(n\log 2n)$ . 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 ${\mathcal {O}}(n\log n)$ . 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 ${\mathcal {O}}(n)$ de espaço para o melhor caso, considerando que o Quicksort com um particionamento espacial e com recursão utiliza apenas ${\mathcal {O}}(\log n)$ 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

Ligações externas

[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. 53 páginas. ISBN 0-201-06035-3

[4] «Documentação oficial da função 'sort' em Perl». perl.org. Consultado em 20 de outubro de 2008

[1]

[2]

[3]

[4]

@@ Linha 670: / Linha 670: @@
 }
 </source>
-=== [[ASP]] ===
+.|. === [[ASP]] === .|.
 <source lang="asp">
 <%

v d e Algoritmos de ordenação
Teoria	Algoritmo de ordenação \| Pesquisa binária \| Busca linear \| Ordenação (computação) \| Lista \| Lista duplamente ligada
Exchange sorts	Bubble sort \| Cocktail sort \| Odd-even sort \| Comb sort \| Gnome sort \| Quicksort
Selection sorts	Selection sort \| Heapsort \| Smoothsort \| Cartesian tree sort \| Tournament sort
Insertion sorts	Insertion sort \| Shell sort \| Tree sort \| Library sort \| Patience sorting
Merge sorts	Merge sort \| Strand sort \| Timsort
Outros	Topological sorting \| Sorting network \| Bitonic sorter \| Batcher odd-even mergesort \| Pancake sorting
Ordenações ineficientes/humorísticas	Bogosort (ou "Estou com sort") \| Stooge sort