SelectionSort e HeapSort

Prévia do material em texto

SelectionSort
Introdução
O SelectionSort é um método de ordenação por seleção, onde é feito uma troca de elementos das matrizes. O método é pegar o menor elemento e trocar sua posição com o primeiro, após isso, o próximo menor elemento troca de posição com o segundo e assim continua até que o algoritmo seja ordenado corretamente, podendo ser ordenado de forma crescente ou decrescente.
Fundamentos
Utilizando o método por seleção, será preciso de dois loops sendo um usado para percorrer todos os elementos e outro para cada elemento percorrer toda a lista. Quando executado o programa, ele percorreria por todos os elementos e identificaria o número ‘1’ como o menor elemento e trocaria sua posição com o primeiro que no caso é o número ‘10‘, o processo irá se repetir até não houver amis opções de troca, indicando assim que a lista está ordenada.
L = [10,1,5,7,8]
Lista ordenada:
L = [1,5,7,8,10]
Aplicações
 Linhas Principais:
def selection_sort (arr): Está definindo a função ‘selection_sort’ que aceita ‘arr’ como um argumento representando a lista que deve ser ordenada.
n = len (arr): A variável ‘n’ está armazenando o cumprimento da lista ‘arr’.
for i in range(n): Um loop que irá percorrer por todos os elementos da lista até n-1. O índice ‘i’ está representando o elemento que deve ser colocado na posição certa.
min_index = i: Define ‘min_index’ como ‘i’, ou seja o menor elemento da lista não ordenada irá começar na posição ‘i’.
for j in range(i+1,n): Um loop interno que irá percorrer os elementos que ainda restam na lista, utilizando índice ‘j’ para comparar com os elementos menores. Na próxima linha o elemento no índice ‘j’ irá ser comparado com o menor índice, caso arr[j] for menor ‘min_index’ irá ser usado para ‘j’, pois um novo menor elemento foi encontrado. 
Após o término do loop interno, o elemento da posição ‘i’ irá ser trocado com o menor elemento da parte não ordenada. 
A lista ‘L’ não ordenada é definida e a função ‘selection_sort’ é chamada para que a ordenação seja feita e depois a lista ordenada é impressa.
Vantagens e desvantagens
O SelectionSort é simples e fácil de implementar, porém não muito eficaz para listas grandes, algo também observado por Thomas Cormen, autor do livro Desmitificando Algritmos, de acordo com sua analise “(..) A primeira é que veremos que seu tempo de execução assintótico de Θ (n2) é o pior dos algoritmos de ordenação que examinaremos(..)”.(Desmitificando Algoritmos, p.29).
HeapSort
Introdução
Diferente do método ‘SelectionSort’, o método ‘HeapSort’ não faz comparações entre o menor elemento com os maiores, mas sim do maior, reorganizando de uma forma que o maior elemento fique na última posição e o próximo maior, caso exista, depois dele ocupando assim a última posição. Continuando até que a lista esteja ordenada.
Pois esse método usa uma estrutura de dados ‘Binary Heap’ que simboliza uma árvore binária, onde o maior elemento é a raiz dessa árvore, os elementos filhos a esquerda são verificados para saber se são maiores que a raiz, os filhos a direita são verificados para saber se são maiores que o maior elemento até agora. A prioridade é levar o maior elemento para esquerda primeiramente.
Fundamentos
Usando o método ‘HeapSort’ para ordenar essa lista o programa levaria o maior número que no caso é o ‘10’ para a última posição, que quando na posição certa irá ser cortado da árvore.
L = [10,1,5,7,8]
L = [1,5,7,8]
Após isso, uma outra ‘Heap’ é criada fora desses elementos para só assim procurar o próximo maior número que será levado a última posição. Repetindo esse processo até que todos os elementos sejam excluídos dessa primeira ‘Heap’. Portando a saída do programa ficaria assim:
L = [1,5,7,8,10]
Aplicações
Linhas principais:
Esta linha define a função heapify, que aceita como argumentos a lista arr, o tamanho da lista n e o índice i do elemento a ser ajustado. Inicializamos maior como i, assumindo que o elemento em i é o maior, pelo menos por enquanto, calculamos os índices dos filhos do nó atual. O filho à esquerda é 2*i + 1 e o filho à direita é 2*i + 2.
Esta condição verifica se o filho à esquerda existe (esquer