Fonte: https://medium.com/@byron.

skoutaris/sorting-algorithms-fa96ce78006d

ALGORITMOS DE ORDENAÇÃO
Adaptado: Prof. André Backes Profª Otilia
 Objetivos
2

 Explicar a necessidade, escrever e executar algoritmos

básicos de ordenação, desenvolvidos a partir de exemplos
estabelecidos, para criar programas capazes de ordenar dados
através de métricas
determinadas.

Estrutura de Dados em C - Ordenação

 Situação Problema
3

 Imagine que estar trabalhando com um array de números

inteiros com n posições, e os valores contidos neste array se
encontram desordenados numericamente.
 Não seria vantajoso, para algumas operações, que estes
elementos estivessem ordenados?
 Como poderíamos ordenar esta coleção?
 Sabendo que há mais de uma maneira de fazer isso, qual seria o
método mais adequado?
Estrutura de Dados em C - Ordenação
 Conceitos básicos
4

 Ordenação
 Ato de colocar um conjunto de dados em uma determinada ordem
predefinida
 Fora de ordem
◼ 5, 2, 1, 3, 4
 Ordenado
◼ 1, 2, 3, 4, 5 OU 5, 4, 3, 2, 1
 Algoritmo de ordenação
 Coloca um conjunto de elementos em uma certa ordem

Estrutura de Dados em C - Ordenação

 Conceitos básicos
5

 A ordenação permite que o acesso aos dados seja feito de

forma mais eficiente
É parte de muitos métodos computacionais
◼ Algoritmos de busca, intercalação/fusão, utilizam ordenação como
parte do processo

◼ Aplicações em geometria computacional, bancos de dados, entre outras

necessitam de listas ordenadas para funcionar

Estrutura de Dados em C - Ordenação

 Conceitos básicos
6

 A ordenação é baseada em uma chave

A chave de ordenação é o campo do item utilizado para
comparação
◼ Valor armazenado em um array de inteiros
◼ Campo nome de uma struct
◼ etc

É por meio dela que sabemos se um determinado elemento está a

frente ou não de outros no conjunto
Estrutura de Dados em C - Ordenação
 Conceitos básicos
7

 Podemos usar qualquer tipo de chave

 Deve existir uma regra de ordenação bem-definida

 Alguns tipos de ordenação

 numérica

◼ 1, 2, 3, 4, 5

 lexicográfica (ordem alfabética)

◼ Ana, André, Bianca, Ricardo
Estrutura de Dados em C - Ordenação
 Conceitos básicos
8

 Independente do tipo, a ordenação pode ser

 Crescente

◼ 1, 2, 3, 4, 5

◼ Ana, André, Bianca, Ricardo

 Decrescente

◼ 5, 4, 3, 2, 1

◼ Ricardo, Bianca, André, Ana

Estrutura de Dados em C - Ordenação

 Conceitos básicos
9

 Os algoritmos de ordenação podem ser classificados como

de
 Ordenação interna
◼O conjunto de dados a ser ordenado cabe todo na memória principal
(RAM)

◼ Qualquer elemento pode ser imediatamente acessado

Estrutura de Dados em C - Ordenação

 Conceitos básicos
10

 Os algoritmos de ordenação podem ser classificados como

de
 Ordenação externa
◼O conjunto de dados a ser ordenado não cabe na memória principal

◼ Os dados estão armazenados em memória secundário (por exemplo, um

arquivo)

◼ Os elementos são acessados sequencialmente ou em grandes blocos

Estrutura de Dados em C - Ordenação

 Conceitos básicos
11

 Além disso, a ordenação pode ser estável ou não

 Um algoritmo de ordenação é considerado estável se a ordem dos
elementos com chaves iguais não muda durante a ordenação

O algoritmo preserva a ordem relativa original dos valores

Estrutura de Dados em C - Ordenação

 Conceitos básicos
12

 Exemplo
 Dados não ordenados
◼ 5a, 2, 5b, 3, 4, 1
◼ 5a e 5b são o mesmo número

 Dados ordenados
◼ 1, 2, 3, 4, 5a, 5b: ordenação estável
◼ 1, 2, 3, 4, 5b, 5a: ordenação não-estável
Estrutura de Dados em C - Ordenação
 Métodos de ordenação
13

 Os métodos de ordenação estudados podem ser divididos em

 Básicos

◼ Fácil implementação

◼ Auxiliam o entendimento de algoritmos complexos

 Sofisticados

◼ Em geral, melhor desempenho

Estrutura de Dados em C - Ordenação

 Bubble Sort
14

 Bubble-sort with Hungarian ("Csángó") folk dance

Estrutura de Dados em C - Ordenação

 Algoritmo Bubble Sort
15

 Também conhecido como ordenação por bolha

É um dos algoritmos de ordenação mais conhecidos que existem

 Remete a idéia de bolhas flutuando em um tanque de água em

direção ao topo até encontrarem o seu próprio nível (ordenação
crescente)

Estrutura de Dados em C - Ordenação

 Algoritmo Bubble Sort
16

 Funcionamento
 Compara pares de valores adjacentes e os troca de lugar se estiverem
na ordem errada
◼ Trabalha de forma a movimentar, uma posição por vez, o maior valor existente
na porção não ordenada de um array para a sua respectiva posição no array
ordenado

 Esse processo se repete até que mais nenhuma troca seja necessária
◼ Elementos já ordenados

Estrutura de Dados em C - Ordenação

 Algoritmo Bubble Sort
17

 Algoritmo

Troca dois valores

consecutivos no
vetor

Estrutura de Dados em C - Ordenação

 Algoritmo Bubble Sort
18

 Passo a passo
 1ºiteração do-while: encontra o maior valor e o movimenta até a
última posição

Estrutura de Dados em C - Ordenação

 Algoritmo Bubble Sort
19

 Passo a passo
 2º
iteração do-while: encontra o segundo maior valor e o
movimenta até a penúltima posição

Estrutura de Dados em C - Ordenação

 Algoritmo Bubble Sort
20

 Passo a passo
 Processo continua até todo o array estar ordenado

Estrutura de Dados em C - Ordenação

 Algoritmo Bubble Sort
21

 Vantagens
 Simples e de fácil entendimento e implementação

 Está entre os métodos de ordenação mais difundidos existentes

 Desvantagens
 Não é um algoritmo eficiente
◼ Sua eficiência diminui drasticamente a medida que o número de elementos no
array aumenta

◼ É estudado apenas para fins de desenvolvimento de raciocínio

Estrutura de Dados em C - Ordenação
 Algoritmo Bubble Sort
22

 Complexidade
 Considerando um array com N elementos, o tempo de execução é:
◼ O(N), melhor caso: os elementos já estão ordenados.

◼ O(N2), pior caso: os elementos estão ordenados na ordem inversa.

◼ O(N2), caso médio.

Estrutura de Dados em C - Ordenação

 Selection Sort
23

 Selection Sort: Itik-itik Dance

Estrutura de Dados em C - Ordenação

 Algoritmo Selection Sort
24

 Também conhecido como ordenação por seleção

É outro algoritmo de ordenação bastante simples

A cada passo ele seleciona o melhor elemento para ocupar aquela

posição do array
◼ Maior ou menor, dependendo do tipo de ordenação

◼ Na prática, possui um desempenho quase sempre superior quando

comparado com o bubble sort

Estrutura de Dados em C - Ordenação

 Algoritmo Selection Sort
25

 Funcionamento
 A cada passo, procura o menor valor do array e o coloca na primeira
posição do array
◼ Divide o array em duas partes: a parte ordenada, a esquerda do elemento
analisado, e a parte que ainda não foi ordenada, a direita do elemento.

 Descarta-se a primeira posição do array e repete-se o processo para a

segunda posição

 Isso é feito para todas as posições do array

Estrutura de Dados em C - Ordenação
 Algoritmo Selection Sort
26

 Algoritmo

Procura o
menor elemento
em relação a “i”
Troca os
valores da
posição atual
com a “menor”

Estrutura de Dados em C - Ordenação

 Algoritmo Selection Sort
27

 Passo a passo
 Paracada posição i, procura no restante do array o menor valor
para ocupá-la

Estrutura de Dados em C - Ordenação

 Algoritmo Selection Sort
28

 Passo a passo
 Paracada posição i, procura no restante do array o menor valor
para ocupá-la

Estrutura de Dados em C - Ordenação

 Algoritmo Selection Sort
29

 Vantagem
 Estável: não altera a ordem dos dados iguais

 Desvantagens
 Sua eficiência diminui drasticamente a medida que o número de
elementos no array aumenta
◼ Não é recomendado para aplicações que que envolvam grandes
quantidade de dados ou que precisem de velocidade

Estrutura de Dados em C - Ordenação

 Algoritmo Selection Sort
30

 Complexidade
 Considerando um array com N elementos, o tempo de execução é
sempre de ordem O(N2)
◼ A eficiência do selection sort não depende da ordem inicial dos elementos

 Melhor do que o bubble sort

◼ Apesar de possuírem a mesma complexidade no caso médio, na prática o
selection sort quase sempre supera o desempenho do bubble sort pois envolve
um número menor de comparações

Estrutura de Dados em C - Ordenação

 Insert Sort
31

 Insert-sort with Romanian folk dance

Estrutura de Dados em C - Ordenação

 Algoritmo Insertion Sort
32

 Também conhecido como ordenação por inserção

 Similar a ordenação de cartas de baralho com as mãos
◼ Pegue uma carta de cada vez e a insira em seu devido lugar, sempre
deixando as cartas da mão em ordem

Estrutura de Dados em C - Ordenação

 Algoritmo Insertion Sort
33

 Funcionamento
O algoritmo percorre o array e para cada posição X verifica se o
seu valor está na posição correta
◼ Isso é feito andando para o começo do array a partir da posição X e
movimentando uma posição para frente os valores que são maiores do
que o valor da posição X

◼ Desse modo, teremos uma posição livre para inserir o valor da posição X
em seu devido lugar
Estrutura de Dados em C - Ordenação
 Algoritmo Insertion Sort
34

 Algoritmo

Move as cartas maiores

para frente e insere na
posição vaga

Estrutura de Dados em C - Ordenação

 Algoritmo Insertion Sort
35

 Passo a passo
 Paracada posição i, movimenta os valores maiores uma posição
para frente no array

Estrutura de Dados em C - Ordenação

 Algoritmo Insertion Sort
36

 Passo a passo
 Paracada posição i, movimenta os valores maiores uma posição
para frente no array

Estrutura de Dados em C - Ordenação

 Algoritmo Insertion Sort
37

 Vantagens
 Fácil implementação
 Na prática, é mais eficiente que a maioria dos algoritmos de
ordem quadrática
◼ Como o selection sort e o bubble sort.

 Um dos mais rápidos algoritmos de ordenação para conjuntos

pequenos de dados
◼ Superando inclusive o quick sort
Estrutura de Dados em C - Ordenação
 Algoritmo Insertion Sort
38

 Vantagens
 Estável: não altera a ordem dos dados iguais

 Online

◼ Pode ordenar elementos a medida que os recebe (tempo real)

◼ Não precisa ter todo o conjunto de dados para colocá-los em ordem

Estrutura de Dados em C - Ordenação

 Algoritmo Insertion Sort
39

 Complexidade
 Considerando um array com N elementos, o tempo de execução é:
◼ O(N), melhor caso: os elementos já estão ordenados.

◼ O(N2), pior caso: os elementos estão ordenados na ordem inversa.

◼ O(N2), caso médio.

Estrutura de Dados em C - Ordenação

 Ordenação de array de struct
80

 A ordenação de um array de inteiros é uma tarefa simples

 Na prática, trabalhamos com dados um pouco mais complexos,
como estruturas

 Mais dados para manipular

Estrutura de Dados em C - Ordenação

 Ordenação de array de struct
81

 Como fazer a ordenação quando o que temos é um array de

struct?

V[0] v[1] v[2] v[3] v[4] v[5]

Estrutura de Dados em C - Ordenação

 Ordenação de array de struct
82

 Relembrando

 A ordenação é baseada em uma chave

 A chave de ordenação é o campo do item utilizado para comparação
◼ Valor armazenado em um array de inteiros

◼ Campo de uma struct

◼ etc

 É por meio dela que sabemos se um determinado elemento está a

frente ou não de outros no conjunto
Estrutura de Dados em C - Ordenação
 Ordenação de array de struct
83

 Ou seja, devemos modificar o algoritmo para que a comparação das

chaves seja feita utilizando um determinado campo da struct
 Exemplo
 Vamos modificar o insertion sort
◼ Essa modificação vale para os outros métodos

Estrutura de Dados em C - Ordenação

 Ordenação de array de struct
84

 Duas novas formas de ordenação

 Por matricula

Estrutura de Dados em C - Ordenação

 Ordenação de array de struct
85

 Duas novas formas de ordenação

 Por nome

Estrutura de Dados em C - Ordenação

 Leitura Específica
86

 Ordenando Vetores Usando a Linguagem C. Disponível em:

https://terminaldeinformacao.com/2013/05/10/ordenando-vetores-usando-linguagem-c/

 ASCENCIO, A.F.G., ARAUJO, G.S. Estrutura de Dados: Algoritmos, Análise da Complexidade e

implementações em Java e C/C++. 1ª Ed.. São Paulo: Pearson Prentice Hall, 2010. Disponível em:
https://plataforma.bvirtual.com.br/Acervo/Publicacao/1995 Pags. 21, 38 44 - Algoritmos de
Ordenação e Busca

 Ordenação. Disponível em: http://www.ic.uff.br/~cbraga/ed/apostila/ed15-ordenacao.pdf

 Conheça os principais algoritmos de ordenação. Disponível em:

https://www.treinaweb.com.br/blog/conheca-os-principais-algoritmos-de-ordenacao/

Estrutura de Dados em C - Ordenação

 Aprenda+
87

 Video "Insert-sort with Romanian folk dance". Disponível

em: https://www.youtube.com/watch?v=ROalU379l3U

 Video "Select-sort with Gypsy folk dance". Disponível em:

https://www.youtube.com/watch?v=Ns4TPTC8whw

 Video "Bubble-sort with Hungarian ("Csángó") folk dance.

Disponível em:
https://www.youtube.com/watch?v=lyZQPjUT5B4
Estrutura de Dados em C - Ordenação