Ordenação e Estatísticas de Ordem

Uma ordenação permuta as chaves de um vetor para ordem não decrescente. A estatística de ordem k é o k-ésimo menor: k = 1 é o mínimo e k = ⌈n/2⌉ é uma mediana.

Max-Heapify, a partição de Lomuto e o Quickselect deste tópico — e Huffman nos algoritmos gulosos — reutilizam o extremo na raiz e o recorte em torno de um pivô.

As páginas se agrupam em quatro blocos. O primeiro mantém o extremo na raiz: árvore completa no vetor indexado a partir de 1, restauração só contra os filhos, extrações até o sufixo ordenado, e a fila de prioridade.

O segundo recorta em torno do último elemento e recorre nas duas metades — recorte n/2 ou um lado vazio — e trata o caso médio e o pivô sorteado.

O terceiro deriva Ω(n log n) da altura da árvore de decisão e posiciona inteiros em {0,…,k} pelo prefixo das contagens.

O quarto obtém mínimo e máximo comparando os elementos em pares, e o k-ésimo com uma única recursão ou com pivô da mediana das medianas.

Pior caso O(n log n) por extrações da raiz está em Heapsort. Recorrências T(n)=2T(n/2)+n e T(n)=T(n−1)+n, médio e aleatorizado, estão em Quicksort.

Particionar e recorrer nos dois lados é Quicksort. Recorrer só no lado que contém o k-ésimo é Medianas e Estatísticas de Ordem.

Inserir e extrair o máximo em O(log n) estão em Heapsort. Mínimo e máximo juntos em 3⌊n/2⌋−2 comparações, sem heap, estão em Medianas e Estatísticas de Ordem.

A cota Ω(n log n) por Stirling e a ordenação por contagem com prefixo e escrita de trás estão em Ordenação em Tempo Linear.