UNISANTOS

Faculdade de Filosofia, Ciências e Letras

Professor: Ciro Cirne Trindade
Disciplina: Estruturas de Dados
Curso: Ciência da Computação
Ano: 2o
Tópico: Busca e Ordenação

Busca e Ordenação

1. Busca Binária
A recursividade pode ser aplicada em atividades muito conhecidas na computação,
como a busca.
Imagine um vetor de elementos no qual os objetos foram posicionados em
determinada ordem. Por exemplo, um dicionário ou um catálogo de telefones pode ser
considerado um vetor cujos elementos estão em ordem alfabética. Suponha que este vetor e
desejemos localizar determinado elemento dentro dele. Por exemplo, queremos pesquisar uma
palavra num dicionário ou um nome num catálogo telefônico. O processo usado para
encontrar tal elemento é chamado busca.
Como a busca é uma atividade muito conhecida na computação, queremos descobrir
um método eficiente para executá-la. Talvez o método de busca mais simples seja a busca
seqüencial ou linear, no qual cada item do vetor é examinado por vez e comparado ao item
que se está procurando, até ocorrer uma coincidência. Se a lista não estiver organizada, é
possível que a busca linear seja a única maneira de localizar algo dentro dela. Entretanto, em
método desse jamais seria usado para localizar um nome no catálogo de telefones. Em vez
disso, o catálogo seria aberto numa página qualquer e os nomes pertencentes a essa página
seriam examinados. Como os nomes encontram-se em ordem alfabética, esse exame
determinaria se a busca deve continuar na primeira ou segunda metade do catálogo.
Apliquemos essa idéia à pesquisa em vetores. Se um vetor contiver somente um
elemento, o problema será simples. Caso contrário, compare o item sendo procurado ao item
posicionado no meio do vetor. Se forem iguais, a busca terminou com sucesso. Se o elemento
do meio for maior que o elemento sendo procurado, o processo de busca será repetido na
primeira metade do vetor (porque esse item deve estar na primeira metade); caso contrário, o
processo será repetido na segunda metade. Observe que, toda vez que uma comparação é
feita, o número de elementos a pesquisar é cortado pela metade. Por causa da divisão do vetor
a ser pesquisado em duas partes iguais, esse método de busca é chamado busca binária.
Observe que definimos de modo muito natural uma busca binária recursivamente. Se o
item sendo procurado não for igual ao elemento do meio do vetor, as instruções serão
pesquisar um subvetor usando o mesmo método. Dessa forma, o método de busca é definido
 2

em termos de si mesmo com um vetor menor como entrada. Temos certeza de que o processo
terminará porque os vetores de entrada ficarão cada vez menores, e a busca em um vetor de
um único elemento é definida não recursivamente, uma vez que o elemento do meio desse
vetor é seu único elemento.
Sabemos que se o elemento procurado não estiver contido no vetor os índices que
apontam para as extremidades esquerda (e) e direita (d) do vetor se cruzam. A solução
recursiva para procurar num vetor a classificado um elemento x entre a[e] e a[d] é dada por:
 solução trivial: se e > d então retorne –1
caso contrário, m = (e + d) / 2, se x == a[m] então retorne m
 solução geral: se x < a[m] então procurar x em a[e] até a[m-1]
senão procurar x em a[m+1] até a[d]
O algoritmo retornará um índice de a, de modo que a[indice] seja igual a x, se esse
índice existir entre e e d. Se x não for encontrado nessa parte do vetor, a função buscabin
retornará –1 (em C, não pode existir em elemento a[-1]). Supondo a um vetor de inteiros, a
função buscabin ficaria assim:
int buscabin(int x, int a[], int e, int d) {
int m;
if(e > d) return –1;
m = (e + d) / 2;
if(x == a[m]) return m;
if(x < a[m]) return (buscabin(x,a,e,m-1));
else return (buscabin(x,a,m+1,d));
}

2. Ordenação
A técnica de ordenação ilustra claramente como um dado problema pode ser resolvido
por meio de diferentes algoritmos, cada qual apresentando vantagens e desvantagens, as quais
devem ser consideradas sob o ângulo da aplicação particular a que se destinam.
Em geral, entende-se a atividade de ordenação como sendo um processo de rearranjo
de um certo conjunto de objetos de acordo com um critério (ordem) específico. O objetivo da
ordenação é facilitar a localização dos membros de um conjunto de dados. Exemplos de casos
em que os objetos são ordenados podem ser encontrados em listas telefônicas, índices,
bibliotecas, dicionários, etc. e em quase todos os casos em que estejam colecionados objetos
sujeitos a procura e alteração.
Portanto, a ordenação é uma atividade relevante e essencial, sobretudo na área de
processamento de dados. De modo particular, a ordenação é um assunto ideal para se
demonstrar a grande diversidade de algoritmos que podem ser construídos de maneiras
extremamente variadas, porém, todos com o mesmo propósito, muitos dos quais funcionam
de modo perfeito sob determinadas circunstâncias, e a maioria dos quais apresentando
vantagens sobre os demais. Este assunto é ideal inclusive para demonstrar a necessidade de
uma análise do desempenho de algoritmos.
A dependência da escolha de um algoritmo quanto à estrutura de dados a ser
processada é tão forte no caso da ordenação que os métodos utilizados são, em geral,
classificados em duas categorias: ordenação de vetores e ordenação de arquivos. As duas
classes são freqüentemente chamadas de ordenação interna e externa porque os vetores são
 3

armazenados na memória “interna” do computador (memória principal), de acesso aleatório e

rápido, que apresentam uma velocidade muito alta enquanto os arquivos são armazenados em
memórias “externas” (memória secundária), de acesso lento, porém com alta capacidade de
armazenamento. A importância desta distinção é que no caso de vetores, todos os elementos
do vetor estão “visíveis”, permitindo um acesso individual direto.
Entretanto, no caso de arquivos, somente um elemento (registro) é “visível”.
Evidentemente, tal restrição ocasiona sérias conseqüências no método a ser utilizado na
ordenação.

2.1 Ordenação de Vetores

O registro mais importante a ser estabelecido em relação aos métodos de ordenação de

vetores corresponde ao uso econômico da memória disponível. Isto implica que a permutação
dos elementos, responsável por levar o elemento à ordem desejada, deve ser efetuada in situ,
ou seja, sem a utilização de um vetor auxiliar. Portanto, são de menor interesse os métodos
que efetuam o transporte físico dos elementos de um vetor A para um vetor resultante B.
Assim, restringindo-se a escolha dos métodos, dentre as inúmeras soluções possíveis, de
acordo com o critério de economia de memória, pode-se promover uma primeira classificação
de acordo com a eficiência do mesmo em relação à economia de tempo. Uma boa medida de
eficiência é obtida contando-se o número C de comparações necessárias das chaves e o
número M de movimentos dos elementos. Estes números são funções do número n de
elementos a serem ordenados. Enquanto bons algoritmos de ordenação exigem cerca de
n*log(n) comparações, serão discutidos em primeiro lugar, algumas técnicas simples de
ordenação, chamadas métodos diretos, todos os quais exigindo um número de comparações
das chaves da ordem de n2.
Os métodos de ordenação que ordenam os elementos in situ podem ser classificados
em três principais categorias, de acordo com o método empregado em seu projeto:
a) Ordenação por inserção.
b) Ordenação por seleção;
c) Ordenação por permutação;
Estes três princípios serão, agora, examinados e comparados.

2.1.1 Ordenação por Inserção

Neste método, os elementos são conceitualmente divididos em uma seqüência destino

a0 ... ai-1 e uma seqüência fonte ai ... an-1. Em cada passo, iniciando-se com i=1 e
incrementando-se i de uma em uma unidade, o i-ésimo elemento da seqüência vai sendo
retirado e transferido para a seqüência destino, e inserido na posição apropriada. A Figura 1
mostra o processo de ordenação por inserção direta sendo aplicado sobre oito números
escolhidos aleatoriamente.

A 44 55 12 42 6 94 18 67
i=1 44 55 12 42 6 94 18 67

i=2 12 44 55 42 6 94 18 67

i=3 12 42 44 55 6 94 18 67

i=4 6 12 42 44 55 94 18 67
 4

i=5 6 12 42 44 55 94 18 67

i=6 6 12 18 42 44 55 94 67

i=7 6 12 18 42 44 55 67 94
Figura 1: Exemplo de uma ordenação pelo método de inserção direta

No processo de se encontrar, de fato, o local apropriado para o elemento, é

conveniente utilizar, de modo alternado, operações de comparação e de movimentação,
examinando cuidadosamente o elemento a ser inserido na posição correta, e comparando com
o próximo elemento aj, e, então, efetuando a inserção do elemento ou efetuando a
movimentação do elemento aj para a direita, prosseguindo-se, em seguida, para a esquerda no
tratamento dos elementos pelo algoritmo. Note-se que existem duas condições distintas que
causam o término deste processo de análise:
1. Um elemento aj é encontrado com uma chave de valor menor ou igual do que a chave do
elemento a ser inserido;
2. A extremidade esquerda da seqüência destino é atingida.
O algoritmo completo deste método está formulado abaixo:
/* Rotina para ordenar um vetor de n elementos pelo método de
Inserção Direta */
void InsercaoDireta(int a[], int n) {
int i; // Passos do algoritmo
int j; // Índice do vetor
int x; // Elemento a ser inserido

for(i = 1; i < n; i++) {

x=a[i];
j=i-1;
while(j >= 0 && a[j] > x) {
a[j+1]=a[j--]; // Desloca o elemento para a direita
}
a[j+1]=x; // Insere o elemento na posição correta
}
}

Eficiência da inserção direta:

Mínimo Médio Máximo

Comparações n-1 (n2 + n – 2) / 4 (n2 - n) / 2 - 1
Movimentos 2 (n –1) (n2 + 9n –10) / 4 (n2 + 3n – 4) / 2

2.1.2 Ordenação por Seleção

Este método é baseado no seguinte princípio:

1. Selecionar o elemento que apresenta a chave de menor valor;
2. Trocá-lo com o primeiro elemento da seqüência;
3. Repetir estas operações, envolvendo agora apenas os n-1 elementos restantes, depois os n-
2, e assim por diante, até restar um único elemento, o maior deles.
 5

O processo de ordenação por inserção é mostrado em um exemplo, com os mesmos

números da Figura 1, na Figura 2.

A 44 55 12 42 6 94 18 67

i=0 6 55 12 42 44 94 18 67

i=1 6 12 55 42 44 94 18 67

i=2 6 12 18 42 44 94 55 67

i=3 6 12 18 42 44 94 55 67

i=4 6 12 18 42 44 94 55 67

i=5 6 12 18 42 44 55 94 67

i=6 6 12 18 42 44 55 67 94
Figura 2: Exemplo de uma ordenação pelo método de seleção direta

O algoritmo que implementa o método seleção direta é mostrado abaixo:

/* Rotina para ordenar um vetor de n elementos pelo método de
Seleção Direta */
void SelecaoDireta(int a[], int n) {
int i; // Passos do algoritmo
int j; // Índice do vetor
int k; // Índice do menor elemento da seqüência
int menor; // Menor elemento da seqüência

for(i = 0; i < n-1; i++) {

k = i;
menor = a[k];
for(j = i+1; j < n; j++) { // procura o menor elemento da seqüência
if(a[j] < menor) {
k = j;
menor = a[k];
}
}
//troca o menor elemento com o primeiro da seqüência}
a[k] = a[i];
a[i] = menor;
}
}

Eficiência da seleção direta:

Mínimo Médio Máximo

Comparações (n2 – n) / 2 (n2 – n) / 2 (n2 – n) / 2
Movimentos 3 (n –1) (n2 + 9n –10) / 4 n2 / 4 + 3 (n – 1)
 6

2.1.3 Ordenação por Permutação

Raramente, é possível efetuar de maneira totalmente clara a classificação de um

método de ordenação. Ambos os métodos discutidos anteriormente podem ser vistos também
como ordenações por permutação. Nesta seção, entretanto, será apresentado um método em
que a permutação entre dois elementos é a principal característica do processo. O algoritmo
subsequente de permutação direta é baseado na comparação e permutação de pares de
elementos adjacentes até que todos tenham sido ordenados.
Neste método, efetuam-se varreduras repetidas sobre o vetor, deslocando-se, a cada
passo, para a sua extremidade direita, o maior dos elementos do conjunto que restou. Se, para
uma troca, o vetor for visualizado na posição vertical ao invés de na horizontal, e com o
auxílio da imaginação, os elementos formem bolhas em um tanque de água, com densidades
inversamente proporcionais ao valor de suas respectivas chaves, então cada varredura
efetuada sobre o vetor resultaria na ascensão de uma bolha para o seu nível apropriado, de
acordo com sua densidade. Este método é conhecido como Bubblesort (ordenação por
bolhas). Sua forma mais simples é mostrada na rotina abaixo:
/* Procedimento que ordena o vetor pelo método de ordenação Bubblesort */
void BubbleSort(int a[], int n) {
int i; // Passos do algoritmo de ordenação
int j; // Índice do vetor}
int aux; // Variável auxiliar para a permutação de elementos

for(i = 0; i < n-1; i++) {

for(j = 0; j < n-1-i; j++) {
if(a[j] > a[j+1]) { // Se o elemento a esquerda for maior que o a
direita
aux = a[j]; // Troca-se a posição destes elementos
a[j] = a[j+1];
a[j+1] = aux;
}
}
}
}

A 44 55 12 42 6 94 18 67

i=0 44 12 42 6 55 18 67 94

i=1 12 42 6 44 18 55 67 94

i=2 12 6 42 18 44 55 67 94

i=3 6 12 18 42 44 55 67 94

i=4 6 12 18 42 44 55 67 94

i=5 6 12 18 42 44 55 67 94

i=6 6 12 18 42 44 55 67 94
Figura 3: Exemplo de uma ordenação pelo método Bubblesort

Este algoritmo sugere, por si próprio, alguns aperfeiçoamentos. No exemplo da Figura

3, em que são ordenados os mesmos números das Figuras 1 e 2, pode-se observar que os três
 7

últimos passos do algoritmo não afetaram a ordem dos elementos do vetor, pois estes já
encontravam-se ordenados. Uma técnica óbvia para melhorar este algoritmo consiste em
manter uma indicação informando se houve ou não ocorrência de uma permutação, para
determinar precocemente o término do algoritmo. Sendo assim, o algoritmo para ordenação
bolha aperfeiçoado ficaria assim:
/* Rotina para ordenar um vetor de n elementos pelo método Bolha aperfeiçoado */
void BubbleSort2(int a[], int n) {
int i = 0; // Passos do algoritmo de ordenação
int j; // Índice do vetor
int aux; // Variável auxiliar para a permutação de elementos
int trocou = TRUE; // Indica se houve permutação em um passo
while(trocou && i < n-1) {
trocou = FALSE;
for(j = 0; j < n-1-i; j++) {
if(a[j] > a[j+1]) { // Se o elemento a esquerda for maior que o a
direita
aux = a[j]; // Troca-se a posição destes elementos
a[j] = a[j+1];
a[j+1] = aux;
trocou = TRUE; // sinaliza que houve uma troca
}
}
i++;
}
}

Entretanto, mesmo esta melhoria pode ser por sua vez aperfeiçoada, guardando-se não
a simples informação da ocorrência de uma permutação, mas a posição (índice) k do vetor em
que ocorreu a última permutação realizada. Por exemplo, é evidente que todos os pares de
elementos adjacentes de índice maior que k já se encontram na ordem desejada. Portanto, a
partir deste índice, o prosseguimento dos exames pode ser interrompido, ao invés de se
prosseguir até o limite superior n – i predeterminado. Entretanto, um programador cuidadoso
percebe uma assimetria peculiar: uma única bolha, colocada de modo incorreto na
extremidade esquerda de um vetor, cujos demais elementos estejam ordenados será
posicionada corretamente em um único passo, mas um elemento incorretamente posicionado
na extremidade direita irá deslocar-se de apenas uma posição por vez em direção a sua
posição correta. Por exemplo, o vetor
94 06 12 18 42 44 55 67
é ordenado pelo método Bubblesort aperfeiçoado em um único passo, mas o vetor
12 18 42 44 55 67 94 06
requer sete passos para a sua ordenação. Esta assimetria não natural sugere uma segunda
melhoria: alterar a direção dos sucessivos passos de ordenação. O algoritmo resultante desta
prática se chama Shakesort (Ordenação por agitação).
Seu comportamento é ilustrado na Figura 4, aplicando-se o algoritmo para as mesma
oito chaves que foram utilizadas na Figura 3.
 8

E= 0 0 1 1 3
D= 7 6 6 3 3
direção =     
44 44 06 06 06
55 12 44 12 12
12 42 12 42 18
42 06 42 18 42
06 55 18 44 44
94 18 55 55 55
18 67 67 67 67
67 94 94 94 94

Figura 4: Exemplo de aplicação do Shakesort

/* Rotina para ordenar um vetor de n elementos pelo método Shakesort */

void ShakeSort(int a[], int n) {
int j; // Índice do vetor
int k = 0; // Indica a posição da última permutação
int e = 0,d = n-1; // Limites esquerdo e direito do vetor
int aux; // Variável auxiliar para a permutação de elementos

do {
for(j = e; j < d; j++) {
if(a[j] > a[j+1]) { // se o elemento a esquerda for maior que o a
direita
aux = a[j]; // Troca-se a posição destes elementos
a[j] = a[j+1];
a[j+1] = aux;
k = j; // sinaliza a posição da última troca
}
}
d = k;
for(j = d; j > e; j--) {
if(a[j-1] > a[j]) {
aux = a[j-1]; // troca-se a posição destes elementos
a[j-1] = a[j];
a[j] = aux;
k = j; // sinaliza a posição da última troca
}
}
e = k;
}while(e < d);
}

Eficiência da permutação direta (Bubblesort):

 9

Mínimo Médio Máximo

Comparações (n2 – n) / 2 (n2 – n) / 2 (n2 – n) / 2
Movimentos 0 3 (n2 – n) / 4 3 (n2 – n) / 2

3. Métodos Sofisticados de Ordenação

3.1 Ordenação por Inserção através de Incrementos Decrescentes –

Shellsort

Um refinamento do método de ordenação por inserção direta foi proposto por Donald
L. Shell em 1959. O método, chamado Shellsort, será explicado e seu funcionamento será
demonstrado através do exemplo dos oito elementos utilizados nos casos anteriores.
O Shellsort explora o fato de que o método de inserção direta apresenta desempenho
aceitável quando o número de chaves é pequeno e/ou estas já possuem uma ordenação parcial.
De fato, como o desempenho do método é quadrático, se dividirmos o vetor em h segmentos,
de tal forma que cada um possua aproximadamente n/h chaves e classificarmos cada
segmento separadamente, teremos, para cada um deles um desempenho em torno de (n/h)2.
Para classificarmos todos os h segmentos, o desempenho será proporcional a h x (n/h)2 = n2/h.
Poder-se-ia querer saber em primeiro lugar se a necessidade de vários passos de
ordenação, cada qual envolvendo todos os elementos do vetor, introduzirá mais complexidade
(trabalho) do que eficiência ao algoritmo. Entretanto, cada avanço na ordenação de uma
cadeia, ou envolve relativamente poucos elementos, ou então os elementos já estão quase
todos ordenados exigindo, portanto, um número de rearranjos comparativamente menor.
Para implementar o método, o vetor a[n] é dividido em segmentos, assim formados:
 Segmento 1: a[0], a[0+h], a[0+2h], ...
 Segmento 2: a[1], a[1+h], a[1+2h], ...
 Segmento 3: a[2], a[2+h], a[2+2h], ...
 ...
 Segmento h: a[h-1], a[h-1+h], a[h-1+2h], ...
onde h é um incremento. Inicialmente, consideraremos incrementos iguais a potências inteiras
de 2.
Num primeiro passo, para um certo h inicial, os segmentos assim formados são
classificados por inserção direta. Num segundo passo, o incremento h é diminuído (a metade
do valor anterior, se este era uma potência inteira de 2), dando origem a novos segmentos, os
quais também serão classificados por inserção direta.
O processo se repete até que h=1. Quando for feita uma classificação com h=1, o
vetor estará classificado. Observe que quando h=1, o método se confunde com o da inserção
direta.
A Figura 5 mostra o funcionamento do método Shellsort.
 10

A 44 55 12 42 6 94 18 67

h=4 44 55 12 42 6 94 18 67

h=2 6 55 12 42 44 94 18 67

h=1 6 42 12 55 18 67 44 94

Vetor ordenado 6 12 18 42 44 55 67 94

Figura 5: Exemplo de uma ordenação pelo método Shellsort

É óbvio que qualquer seqüência de incrementos seja aceitável, contanto que a última
seqüência seja unitária, uma vez que, no pior caso, o último passo de ordenação deverá
efetuar todo o trabalho. Entretanto, é menos óbvio que o método de incrementos decrescentes
venha a produzir resultados ainda melhores adotando-se incrementos que não sejam potências
de 2. Segundo pesquisadores renomados, como Donald Knuth e Niklaus Wirth, os valores dos
incrementos não devem ser múltiplos uns dos outros. Isto evitará o fenômeno, evidente no
exemplo mostrado acima, em que cada passo de ordenação combina duas cadeia entre as
quais anteriormente não havia nenhuma interação. É de fato, desejável que ocorra o maior
número possível de interações entre as diversas cadeias. Uma das seqüências recomendadas
por Knuth é a seguinte (escrita em ordem inversa):
1, 3, 7, 15, 31, ...
onde, h = 2k – 1, dado k como sendo o número de incrementos.
A implementação do método de incrementos decrescentes corresponde a uma
adaptação do método de inserção direta, de tal forma que, ao invés de classificar um vetor
cujos elementos se encontram contíguos uns aos outros, considera apenas os elementos do
vetor que pertencem a um certo segmento, ou seja, os elementos que iniciam numa dada
célula f e estão espaçados entre si a uma distância h.
void InsercaoShell(int a[], int n, int f, int h) {
int i; // Passos do algoritmo
int j; // Índice do vetor
int x; // Elemento a ser inserido

for(i = f+h; i < n; i+=h) {

x = a[i];
j = i-h;
while (j >= f && a[j] > x) {
a[j+h] = a[j]; // Desloca o elemento para a direita
j -= h;
}
a[j+h] = x; // Insere o elemento na posição correta
}
}
 11

A rotina ShellSort, a seguir, faz chamadas ao procedimento InsercaoShell. No

laço mais interno, são ordenados todos os segmentos definidos para um certo valor de h,
enquanto que o laço mais externo corresponde a cada um dos passos que caracterizam o
método.
void ShellSort(int a[], int n, int k) {
int i; // Número de segmentos
int h; // Tamanho do incremento
do {
h = pot(2,k) – 1;
for(i = 0; i < h; i++) {
InsercaoShell(a,n,i,h);
}
k--;
}while(k >= 1);
}

A função pot(x,y) usada na rotina ShellSort pode ser definida recursivamente

como segue abaixo:
int pot(int x, int y) {
if(y < 0) return NULL; // A função não é definida p/ expoentes negativos
return (y == 0 ? 1 : x * pot(x,y-1));
}

Análises matemáticas indicam que o esforço computacional necessário à ordenação de

n elementos é proporcional a n1,2 através do uso do algoritmo de Shelsort.
equenos.

3.2 Ordenação por Particionamento – Quicksort

O método apresentado a seguir foi proposto por Hoare, e é baseado no princípio da

permutação. Dado o fato de que o método Bolha (ou Bubblesort) apresenta-se, em média,
como o pior dentre os três algoritmos de ordenação direta, um fator substancial de melhoria
pode ser esperado. De fato, é surpreendente que a melhoria, baseada em permutações, a ser
discutida adiante, venha a produzir um método de desempenho tão espetacular, tanto que seu
inventor denominou-o de Quicksort ou “ordenação rápida”.
O algoritmo Quicksort é baseado no fato de que as permutações devem ser
preferencialmente empregadas para pares de elementos que guardem entre si distâncias
grandes, com a finalidade de se conseguir uma eficiência maior. Admita-se que sejam
fornecidos n elementos em ordem inversa de suas chaves. É possível ordená-las com n/2
permutações tomando-se primeiramente os elementos das extremidades à direita e à esquerda
e convergindo gradualmente para o centro, pelos dois lados. Obviamente, isto é possível se os
elementos estiverem exatamente na ordem inversa.
Dado o seguinte algoritmo:
 escolha-se arbitrariamente um elemento (denominado x);
 o vetor é varrido da esquerda para a direita até que seja encontrado um elemento a i > x;
 sendo então varrido da direita para a esquerda até que seja encontrado um elemento a j < x;
 nesta ocasião, os dois elementos serão permutados, e este processo de varredura e
 12

permutação continua até que os dois deslocamentos se encontrem em algum lugar

intermediário do vetor.
O resultado desta prática é um vetor parcialmente ordenado, onde a partição esquerda
contém apenas chaves cujos valores são menores (ou iguais) a x e a partição direita, apenas
chaves cujos valores são maiores (ou iguais) a x. Este processo de particionamento é a seguir
desenvolvido, na forma de uma rotina.
void particao(int a[], int n) {
int i = 0; // Índice esquerdo
int j = n-1; // Índice direito
int x; // Elemento mediano do vetor
int aux; // Variável auxiliar para troca

x = a[(i+j) / 2];
do {
while (a[i] < x) i++;
while (x < a[j]) j--;
if(i <= j) {
aux=a[i];
a[i++]=a[j];
a[j--]=aux;
}
while(i <= j);
}

Como exemplo, se for selecionada a chave 42 que está no ponto médio do vetor como
sendo o elemento x de referência para comparação, então o vetor de chaves:
44 55 12 42 6 94 18 67

exigirá as permutações 4418 e 556 para produzir o vetor particionado:

18 6 12 42 55 94 44 67

e os valores finais dos índices i=4 e j=2. As chaves a0 ... ai-1 são menores ou iguais à chave
x=42, e as chaves aj+1 ... an-1 são maiores ou iguais à chave x. Consequentemente, surgem as
seguintes partições:
 Partição esquerda: 0  k < i: ak  x
 Partição direita: j < k < n: x  ak
É necessário relembrar, no entanto, que o objetivo almejado não é só o de encontrar
partições do vetor original, mas também ordená-lo. Contudo, é muito pequeno o passo que
leva à ordenação a partir do particionamento: após ter sido particionado o vetor, aplica-se o
mesmo processo para as partições oriundas de cada uma das partições obtidas, e assim por
diante, até que todas as partições consistam de apenas um único elemento. Este algoritmo é
descrito na rotina QuickSort abaixo:
void QuickSort(int a[], int e, int d) {
int i = e; // Índice esquerdo
int j = d; // Índice direito
int x; // Elemento mediano do vetor
int aux; // Variável auxiliar para troca
x = a[(i+j) / 2];
do {
while (a[i] < x) i++;
 13

while (x < a[j]) j--;

if(i <= j) {
aux=a[i];
a[i++]=a[j];
a[j--]=aux;
}
while(i <= j);
if(e < j) QuickSort(a,e,j);
if(i < d) QuickSort(a,i,d);
}

A rotina QuickSort ativa recursivamente a si própria.

Referências
 WIRTH, N.. Algoritmos e Estruturas de Dados. Rio de Janeiro: Prentice-Hall do Brasil,
1989.
 AZEREDO, Paulo A.. Métodos de Classificação de Dados e Análise de suas
Complexidades. Editora Campus, 1996.
 KNUTH, D.E.. The Art of Computer Programming: sorting and searching. Vol. 3,
Addison Wesley, 2000.
 TENENBAUM, A.M.; LANGSAM, Y.; AUGENSTEIN, M.J.. Estruturas de Dados
Usando C. Makron Books, 1995.