Curso de Pascal
Quick Sort


  O Quicksort é um algoritmo de ordenação rápido, criado por C.A.R. Hoare na década de 60. Ele 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.

  Passos:
  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 sub listas não ordenadas.
  3. Recursivamente ordene a sub lista dos elementos menores e a sub lista dos elementos maiores.
  Fonte: Wikipedia[1]

  A seguir, será apresentado o algoritmo que realiza o Quicksort.
{$A-}

var vetor : array[1..10] of integer;

procedure quicksort(inicio, fim : integer);
var i, j, pivo, aux : integer;
begin
  i := inicio;
  j := fim;
  pivo := vetor[(inicio + fim) div 2];

  while (i <= j) do
  begin
    while (vetor[i] < pivo) and (i < fim) do
      i := i+1;

    while (vetor[j] > pivo) and (j > inicio) do
      j := j-1;

    if (i <= j) then
    begin
      aux := vetor[i];
      vetor[i] := vetor[j];
      vetor[j] := aux;
      i := i+1;
      j := j-1;
    end;
  end;

  if (j > inicio) then
    quicksort(inicio, j);

  if (i < fim) then
    quicksort(i, fim);
end;

procedure cria_vetor;
var i : integer;
begin
  randomize;
  for i:=1 to 10 do
    vetor[i] := random(100)+1;
end;

procedure imprime_vetor;
var i : integer;
begin
  for i:=1 to 10 do
    write(vetor[i], ' ');
  writeln;
end;

begin
  cria_vetor;

  writeln('Vetor desordenado:');
  imprime_vetor;
  writeln;

  quicksort(1, 10);

  writeln('Vetor ordenado:');
  imprime_vetor;
end.
  Adaptado de: Wikipedia[1]

  Saída:
  Vetor desordenado:
  25 59 38 76 98 14 12 93 31 11
  Vetor ordenado:
  11 12 14 25 31 38 59 76 93 98

  Obs: Para os sistemas CP/M-80 que utilizam o Pascal, no caso, o modelo do MSX, deve-se utilizar a diretiva {$A-} para ativar as recursividades.



  Referências:

  [1]- Quick Sort, Wikipedia - http://pt.wikipedia.org/wiki/Quicksort

<< Anterior Pascal Próxima >>


/MARMSX/CURSOS/PASCAL