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 {O}(n^2)
complexidade caso médio {O}(n\log n)
complexidade melhor caso {O}(n\log n)
complexidade de espaços pior caso O(n)
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 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[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 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[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

Pascal[editar | editar código-fonte]

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

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

procedure Quick_Sort(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.Net[editar | editar código-fonte]

 Sub QuickSort(ByRef vetor() As String, ByVal inicio As Long, ByVal final As Long)
        Dim pivo As String
        Dim i As Long
        Dim j As Long
 
        If final > inicio Then
            i = inicio
            j = final
            pivo = vetor(Fix((inicio + final / 2)))
            While i <= j
                While vetor(i) < pivo
                    i = i + 1
                End While
                While pivo < vetor(j)
                    j = j - 1
                End While
                If i <= j Then
                    Troca(vetor(i), vetor(j))
                    i = i + 1
                    j = j - 1
                End If
            End While
            QuickSort(vetor, inicio, j)
            QuickSort(vetor, final, i)
        End If
 
    End Sub
 
    Sub Troca(ByRef val1 As String, ByRef val2 As String)
        Dim aux As String
        aux = val1
        val1 = val2
        val2 = aux
    End Sub

Javascript[editar | editar código-fonte]

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

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

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

  sort :: (Ord a)   => [a] -> [a]
  sort []           = []
  sort (pivot:rest) = (sort [y | y <- rest, y < pivot])
                       ++ [pivot] ++
                      (sort [y | y <- rest, y >=pivot])

Erlang[editar | editar código-fonte]

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

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

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

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

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

Implementação utilizando o groupBy e o compareTo "<=>".

def sort(list) {
    if (list.size() < 2) return list
    def items = list.groupBy { it <=> list[0] }.withDefault { [] }
    sort(items[-1]) + items[0] + sort(items[1])
}

ML[editar | editar código-fonte]

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

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

<?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/C++[editar | editar código-fonte]

void quickSort(int valor[], int esquerda, int direita)
{
    int i, j, x, y;
    i = esquerda;
    j = direita;
    x = valor[(esquerda + direita) / 2];
 
    while(i <= j)
    {
        while(valor[i] < x && i < direita)
        {
            i++;
        }
        while(valor[j] > x && j > esquerda)
        {
            j--;
        }
        if(i <= j)
        {
            y = valor[i];
            valor[i] = valor[j];
            valor[j] = y;
            i++;
            j--;
        }
    }
    if(j > esquerda)
    {
        quickSort(valor, esquerda, j);
    }
    if(i < direita)
    {
        quickSort(valor,  i, direita);
    }
}

ASP[editar | editar código-fonte]

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

void trocaValores(int* a, int* b)
{
    int aux;
    aux = *a;
    *a = *b;
    *b = aux;
}
 
int divide(int vec[], int esquerdo, int direito)
{
    int i, j;
 
    i = esquerdo;
    for (j = esquerdo + 1; j <= direito; ++j)
    {
        if (vec[j] < vec[esquerdo])
        {
            ++i;
            trocaValores(&vec[i], &vec[j]);
        }
    }
    trocaValores(&vec[esquerdo], &vec[i]);
 
    return i;
}
 
void quickSort(int vec[], int esquerdo, int direito)
{
    int r;
 
    if (direito > esquerdo)
    {
        r = divide(vec, esquerdo, direito);
        quickSort(vec, esquerdo, r - 1);
        quickSort(vec, r + 1, direito);
    }
}

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.

# include <string.h>
 
void ordenar_quicksort_nome(int ini, int fim, char vetor[][50])
{
    int i = ini, f = fim;
    char pivo[50], aux_char[50];
    strcpy(pivo, vetor[(ini + fim) / 2]);
    if (i <= f)
    {
        while (strcasecmp(vetor[i], pivo)<0)
            i++;
        while (strcasecmp(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, vetor);
    if (i < fim)
        ordenar_quicksort_nome(i, fim, vetor);
}

JAVA[editar | editar código-fonte]

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

C#[editar | editar código-fonte]

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

ARM Assembly[editar | editar código-fonte]

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

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

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[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 \mathcal{O}(n \log2 n). 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.

Ver também[editar | editar código-fonte]

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 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 pp. ISBN 0-201-06035-3
  4. Documentação oficial da função 'sort' em Perl perl.org. Página visitada em 2008-10-20.

Ligações externas[editar | editar código-fonte]