4 Algoritmos de ordenação - p2

Prévia do material em texto

ALGORITMOS DE ORDENAÇÃO
PARTE 2
DIVIDIR PARA CONQUISTAR
Definição
“Quebra” o problema em subproblemas que são similares ao problema original, recursivamente resolve os subproblemas, e finalmente combina as soluções para resolver o problema original.
Porque dividir e conquistar resolve subproblemas recursivamente, cada subproblema deve ser menor que o problema original, e deve existir um problema base para os subproblemas. 
Definição
Dividir o problema em um número de subproblemas que sejam partes menores do mesmo problemas.
Conquistar os subproblemas resolvendo-os recursivamente. Se eles forem pequenos o suficiente, resolva os subproblemas como problemas base.
Combinar as soluções dos subproblemas em uma solução para o problema original.
Quando utilizar?
É possível identificar pelo menos duas situações genéricas em que a abordagem por divisão e conquista é adequada: 
Problemas onde um grupo de operações são correlacionadas ou repetidas. A multiplicação de matrizes é um exemplo 
Problemas em que uma decisão deve ser tomada e, uma vez tomada, quebra o problema em peças disjuntas. Em especial, a abordagem por divisão e conquista é interessante quando algumas peças passam a ser irrelevantes
Exercício
Aplique a estratégia da divisão e conquista ao problema de calcular a soma dos elementos de um vetor A[1..n] de números inteiros. 
Estime o consumo de tempo do algoritmo. 
Compare o resultado com o consumo de tempo do algoritmo trivial de soma.
Merge sort
Divida o vetor em 2 subvetores (ao meio) recursivamente até ele ter o tamanho 1.
Intercale pares de elementos adjacentes. 
Repita esse processo até restar apenas um arquivo de tamanho n.
Dividir 
void mergeSort(int∗ vetor, int inicio, int fim){
	 if (inicio < fim) {
		int meio = (inicio+fim)/2;
		mergeSort(vetor, inicio, meio);
		mergeSort(vetor, meio+1, fim);
		merge(vetor, inicio, meio, fim);
	}
}
DIVIDIR
Conquistar 
 void merge(int vetor[], int inicio, int meio, int fim) {
 	int com1 = inicio, com2 = meio+1, comAux = 0, vetAux[fim−inicio+1];
	while(com1<=meio && com2<=fim){
		if(vetor[com1] <= vetor[com2]){
			vetAux[comAux] = vetor[com1];
			com1++;
		}else{
			vetAux[comAux] = vetor[com2];
			com2++; }
 		comAux++; }
	while(com1<=meio){ //Caso ainda haja elementos na primeira metade
Conquistar 
	vetAux[comAux] = vetor[com1];
	comAux++;com1++; }
	while(com2<=fim){ 
		vetAux[comAux] = vetor[com2];
		comAux++;com2++; }
	for(comAux=inicio;comAux<=fim;comAux++){					vetor[comAux] = vetAux[comAux−inicio];
	}
}
CONQUISTAR
Vantagens e desvantagens
Método de ordenação com tempo: 
Melhor caso: n ∗ log2n; 
Pior caso:n ∗ log2n; 
Utiliza mais memória para poder ordenar (vetor auxiliar). 
O MergeSort é estável: não altera a ordem de dados iguais. 
Quick sort
Este algoritmo usa uma técnica conhecida por divisão e conquista, muito conhecida por reduzir problemas complexos em problemas menores para tentar chegar em uma solução. 
Sua complexidade é:
Complexidade Pior Caso: O(n²)
Complexidade Caso Médio: (nlogn)
Complexidade Melhor Caso: (nlogn)
Quick sort
Escolhe-se um elemento qualquer da lista, que será chamado de pivô.
Todos os elementos antes do pivô devem ser menores que ele e todos os elementos após o pivô devem ser maiores que ele. Quando esse processo de separação for finalizado, então o pivô deve estar exatamente no meio da lista.
De forma recursiva os elementos da sublista menor e maiores são ordenados.
	private static void quickSort(int[] vetor, int inicio, int fim) {
             if (inicio < fim) {
                    int posicaoPivo = separar(vetor, inicio, fim);
                    quickSort(vetor, inicio, posicaoPivo - 1);
                    quickSort(vetor, posicaoPivo + 1, fim);
             }
       }
  
     
  private static int separar(int[] vetor, int inicio, int fim) {
             int pivo = vetor[inicio];
             int i = inicio + 1, f = fim;
             while (i <= f) {
                    if (vetor[i] <= pivo)
                           i++;
                    else if (pivo < vetor[f])
                           f--;
                    else {
                           int troca = vetor[i];
                           vetor[i] = vetor[f];
                           vetor[f] = troca;
                           i++;
                           f--;
                    }
             }
             vetor[inicio] = vetor[f];
             vetor[f] = pivo;
             return f;
       }
Reforçando
https://visualgo.net/en/sorting
18
Comparação entre os métodos
https://www.toptal.com/developers/sorting-algorithms
 
.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; 
}
 
 
.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; 
}