Unidade 1

Prévia do material em texto

Fundamentos de 
Estruturas de Dados
Material Teórico
Responsável pelo Conteúdo:
Prof.ª Dr.ª Cristiane Camilo Hernandez
Revisão Textual:
Prof. Me. Claudio Brites
Algoritmos de Ordenação e Recursividade
• Introdução;
• Ordenação por Trocas – Bubble Sort;
• Ordenação por Seleção – Selection Sort;
• Ordenação por Inserção – Insertion Sort;
• Recursividade.
• Compreender o conceito de ordenação;
• Apresentar algoritmos de ordenação em pseudocódigo e em C#;
• Apresentar o conceito de recursão.
OBJETIVOS DE APRENDIZADO
Algoritmos de Ordenação
e Recursividade
Orientações de estudo
Para que o conteúdo desta Disciplina seja bem 
aproveitado e haja maior aplicabilidade na sua 
formação acadêmica e atuação profissional, siga 
algumas recomendações básicas:
Assim:
Organize seus estudos de maneira que passem a fazer parte 
da sua rotina. Por exemplo, você poderá determinar um dia e 
horário fixos como seu “momento do estudo”;
Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma 
alimentação saudável pode proporcionar melhor aproveitamento do estudo;
No material de cada Unidade, há leituras indicadas e, entre elas, artigos científicos, livros, vídeos e 
sites para aprofundar os conhecimentos adquiridos ao longo da Unidade. Além disso, você tam-
bém encontrará sugestões de conteúdo extra no item Material Complementar, que ampliarão 
sua interpretação e auxiliarão no pleno entendimento dos temas abordados;
Após o contato com o conteúdo proposto, participe dos debates mediados em fóruns de discus-
são, pois irão auxiliar a verificar o quanto você absorveu de conhecimento, além de propiciar o 
contato com seus colegas e tutores, o que se apresenta como rico espaço de troca de ideias e 
de aprendizagem.
Organize seus estudos de maneira que passem a fazer parte 
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Mantenha o foco! 
Evite se distrair com 
as redes sociais.
Determine um 
horário fixo 
para estudar.
Aproveite as 
indicações 
de Material 
Complementar.
Procure se alimentar e se hidratar quando for estudar; lembre-se de que uma 
Não se esqueça 
de se alimentar 
e de se manter 
hidratado.
Aproveite as 
Conserve seu 
material e local de 
estudos sempre 
organizados.
Procure manter 
contato com seus 
colegas e tutores 
para trocar ideias! 
Isso amplia a 
aprendizagem.
Seja original! 
Nunca plagie 
trabalhos.
UNIDADE Algoritmos de Ordenação e Recursividade
Contextualização
Uma boa razão para estudar algoritmos de ordenação é que eles ilustram algumas 
abordagens muito criativas na resolução de problemas. Por exemplo, o algoritmo de 
ordenação por inserção adapta uma técnica utilizada por jogadores de baralho para 
arrumar um jogo de cartas. Alguns algoritmos utilizam a técnica de dividir e conquis-
tar para separar um grande problema em subproblemas, o que torna o problema 
melhor gerenciável e facilita a sua resolução.
Ordenar dados é um raciocínio comum, mas em computação constituem obje-
tos de estudos profundos, pois lidar com um volume de dados muito grande é algo 
complexo. Ou seja, organizar uma lista de dados de forma lógica facilita a busca por 
um dado específico.
Nesta Unidade, conheceremos os algoritmos de ordenação por trocas (Bubble 
Sort), a ordenação por seleção (Selection Sort), ordenação por inserção (Insertion 
Sort) e ordenação rápida (Quick Sort), a lógica de cada um deles representada na 
forma de pseudocódigo, a aplicação em vetor e o código em C# correspondente. 
Antes de apresentarmos o conceito do algoritmo de ordenação rápida, faz-se ne-
cessário o aprendizado do conceito de recursão.
Vamos começar!
8
9
Introdução
Na disciplina de estrutura de dados, a ordenação é o processo pelo qual um con-
junto de dados ou objetos similares é colocado em ordem crescente ou decrescente. 
A ordenação, realizada de maneira eficiente, é essencial para o funcionamento e a 
funcionalidade de sistemas em diversos seguimentos. 
Ainda que muitas linguagens forneçam utilitários de ordenação, é muito impor-
tante estudar esses algoritmos porque eles ilustram diversas formas bem conheci-
das de resolver problemas de ordenação, cada um com seus próprios méritos. Você 
deve saber como eles são escritos a fim de que possa reproduzi-los caso necessite 
utilizá-los em linguagens que não possuem utilitários de ordenação.
Estudaremos nesta unidade os conceitos dos algoritmos de ordenação, a lógica 
de cada um deles na forma de pseudocódigo e os seus respectivos códigos em C#. 
Alguns desses algoritmos utilizam o conceito de recursividade, que será aqui tam-
bém abordado.
Devido às várias aplicações existentes, encontramos na literatura diferentes ló-
gicas desses algoritmos de ordenação e muitos dessas consistem em basicamente 
realizar comparações sucessivas e trocar elementos de posição. O objetivo da orde-
nação é facilitar a localização de determinado elemento. 
Apresentaremos a seguir os algoritmos de ordenação e ilustraremos todos eles uti-
lizando um vetor de valores inteiros. Para simplificar, porém, podemos aplicá-los em 
qualquer estrutura de dados linear, cujo conteúdo será abordado nas próximas unidades.
Ordenação por Trocas – Bubble Sort
O algoritmo de ordenação por trocas é considerado o mais simples e o que pos-
sui a lógica de implementação quase intuitiva, essas características fazem com que 
ele seja o mais conhecido entre os programadores. 
Esse algoritmo consiste em percorrer várias vezes o conjunto de dados – consi-
deremos um vetor, embora sua lógica seja aplicável a qualquer outra estrutura de 
dados que se deseja ordenar. C ada vez que o algoritmo percorre o vetor, compara 
o conteúdo de um elemento com o seu sucessor, ou seja, o conteúdo da posição 
k com o conteúdo da posição k+1, e troca esses conteúdos entre si de posição, 
caso não estejam na ordem desejada (crescente ou decrescente). Esse percurso de 
comparações entre pares atua em todo o vetor, fazendo com que: da primeira vez 
que terminar de percorrê-lo, o maior valor (ou menor) termine na última posição; 
na segunda vez que percorrer, o segundo maior (ou menor) estará na penúltima 
posição; e assim por diante.
9
UNIDADE Algoritmos de Ordenação e Recursividade
Bubble Sort: o algoritmo possui esse nome porque os menores valores (ou maiores) sobem 
como bolhas para o topo do vetor (em direção à primeira posição, a “superfície”), enquanto 
os valores maiores (ou menores) descem para o fundo do vetor (última posição do vetor). 
Ex
pl
or
Observe que para você construir de forma correta a lógica desse algoritmo, o 
mesmo precisará, a cada vez percorrer todo o vetor, deslocar o conteúdo de um 
elemento para a posição final, isso é, o conteúdo é ordenado com relação aos de-
mais na ordem crescente ou decrescente. Assim, um vetor com N elementos terá, 
após a primeira vez que o algoritmo percorrer todo o vetor, um conteúdo ordenado 
e N-1 elementos por ordenar. Na segunda vez em que percorrer, dois conteúdos 
ordenados e N-2 elementos por ordenar, e assim sucessivamente. 
Para que você entenda como a lógica desse algoritmo de ordenação pode ser 
desenvolvida na prática e aplicada, apresentamos a seguir o seu pseudocódigo. 
Nesse consideraremos a ordenação crescente dos valores armazenados em um 
vetor do tipo inteiro de tamanho N, a escrita do pseudocódigo no escopo de um 
método e a utilização do atributo length que obtém o tamanho do vetor passado 
como parâmetro.
void Bubble_Sort (valores [ ]: inteiro) {
 i,k, aux: inteiro 
 para (i = 0; i < valores.length - 1; i++) {
para (k = 0; k < valores.length - 1 - i; k++) {
 se (valores [ k ] > valores [ k + 1 ]) {
 aux = valores [ k ] 
 valores [ k ] = valores [ k + 1 ]
 valores [ k + 1 ] = aux
 }
}
 }
}
Na prática, para que você entenda passo a passo a lógica explicada anteriormente, 
considere um vetor contendo cinco números armazenados:
0 1 2 3 4
60 42 83 75 27
Cada vez que oalgoritmo percorrer todo o vetor, no pseudocódigo isso se refere à 
primeira estrutura de repetição, consideraremos um passo. Assim, aplicando o algorit-
mo de ordenação por trocas no vetor acima, observaremos o seguinte comportamento:
10
11
Passo 1 (i = 0)
k Pares Adjacentes Comparação Troca Depois da Troca
0 60 42 83 75 27 60 > 42? Sim 42 60 83 75 27
1 42 60 83 75 27 60 > 83? Não
2 42 60 83 75 27 83 > 75? Sim 42 60 75 83 27
3 42 60 75 83 27 83 > 27? Sim 42 60 75 27 83
 
ordenado
 
Passo 2 (i = 1)
k Pares Adjacentes Comparação Troca Depois da Troca
0 42 60 75 27 83 42 > 60? Não
1 42 60 75 27 83 60 > 75? Não
2 42 60 75 27 83 75 > 27? Sim 42 60 27 75 83
 
ordenado
Passo 3 (i = 2)
k Pares Adjacentes Comparação Troca Depois da Troca
0 42 60 27 75 83 42 > 60? Não
1 42 60 27 75 83 60 > 27? Sim 42 27 60 75 83
 
ordenado
Passo 4 (i = 3) 
k Pares Adjacentes Comparação Troca Depois da Troca
0 42 27 60 75 83 42 > 27? Sim 27 42 60 75 83
 
ordenado
Resultado Final:
0 1 2 3 4
27 42 60 75 83
11
UNIDADE Algoritmos de Ordenação e Recursividade
Observe que o número de trocas realizadas depende do vetor a ser ordenado. 
Esse algoritmo de ordenação apresenta um excelente desempenho quando o ve-
tor está quase ordenado (o que raramente acontece), mas um desempenho muito 
insatisfatório quando não está quase ordenado ou a quantidade de valores armaze-
nados no vetor é grande.
O método em C# do algoritmo descrito anteriormente é apresentado a seguir:
Figura 1 – Método do algoritmo de ordenação por trocas em C#
Dependendo dos dados armazenados no vetor, o mesmo pode estar ordenado 
antes mesmo do algoritmo terminar de executar todos os passos. Assim, melhorias 
na lógica desse algoritmo são sugeridas a fim de diminuir o tempo computacional, 
como, por exemplo, terminar a execução quando nenhuma troca é realizada após 
percorrer o vetor.
Veja as variações do algoritmo de ordenação por trocas em: https://goo.gl/7GKodP
Uma animação mostrando o funcionamento do algoritmo por trocas otimizado está 
disponível em: https://goo.gl/CJJ6cH
Ex
pl
or
Ordenação por Seleção – Selection Sort
O algoritmo de ordenação por seleção, assim como o por trocas, é considerado 
simples. A lógica consiste, no primeiro percurso, em selecionar o conteúdo arma-
zenado na primeira posição do vetor e realizar comparações do valor selecionado 
com todos os valores que estão à sua direita. Nessas comparações, procura-se por 
um valor menor do que o valor selecionado (ordem crescente) ou maior (ordem 
decrescente), isso depende da ordem desejada. Caso um valor satisfaça à condição 
12
13
de ordenação desejada, guarda a posição de onde se encontra o menor valor (ou 
maior) e, ao terminar de percorrer o vetor, o menor (ou maior) valor é trocado de 
posição com o valor selecionado. 
No segundo percurso, seleciona o conteúdo armazenado na segunda posição 
do vetor e realiza as comparações desse valor com todos os outros que estão à sua 
direita; caso o valor satisfaça a condição de ordenação, guarda a posição desse e 
após percorrer todo o vetor, troca de posição o valor com o valor selecionado, e 
assim sucessivamente. Observe que, aplicando essa lógica, todos os números à 
esquerda do selecionado ficarão sempre ordenados.
Portanto, o conteúdo do valor selecionado está no índice i e os conteúdos das 
posições à direita estão nos índices i + 1 à N - 1, sendo N o número de elementos 
do vetor. 
Como a lógica desse algoritmo de ordenação pode ser desenvolvido na prática e 
aplicado em um vetor é apresentado a seguir. Nesse consideraremos a ordenação 
crescente dos valores armazenados em um vetor do tipo inteiro de tamanho N, a 
escrita do pseudocódigo no escopo de um método, a utilização do atributo length 
que obtém o tamanho do vetor passado como parâmetro e variáveis auxiliares.
void Selection_Sort (valores [ ]: inteiro) {
 i,k, menor, aux: inteiro 
 para (i = 0; i < valores.length-1; i++) {
menor = i
para (k = i+1; k < valores.length; k++) {
 se (valores [ k ] < valores [ menor ]) {
 menor = k 
 }
}
aux = valores [ menor ] 
valores [ menor ] = valores [ i ]
valores [ i ] = aux
 }
}
No pseudocódigo apresentado, temos a variável menor, que guarda o índice da posi-
ção corrente do elemento do vetor com o menor valor. Agora aplicaremos a lógica do 
algoritmo apresentada acima e, para isso, considere um vetor contendo cinco números 
inteiros armazenados:
0 1 2 3 4
20 3 35 11 2
13
UNIDADE Algoritmos de Ordenação e Recursividade
Cada vez que o algoritmo percorrer todo o vetor, consideraremos um passo 
– no pseudocódigo, refere-se à primeira estrutura de repetição. Assim, apli-
cando o método de ordenação por seleção no vetor acima, observaremos o 
seguinte comportamento:
Passo 1 (i = 0)
k Vetor Comparação Índice do menor valor Depois da Troca
1 20 3 35 11 2 3 < 20? Sim 1
2 20 3 35 11 2 35 < 3? Não 1
3 20 3 35 11 2 11 < 3? Não 1
4 20 3 35 11 2 2 < 3? Sim 4 2 3 35 11 20
 
ordenado
Passo 2 (i = 1)
k Vetor Comparação Índice do menor valor Depois da Troca
2 2 3 35 11 20 35 < 3? Não 1
3 2 3 35 11 20 11 < 3? Não 1
4 2 3 35 11 20 20 < 3? Não 1
 
ordenado
Passo 3 (i = 2)
k Vetor Comparação Índice do menor valor Depois da Troca
3 2 3 35 11 20 11< 35? Sim 3
4 2 3 35 11 20 20< 11? Não 3 2 3 11 35 20
 
ordenado
Passo 4 (i = 3) 
k Vetor Comparação Índice do menor valor Depois da Troca
4 2 3 11 35 20 20< 35? Sim 4 2 3 11 20 35
 
ordenado
Resultado Final:
0 1 2 3 4
2 3 11 20 35
14
15
Perceba, se o vetor estiver ordenado antes de iniciar a ordenação, nenhuma troca 
será necessária. Outra característica é que esse método é ineficiente em vetores grandes. 
Um método em C# do algoritmo mostrado anteriormente é apresentada a seguir:
Figura 2 – Método do algoritmo de ordenação por seleção em C#
Dependendo dos dados armazenados no vetor, o mesmo pode estar ordenado 
antes mesmo do algoritmo terminar de executar todos os passos, assim melhorias 
na lógica desse algoritmo são sugeridas a fim de diminuir o tempo computacional. 
Um exemplo é o de terminar a execução quando nenhuma troca for realizada após 
percorrer o vetor.
Aumente o seu conhecimento sobre esse algoritmo de ordenação em: https://goo.gl/diZHdm
A animação ilustra a lógica do algoritmo em: https://goo.gl/TKYuRbE
xp
lo
r
Ordenação por Inserção – Insertion Sort
A ordenação por inserção é baseada na técnica utilizada por jogadores de ba-
ralho para arrumar uma mão de cartas. O jogador mantém ordenadas as cartas 
que foram selecionadas até aquele momento. Quando o jogador seleciona uma 
nova carta, ele abre espaço para essa nova carta e, em seguida, a insere em sua 
15
UNIDADE Algoritmos de Ordenação e Recursividade
posição apropriada. O diagrama à esquerda da Figura 3 mostra uma mão de cartas 
(ignorando o naipe) após três cartas terem sido selecionadas. Se a próxima carta for 
um 8, ela deve ser inserida entre a 6 e a 10, mantendo a ordem numérica (diagrama 
do meio). Se a carta seguinte for um 7, ela deve ser inserida entre a 6 e a 8, como 
mostrado à direita da Figura 3.
Figura 3 – Selecionando uma mão de cartas de baralho
Considerando que se pretenda ordenar os valores de maneira crescente, a lógica 
dessa ordenação é a seguinte: da primeira vez que percorrer o vetor, o conteúdo 
do segundo elemento será comparado com o conteúdo do elemento que está antes 
dele; se o conteúdo do segundo elemento for menor do que o conteúdo do primeiro 
elemento, acontecerá uma troca de posição entre os elementos. Após a primeira 
vez que percorrer o vetor, os dois primeiros elementos do vetor estarão ordenados.
Na segunda vez, que percorrer o vetor, o conteúdo do terceiro elemento será 
comparado com os conteúdos dos elementos que aparecem antes dele (primeiro 
e segundo). Se o conteúdo do terceiro elemento for menor do que o conteúdo do 
primeiro elemento, ele será inserido na posição do primeiro elemento. Se o conte-
údo do terceiro elemento for maior do que o conteúdodo primeiro elemento, mas 
menor do que o segundo, ele será inserido na posição do segundo elemento. Se 
o conteúdo do terceiro elemento for maior do que ambos os elementos, ele será 
mantido na posição como está. Após a segunda vez que percorrer o vetor, os três 
primeiros elementos do vetor estarão ordenados.
Quando percorrer o vetor pela terceira vez, similarmente, o conteúdo do quarto 
elemento será comparado com os conteúdos dos elementos que aparecem antes 
dele (primeiro, segundo e terceiro elemento), então o mesmo procedimento será 
aplicado e o conteúdo desse elemento será inserido na posição correta. Após o ter-
ceiro passo, os conteúdos dos quatro primeiros elementos do vetor se encontram 
ordenados. Esse processo se repete até o último elemento do vetor.
Assim, para entender na prática como a lógica desse algoritmo de ordenação é 
aplicado em um vetor, a seguir, temos o algoritmo em pseudocódigo que aplica a 
ordenação por inserção de forma crescente em números do tipo inteiro em um vetor 
de tamanho N. O mesmo está no escopo de um método, utilizando o atributo length, 
que obtém o tamanho do vetor passado como parâmetro e variáveis auxiliares.
16
17
void Insection_Sort (valores [ ]: inteiro) {
i,k, aux: inteiro
para (i = 1; i < valores.length; i++) {
aux = valores[ i ]
k = i – 1
enquanto (k >= 0 e aux < valores[ k ] ) {
valores [ k+1 ] = valores [ k ]
k = k - 1
}
valores [ k+1] = aux
}
}
No pseudocódigo apresentado, temos a variável aux, que armazena o conteúdo 
que deseja que seja ordenado com relação aos valores armazenados à esquerda do 
vetor já ordenados. Agora aplicaremos a lógica do algoritmo apresentada acima, 
para isso, considere um vetor contendo cinco números inteiros armazenados:
0 1 2 3 4
5 3 4 6 2
Cada vez que o algoritmo percorrer todo o vetor, consideraremos um passo – no 
pseudocódigo, refere-se à primeira estrutura de repetição. Assim, aplicando o método 
de ordenação por inserção no vetor acima, observaremos o seguinte comportamento:
Passo 1 (i = 1)
k Vetor aux Comparação Depois da Troca
0 7 5 8 2 3 5 5 < 7? Sim 5 7 8 2 3
Passo 2 (i = 2)
k Vetor aux Comparação Depois da Troca
1 5 7 8 2 3 8 8 < 7? Não
17
UNIDADE Algoritmos de Ordenação e Recursividade
Passo 3 (i = 3)
k Vetor aux Comparação Depois da Troca
2 5 7 8 2 3 2 2 < 8? Sim
1 5 7 8 2 3 2 2 < 7? Sim
0 5 7 8 2 3 2 2 < 5? Sim 2 5 7 8 3
Passo 4 (i = 4) 
k Vetor aux Comparação Depois da Troca
3 2 5 7 8 3 3 3 < 8? Sim
2 2 5 7 8 3 3 3 < 7? Sim
0 2 5 7 8 3 3 3 < 5? Sim 2 5 7 8 3
Resultado Final:
0 1 2 3 4
2 3 5 7 8
O algoritmo de ordenação por inserção é eficiente, já que não é executado em 
condições predefinidas, usando estruturas de repetição para (for), mas sim uma es-
trutura enquanto (while), o que evita etapas extras depois que o vetor está ordenado. 
Um método em C# do algoritmo mostrado anteriormente é apresentado a seguir:
Figura 4 – Método do algoritmo de ordenação por seleção em C#
18
19
Embora a ordenação por inserção seja eficiente, assim como os algoritmos apre-
sentados anteriormente, se o vetor já estiver ordenado, o algoritmo executará a 
estrutura de repetição externa, exigindo assim que n passos sejam executados e 
nenhuma alteração no vetor é feita. 
Aumente o seu conhecimento sobre esse algoritmo de ordenação em: https://goo.gl/9UuWtL
A animação ilustra a lógica do algoritmo em: https://goo.gl/ZpEz8iE
xp
lo
r
Recursividade
Na área de resolução de problemas, um algoritmo que para resolver um proble-
ma divide-o em subproblemas mais simples (dividir para conquistar), cujas soluções 
requerem a aplicação dele mesmo, é chamado recursivo. Assim, um método é re-
cursivo quando ele chama a si mesmo, seja de forma direta ou indireta. Para que a 
recursão seja realizável, o subproblema deve ser semelhante ao problema original, 
porém uma versão ligeiramente mais simples ou menor. Como esse subproblema é 
parecido com o problema original, o método chama uma cópia nova dele próprio 
para trabalhar no problema menor, isso é conhecido como passo de recursão. Esse 
normalmente inclui a instrução return, pois seu resultado será combinado com re-
sultado do subproblema que o método resolveu para formar um resultado que será 
passado novamente para o método original.
Importante!
Um método recursivo requer uma chamada externa para ser invocado e uma condição de 
saída (critério de parada) para retornar ao mesmo ponto no qual foi realizada a chamada.
Importante!
Em geral, um método recursivo R pode ser expresso como uma composição for-
mada por um conjunto de comandos C (que não tem chamadas a R) e uma chamada 
(recursiva) à rotina R:
R = (C, R)
19
UNIDADE Algoritmos de Ordenação e Recursividade
Entretanto, pode-se ter também uma forma indireta de recursão, na qual os méto-
dos são conectados através de uma cadeia de chamadas sucessivas que acaba retor-
nando à primeira que foi chamada:
R1 = [C1, R2]
R2 = [C2, R3]
R3 = [C3, R4]
….
Rn = [Cn, Rn]
Assim, diz-se que um método R é indiretamente recursivo se ele contém uma 
chamada a outro método S, que por sua vez contém uma chamada direta ou indi-
reta a R. Note que a recursão nem sempre é explícita e, às vezes, pode ser difícil 
percebê-la através de uma simples leitura do método. O método de ordenação 
apresentado a seguir utiliza recursão.
Conheça mais sobre recursividade em: https://goo.gl/5kCq34
Ex
pl
or
Ordenação Rápida – Quick Sort
Na ordenação rápida, o vetor é particionado em dois utilizando um algoritmo re-
cursivo. Essa divisão é realizada de acordo com a escolha de um elemento denomi-
nado pivô e ocorre até que o vetor fique apenas com um valor, enquanto os demais 
ficam ordenados à medida que ocorre o particionamento. Assim, esse algoritmo 
utiliza a técnica de resolução de problemas chamada divisão e conquista, em que 
o problema é divido em problemas menores e cada uma dessas partes é resolvida 
utilizando o mesmo método de solução; as soluções menores são combinadas para 
se obter a solução do problema todo.
No processo de particionamento, obtém-se de um lado todos os conteúdos do 
vetor que sejam menores do que o pivô (por exemplo, lado esquerdo) e, do outro 
lado, todos os conteúdos que sejam maiores do que o pivô (por exemplo, lado di-
reito). Apesar de termos dois grupos de valores, isso não quer dizer que os valores 
estejam ordenados nesses grupos. Porém, só o fato de estarem separados pelo 
pivô em uma classificação de maior/menor que o pivô já facilita o trabalho de orde-
nação. A cada passo que um novo pivô é escolhido nos grupos e o particionamento 
é aplicado nesses grupos, os mesmos ficam mais ordenados do que antes, e é nesse 
processo que temos a recursividade.
20
21
Existem diferentes versões desse algoritmo, que selecionam o pivô de maneiras 
distintas. Sendo assim, temos algoritmos que escolhem o primeiro valor do vetor 
como pivô, já outros escolhes sempre o último valor como pivô (versão apresen-
tada no desenvolvimento do pseudocódigo e programa em C# abaixo), ou ainda 
versões que escolhem um valor aleatório como pivô ou que escolhem o valor posi-
cionado no meio do vetor como pivô. 
Para auxiliar no entendimento da lógica desse algoritmo de ordenação, a seguir, 
apresentamos o algoritmo em pseudocódigo que aplica a ordenação rápida de for-
ma crescente em números do tipo inteiro em um vetor de tamanho N. Esse está es-
crito no escopo de um método, que utiliza o conceito de recursividade, e o método 
praticado que retorna o índice para o pivô, ou seja, auxilia no particionamento do 
vetor. Os parâmetros de início e fim armazenam repectivamente o valor do índice 
inicial e final do vetor e variáveis auxiliares.
void Quick_Sort (valores [ ]: inteiro, inicio: inteiro, fi m: 
inteiro) {
posicao: inteiro
se (inicio < fi m) {
posicao = particao(valores, inicio, fi m)
Quick_Sort(valores, inicio, posicao-1) 
Quick_Sort(valores, posicao+1, fi m) 
}
}
inteiro particao (valores [ ]: inteiro, inicio: inteiro, fi m: 
inteiro) {
pivo, i,k, aux: inteiro
pivo =valores [ fi m ]
i = inicio - 1
para (k = inicio; k < fi m; k++) {
se (valores [ k ] < pivo) {
i = i + 1
aux = valores [ k ]
valores [ k ] = valores [ i ]
valores [ i ] = aux
}
}
21
UNIDADE Algoritmos de Ordenação e Recursividade
aux = valores[ i+1 ]
valores[ i+1 ] = valores[fim]
valores[ fim ] = aux
retorne (i + 1) 
}
Agora, vamos aplicar a lógica do algoritmo apresentada acima, para isso, consi-
dere um vetor contendo nove números inteiros:
Figura 5 – Exemplo de ordenação rápida
O algoritmo de ordenação rápido é a mehor opção para ordenar vetores gran-
des, pois o laço de repetição interno é simples. Um método em C# do algoritmo 
mostrado anteriormente é apresentada a seguir:
22
23
Figura 6 – Método do algoritmo rápido em C#
A recursão usada no método Quick_Sort é importante. Quando o método 
Quick_Sort é chamado, a função Particao e outras duas funções Quick_Sort são 
executadas. Ele continua até que o critério de parada seja satisfeito (inicio > fim).
A seguir, o algoritmo que seleciona e retorna o pivô, para que assim seja reali-
zada a operação de partição do vetor.
Figura 7 – Método do particionamento utilizado no algoritmo rápido em C#
23
UNIDADE Algoritmos de Ordenação e Recursividade
Esse é algoritmo apresenta o pior caso quando o vetor já está ordenado de for-
ma crescente ou decrescente. Isso acontece porque o pivô será o maior (crescente) 
ou menor (descrescente) valor do vetor. 
Veja a simulação do método de ordenação rápido em: https://youtu.be/tIYMCYooo3c
Ex
pl
or
Um algoritmo de ordenação rápida e a sua animação é ilustrada em: https://goo.gl/yCGWQf
Ex
pl
or
Agora que já entendemos a lógica de cada método de ordenação, mudaremos 
de nível. Nosso próximo passo será conhecer as estruturas de dados pilha na sua 
forma mais simples, para que possamos entender sua aplicação no desenvolvimento 
de jogos.
24
25
Material Complementar
Indicações para saber mais sobre os assuntos abordados nesta Unidade:
 Sites
Treinaweb
Conheça os principais algoritmos de ordenação.
https://goo.gl/tTEKmr
 Leitura
SORTIA – Um jogo para ensino de algoritmo de ordenação: estudo de caso na disciplina de estrutura de dados
https://goo.gl/wVyud6
LogicSort: um objeto de aprendizagem para o ensino de algoritmos de ordenação
https://goo.gl/9Zi3Mw
Recursividade e algoritmos de busca e ordenação
https://goo.gl/LfJn19
25
UNIDADE Algoritmos de Ordenação e Recursividade
Referências
ASCENIO, A. F. G.; ARAÚJO, G. S. Estrutura de Dados: algoritmos, análise da 
complexidade e implementações em Java e C/C++. São Paulo: Pearson Prentice 
Hall, 2010.
DEITEL, H. M. C# – Como Programar. 1. ed. São Paulo: Pearson Education, 2003.
KOFFMAN, E. B. Objetos, abstração, estruturas de dados e projeto usando 
C++. Rio de Janeiro: LTC, 2008.
PUGA, S.; RISSETI, G. Lógica de Programação e Estrutura de Dados, com Apli-
cações em Java. 3. ed. São Paulo: Pearson Education do Brasil, 2016.
26