3 Algoritmos de Ordenação - p1

Prévia do material em texto

ALGORITMOS DE ORDENAÇÃO
PARTE 1
MÉTODOS DE ORDENAÇÃO
Introdução
Ordenar corresponde ao processo de reorganizar um conjunto de objetos em uma ordem ascendente ou descendente
Consiste em facilitar a recuperação posterior de itens do conjunto ordenado
Exemplo: lista telefônica, biblioteca, geração de relatórios
Outras funções
Teste de unicidade 
Remoção de duplicatas 
Busca 
Encontrar o i-ésimo maior (ou menor) elemento de uma coleção 
Contagem de frequência
Métodos de ordenação
Os mais populares algoritmos de ordenação são:
 Insertion sort
Selection sort
Bubble sort
Comb sort
Quick sort
Merge sort
Heap sort
Shell sort. 
Métodos de ordenação
Os mais populares algoritmos de ordenação são:
Insertion sort
Selection sort
Bubble sort
Comb sort
Quick sort
Merge sort
Heap sort
Shell sort. 
BUBBLE SORT
É o algoritmo mais simples, mas o menos eficiente.
 Neste algoritmo cada elemento da posição i será comparado com o elemento da posição i + 1.
Caso o elemento da posição 2 for maior que o da posição 3, eles trocam de lugar e assim sucessivamente. 
Por causa dessa forma de execução, o vetor terá que ser percorrido quantas vezes que for necessária, tornando o algoritmo ineficiente para listas muito grandes.
BUBBLE SORT
BUBBLE SORT - IMPLEMENTAÇÃO
public static void main(String args[]){
    int[] vet = {8, 9, 3, 5, 1};
    int aux = 0;
    int i = 0;
     
    System.out.println("Vetor desordenado: ");
    for(i = 0; i<5; i++){
        System.out.println(" "+vet[i]);
    }
    System.out.println(" ");
     
    for(i = 0; i<5; i++){
        for(int j = 0; j<4; j++){
            if(vet[j] > vet[j + 1]){
                aux = vet[j];
                vet[j] = vet[j+1];
                vet[j+1] = aux;
            }
        }
    }
    System.out.println("Vetor organizado:");
    for(i = 0; i<5; i++){
        System.out.println(" "+vet[i]);
    }
}
QUAL A COMPLEXIDADE DO ALGORITMO NO PIOR CASO?
BUBBLE SORT
Vantagens
Simplicidade do algoritmo
Estável
Desvantagens
Lentidão
Indicações
Tabelas muito pequenas
Quando se sabe que a tabela está quase ordenada
Exercício
Implemente o bubble sort 
Meça o tempo e conte o nº de trocas nas seguintes situações:
Vetores aleatórios, ordenados e invertidos
Tamanhos: 
100
200
400
1000
2000
10000
SELECTION SORT
Este algoritmo é baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o segundo menor valor para a segunda posição e assim sucessivamente, até os últimos dois elementos.
É repetido esse processo até que a lista esteja ordenada.
SELECTION SORT
SELECTION SORT - IMPLEMENTAÇÃO
QUAL A COMPLEXIDADE DO ALGORITMO NO PIOR CASO?
void selection_sort(int∗ v, int n) { //n é tamanho do vetor
	int i, j, min, aux;
	for (i = 0; i < (n−1); i++){
		min = i;
		for (j = (i+1); j < n; j++) {
if(v[j] < v[min])
	min = j;
		}
		if (v[i] != v[min]) {
aux = v[i];
v[i] = v[min];
v[min] = aux;
}
	}
}
SELECTION SORT
Uma vantagem do Selection Sort é que entre os algoritmos de ordenação ele apresenta uma das menores quantidades de movimentos entre os elementos, assim pode haver algum ganho quando se necessita ordenar estruturas complexas.
Uma desvantagem é que o número de comparações é igual para o melhor caso, caso médio e o pior caso. Assim, mesmo que o vetor esteja ordenado o custo continua quadrático.
Não é estável (depende da implementação).
Exercício
Implemente o selection sort 
Meça o tempo e conte o nº de trocas nas seguintes situações:
Vetores aleatórios, ordenados e invertidos
Tamanhos: 
100
200
400
1000
2000
10000
INSERTION SORT
Compare o valor do item “chave” que está entrando com os outros itens até que se sua posição seja encontrada. Essa comparação é feita em direção à esquerda.
Se o item que você está comparando for menor, desloque o item para a direita , visando “abrir” um novo espaço para colocar a carta na posição correspondente);
Finalmente ao encontrar um item maior ou não haver mais itens, significa que você encontrou a posição que este item deve estar: coloque o item “chave” na posição correspondente.
INSERTION SORT
INSERTION SORT - IMPLEMENTAÇÃO
QUAL A COMPLEXIDADE DO ALGORITMO NO PIOR CASO?
public static void insertionSort(int[] vetor) {
    int j;
    int key;
    int i;
    
    for (j = 1; j < vetor.length; j++)
    {
      key = vetor[j];
      for (i = j - 1; (i >= 0) && (vetor[i] > key); i--)
      {
         vetor[i + 1] = vetor[i];
       }
        vetor[i + 1] = key;
    }
}
INSERTION SORT
O número mínimo de comparações e movimentos ocorre quando os itens estão originalmente em ordem.
O número máximo de comparações e movimentos ocorre quando os itens estão originalmente em ordem reversa.
Bom método a ser usado quando a sequência esta quase ordenada, ou quando se deseja adicionar poucos itens a uma sequência já ordenada.
O algoritmo de ordenação por inserção é estável.
Exercício
Implemente o Insertion sort 
Meça o tempo e conte o nº de trocas nas seguintes situações:
Vetores aleatórios, ordenados e invertidos
Tamanhos: 
100
200
400
1000
2000
10000
Material auxiliar
https://pt.khanacademy.org/computing/computer-science/algorithms
22
Revisão
23
24
ANÁLISE DOS MÉTODOS DE ORDENAÇÃO
Bubble sort
for( i = 0 ; i < N-1 ; i++ )
 for( j = 1 ; j < N-i ; j++ )
 if ( v[j] < v[j-1]) 
 {
 		aux = v[j];
 		v[j] = v[j-1];
 		v[j-1] = aux;
 } 
25
Selection sort
for (i = 0; i < N - 1; i++)
 { 
 Min = i;
 for (j = i + 1 ; j < N; j++)
 if ( v[j] < v[Min]) 
 	Min = j;
 aux = v[Min];
 v[Min] = v[i];
 v[i] = aux;
 }
26
Insertion sort
for (i = 1; i < N; i++)
 {
 	aux = v[i];
 	j = i - 1;
 	while ( (j >= 0) && (aux < v[j]) )
 	{
 		v[j + 1] = v[j];
 		j--;
 	}
 	v[j + 1] = aux;
 }
27
Mais alguns exercícios
28
Encontrar o máximo de um vetor
Qual a complexidade no melhor e no pior caso?
d e f exp ( x , a ) : 
r = 1 
w hil e a ! = 0 : 	
i f ( a % 2 ) != 0: 
r ∗= x 
a −= 1 
 a / = 2 
 x = x∗x 
 r e t u r n r
Sugestão
Assistir os vídeos do canal da Univesp – Universidade Virtual do Estado de São Paulo:
https://www.youtube.com/watch?v=ojCAnD7vrOY
 
.MsftOfcThm_Accent1_Fill {
 fill:#4472C4; 
}
.MsftOfcThm_Accent1_Stroke {
 stroke:#4472C4; 
}
 
 
.MsftOfcThm_Accent1_Fill {
 fill:#4472C4; 
}
.MsftOfcThm_Accent1_Stroke {
 stroke:#4472C4; 
}
 
 
.MsftOfcThm_Accent1_Fill {
 fill:#4472C4; 
}
.MsftOfcThm_Accent1_Stroke {
 stroke:#4472C4; 
}
 
 
.MsftOfcThm_Accent1_Fill {
 fill:#4472C4; 
}
.MsftOfcThm_Accent1_Stroke {
 stroke:#4472C4; 
}