Heapsort: utiliza uma estrutura de dados chamada heap binário para ordenar os elementos a medida que os insere na estrutura. Assim, ao final das inserções, os elementos podem ser sucessivamente removidos da raiz da heap, na ordem desejada.
Ordenação por Inserção
Sua complexidade é equivalente à da ordenação bolha. A ordenação da tabela pode ser estendida até o (i + 1)-ésimo elemento por meio de comparações sucessivas deste com os elementos anteriores, isto é, com o iésimo elemento, com o (i – 1)-ésimo elemento, procurando sua posição correta na parte da tabela que já está ordenada.
Ordenação Rápida (Quicksort)
A ordenação rápida é um dos mais eficientes dentre os conhecidos.
Dois pontos são decisivos para o bom desempenho do algoritmo: a escolha do pivô e o particionamento da tabela.
Alternativa: A
QuickSort é um algoritmo de divisão e conquista. Ele seleciona um elemento como pivô e particiona o array fornecido ao redor do pivô selecionado. Existem muitas versões diferentes do quickSort que selecionam o pivô de maneiras diferentes.
Sempre escolha o primeiro elemento como pivô.
Sempre escolha o último elemento como pivô (implementado abaixo)
Escolha um elemento aleatório como pivô.
Escolha a mediana como pivô.
O principal processo no quickSort é a partição (). O objetivo das partições é, dado uma matriz e um elemento x da matriz como pivô, colocar x em sua posição correta na matriz classificada e colocar todos os elementos menores (menores que x) antes de x, e colocar todos os elementos maiores (maiores que x) depois x. Tudo isso deve ser feito em tempo linear.
Inserção é um algoritmo de classificação simples que funciona de maneira semelhante à maneira como você classifica as cartas de baralho em suas mãos. O array é virtualmente dividido em uma parte ordenada e outra não ordenada. Os valores da parte não ordenada são selecionados e colocados na posição correta na parte ordenada.
Algoritmo:
Para ordenar uma matriz de tamanho n em ordem crescente:
1: Itere de arr [1] para arr [n] na matriz.
2: Compare o elemento atual (chave) com seu predecessor.
3: Se o elemento-chave for menor do que seu predecessor, compare-o com os elementos anteriores. Mova os elementos maiores uma posição para cima para liberar espaço para o elemento trocado.
Heapsort é uma técnica de classificação baseada em comparação baseada na estrutura de dados Binary Heap. É semelhante à classificação por seleção, onde primeiro encontramos o elemento mínimo e colocamos o elemento mínimo no início. Repetimos o mesmo processo para os elementos restantes.
1. Construa um heap máximo a partir dos dados de entrada.
2. Nesse ponto, o maior item é armazenado na raiz do heap. Substitua-o pelo último item do heap seguido pela redução do tamanho do heap em 1. Finalmente, monte a raiz da árvore.
3. Repita a etapa 2 enquanto o tamanho do heap for maior que 1.
shellSort é um algoritmo de classificação que primeiro classifica os elementos distantes uns dos outros e reduz sucessivamente o intervalo entre os elementos a serem classificados. É uma versão generalizada do insertionSort.
No shellSort, os elementos em um intervalo específico são classificados. O intervalo entre os elementos é diminuído gradualmente com base na sequência usada. O desempenho da classificação de shell depende do tipo de sequência usada para um determinado array de entrada.
O selectionSort classifica uma matriz encontrando repetidamente o elemento mínimo (considerando a ordem crescente) da parte não classificada e colocando-o no início. O algoritmo mantém dois subarrays em um determinado array.