Ordenação de Arrays
►A
ordenação de arrays é processo pelo qual
se procede à ordenação dos elementos de
um array por ordem crescente ou
decrescente.
►A
ordenação pode ser aplicada a dados
numéricos (inteiros, float, ..) e a
alfanuméricos (char), neste último caso os
dados ficam ordenados alfabeticamente.
1
Ordenação de Arrays
►O
porquê de ordenar os arrays?
 Para facilitar a pesquisa. Existem muitas funções de
pesquisa que exigem que o array esteja ordenado para
que se possam pesquisar valores.
 Facilita a detecção do maior e do menor valor.
► Se
o array não estiver ordenado temos de
percorrer todos os elementos para saber se um
determinado valor existe ou não.
 Desvantagem: mais processamento, muito tempo gasto
na pesquisa.
2
Ordenação de Arrays
► Funções
de ordenação:
►Bubble
Sort
►Heap Sort
►Insertion Sort
►Merge Sort
►Quick Sort
►Selection Sort
►Shell Sort
http://linux.wku.edu/%7Elamonml/algor/sort/index.html
3
Ordenação de Arrays
Bubble Sort:
►


É uma função de ordenação muito simples;
Ideal para ordenação de pequenas quantidades de valores, pois
exige bastante processamento.
Funcionamento
►




compara elementos adjacentes (vizinhos). Se o primeiro é maior
do que o segundo, troca-os.
Faz isto para cada par de elementos adjacentes, começando com
os dois primeiros e terminando com os dois últimos. Neste ponto
o último elemento deve ser o maior de todos.
repete os passos para todos os elementos excepto para o último.
continua a repetir, cada vez com um elemento a menos, até não
existam mais pares para comparar.
4
void bubbleSort(int array[], int array_size)
void bubbleSort(int array[], int array_size)
{
int i, j, temp;
}
for (i = (array_size - 1); i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (array[j-1] > array[j])
{
temp = array[j-1];
array[j-1] = array[j];
array[j] = temp;
}
}
}
5
i=3
j=1
i=3
j=2
i=3
j=3
i=2
j=1
i=2
j=2
i=1
j=1
i=0
j=1
4
1
0
1
1
4
0
1
5
2
2
5
3
2
2
5
não troca
3
1
4
2
0
1
2
3
1
4
2
5
0
1
2
3
1
4
2
5
0
1
1
2
0
1
2
3
1
2
4
5
0
1
2
4
troca
não troca
troca
3
5
2
troca
não troca
3
Array Ordenado
6
bubbleSort
► Ordenar
o seguinte array pelo método
Bubble Sort:
10
9
8
7
6
7
Ordenação de Arrays
► Quick
Sort:
 É uma das funções de ordenação mais rápidas e
eficazes.
 Faz uso da recursividade.
 É muito eficaz em grandes quantidades de
dados.
► Funcionamento:
 Divide recursivamente o array em partes e
ordena-as (recursivamente).
8
void quickSort(int numbers[], int array_size)
9
#include “ordenacao.h”
► Utilize
para ordenar a biblioteca
ordenacao.h
 Esta contém as funções:
►void
bubbleSort (int array[], int array_size)
►void quickSort (int numbers[], int array_size)
 Exemplo:
bubbleSort(array, 10);
bubbleSort(notas, NUMPOSICOES);
quickSort(array, 20);
10
Exercícios
1. Desenvolva uma aplicação com o seguinte
menu:



►
►
►
1 – ler valores para um array
2 – ordenar valores
3 – mostrar array
O array possui 10 posições de inteiros
Use a biblioteca “ordenacao.h”
Ordene pelo método quickSort.
11
Exercícios
2. Altere o programa anterior para que este
ordene valores reais.
12