Ordenação por Seleção (Seelction Sort)

O conceito fundamental da ordenação por seleção consiste em identificar o menor (ou maior) elemento dentro de um conjunto de dados e posicioná-lo em sua localização correta, repetindo esse processo para o restante dos elementos até que toda a sequência esteja organizada.

Seleção Direta

Neste método, realizamos múltiplas passagens pela lista. Em cada iteração i, buscamos o menor elemento entre a posição i e o final da lista, trocando-o com o elemento da posição i.

def ordenacao_selecao_direta(lista):
    """
    Implementação clássica do Selection Sort.
    """
    total_elementos = len(lista)
    for i in range(total_elementos):
        # Assume que o primeiro elemento não ordenado é o menor
        indice_menor = i
        
        # Procura o menor elemento no restante da lista
        for j in range(i + 1, total_elementos):
            if lista[j] < lista[indice_menor]:
                indice_menor = j
        
        # Realiza a troca se um novo menor for encontrado
        if indice_menor != i:
            lista[i], lista[indice_menor] = lista[indice_menor], lista[i]

if __name__ == "__main__":
    numeros = [84, 62, 35, 77, 55, 14, 35, 98]
    ordenacao_selecao_direta(numeros)
    print(f"Resultado da Seleção Direta: {numeros}")

Ordenação por Torneio (Tree Selection Sort)

Este algoritmo, também conhecido como Tournament Sort, utiliza uma estrutura de árvore binária para reduzir o número de comparações. A ideia é simular um torneio onde os elementos competem em pares, e o vencedor (o menor valor) sobe para o próximo nível da árvore até atingir a raiz.

import math

class OrdenadorTorneio:
    def __init__(self, dados):
        self.original = dados
        self.tamanho = len(dados)
        if self.tamanho > 0:
            self.n_folhas = 1 << (self.tamanho - 1).bit_length()
            self.arvore = [float('inf')] * (2 * self.n_folhas - 1)
            self._construir_arvore()

    def _construir_arvore(self):
        # Preenche as folhas com os dados originais
        inicio_folhas = self.n_folhas - 1
        for i in range(self.tamanho):
            self.arvore[inicio_folhas + i] = self.original[i]
        
        # Sobe na árvore decidindo os vencedores
        for i in range(inicio_folhas - 1, -1, -1):
            self.arvore[i] = min(self.arvore[2 * i + 1], self.arvore[2 * i + 2])

    def extrair_vencedor(self):
        if self.tamanho == 0:
            return None
        
        vencedor = self.arvore[0]
        if vencedor == float('inf'):
            return None

        # Localiza a folha do vencedor e a invalida
        idx = self.n_folhas - 1
        for i in range(self.n_folhas):
            if self.arvore[idx + i] == vencedor:
                self.arvore[idx + i] = float('inf')
                atual = idx + i
                # Atualiza o caminho até a raiz
                while atual > 0:
                    pai = (atual - 1) // 2
                    irmao = atual + 1 if atual % 2 == 1 else atual - 1
                    self.arvore[pai] = min(self.arvore[atual], self.arvore[irmao])
                    atual = pai
                break
        return vencedor

    def executar_sort(self):
        resultado = []
        for _ in range(self.tamanho):
            val = self.extrair_vencedor()
            if val is not None:
                resultado.append(val)
        return resultado

if __name__ == "__main__":
    exemplo = [3, 1, 4, 1, 5, 9, 2, 6]
    torneio = OrdenadorTorneio(exemplo)
    print(f"Resultado do Torneio: {torneio.executar_sort()}")

Ordenação por Heap (Heap Sort)

O Heap Sort é uma evolução otimizada da seleção em árvore. Ele utiliza uma estrutura de dados chamada Heap, que é uma árvore binária completa com propriedades específicas de ordenação entre pais e filhos.

Definições de Heap

• Heap de Mínimo (Min-Heap): O valor de cada nó pai é menor ou igual aos valores de seus filhos. A raiz contém o menor elemento.
• Heap de Máximo (Max-Heap): O valor de cada nó pai é maior ou igual aos valores de seus filhos. A raiz contém o maior elemento.

Estrutura e Manipulação de Heap

Os Heaps são geralmente implementados em arrays para maior eficiência de memória. Para um nó no índice i, seu filho esquerdo está em 2i + 1 e o direito em 2i + 2.

class GestorHeap:
    def __init__(self, elementos=None):
        self.heap = elementos if elementos else []
        if self.heap:
            self._construir_heap_minimo()

    def _ajustar_abaixo(self, pai, limite):
        menor = pai
        esquerda = 2 * pai + 1
        direita = 2 * pai + 2

        if esquerda < limite and self.heap[esquerda] < self.heap[menor]:
            menor = esquerda
        if direita < limite and self.heap[direita] < self.heap[menor]:
            menor = direita

        if menor != pai:
            self.heap[pai], self.heap[menor] = self.heap[menor], self.heap[pai]
            self._ajustar_abaixo(menor, limite)

    def _construir_heap_minimo(self):
        n = len(self.heap)
        for i in range(n // 2 - 1, -1, -1):
            self._ajustar_abaixo(i, n)

    def inserir(self, valor):
        self.heap.append(valor)
        atual = len(self.heap) - 1
        while atual > 0:
            pai = (atual - 1) // 2
            if self.heap[atual] < self.heap[pai]:
                self.heap[atual], self.heap[pai] = self.heap[pai], self.heap[atual]
                atual = pai
            else:
                break

    def remover_topo(self):
        if not self.heap:
            return None
        topo = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        if self.heap:
            self._ajustar_abaixo(0, len(self.heap))
        return topo

if __name__ == "__main__":
    h = GestorHeap([10, 25, 15, 40, 20])
    h.inserir(5)
    print(f"Heap após inserção de 5: {h.heap}")
    print(f"Removendo topo: {h.remover_topo()}")

Implementação do Algoritmo Heap Sort

Para ordenar em ordem crescente, construímos um Max-Heap. O maior elemento é movido para o final do array, o tamanho do heap é reduzido e a propriedade de Max-Heap é restaurada na raiz.

def heap_sort_ascendente(dados):
    n = len(dados)

    def reorganizar(arr, i, tamanho_heap):
        maior = i
        esq = 2 * i + 1
        dir = 2 * i + 2

        if esq < tamanho_heap and arr[esq] > arr[maior]:
            maior = esq
        if dir < tamanho_heap and arr[dir] > arr[maior]:
            maior = dir

        if maior != i:
            arr[i], arr[maior] = arr[maior], arr[i]
            reorganizar(arr, maior, tamanho_heap)

    # 1. Cria o Max-Heap inicial
    for i in range(n // 2 - 1, -1, -1):
        reorganizar(dados, i, n)

    # 2. Extrai elementos um a um
    for i in range(n - 1, 0, -1):
        dados[0], dados[i] = dados[i], dados[0]
        reorganizar(dados, 0, i)

if __name__ == "__main__":
    lista_teste = [40, 55, 73, 12, 98, 27]
    heap_sort_ascendente(lista_teste)
    print(f"Lista Ordenada com Heap Sort: {lista_teste}")