Algoritmos e Programação de Computadores

MC102 – Algoritmos e Programa¸c˜ao de Computadores
Instituto de Computa¸c˜ao
UNICAMP

Primeiro Semestre de 2015

Roteiro

1

O problema da ordena¸c˜ao

2

Selection Sort

3

Insertion Sort

4

Bubble Sort

5

Exerc´ıcios

Instituto de Computa¸c˜ ao (UNICAMP)

MC102

Primeiro Semestre de 2015

2 / 41

O problema da ordena¸c˜ao

Vamos estudar alguns algoritmos para o seguinte problema:
Dada uma cole¸c˜ao de elementos, com uma rela¸c˜ao de ordem entre eles, ordenar os elementos da cole¸c˜ao de forma crescente.
Nos nossos exemplos, a cole¸c˜ao de elementos ser´a representada por um vetor de inteiros.
N´
umeros inteiros possuem uma rela¸c˜ao de ordem entre eles.

Apesar de usarmos inteiros, os algoritmos que estudaremos servem para ordenar qualquer cole¸c˜ao de elementos que possam ser comparados entre si.

Instituto de Computa¸c˜ ao (UNICAMP)

MC102

Primeiro Semestre de 2015

4 / 41

O problema da ordena¸c˜ao

O problema da ordena¸c˜ao ´e um dos mais b´asicos em computa¸c˜ao.
Muito provavelmente este ´e um dos problemas com maior n´ umero de aplica¸c˜ oes diretas ou indiretas (como parte da solu¸c˜ao para um problema maior).
Exemplos de aplica¸c˜ oes diretas: cria¸c˜ao de rankings. defini¸c˜ao de preferˆencias em atendimentos por prioridade. cria¸c˜ao de listas.

Exemplos de aplica¸c˜ oes indiretas: otimiza¸c˜ao de sistemas de busca. manuten¸c˜ao de estruturas de bancos de dados.

Instituto de Computa¸c˜ ao (UNICAMP)

MC102

Primeiro Semestre de 2015

5 / 41

Selection Sort

Seja vet um vetor, contendo n n´ umeros inteiros, que desejamos ordenar de forma crescente.
A ideia do algoritmo ´e a seguinte:
Encontre o menor elemento a partir da posi¸c˜ao 0. Troque este elemento com o elemento da posi¸c˜ao 0.
Encontre o menor elemento a partir da posi¸c˜ao 1. Troque este elemento com o elemento da posi¸c˜ao 1.
Encontre o menor elemento a partir da posi¸c˜ao 2. Troque este elemento com o elemento da posi¸c˜ao 2.
E assim sucessivamente...

Instituto de Computa¸c˜
ao