Intro sort

Intro sort
classe	Algoritmo de ordenação
estrutura de dados	Array, Listas ligadas
complexidade pior caso	${O}(n\log n)$
data	1997
Algoritmos

Introsort ou introspective sort é um algoritmo de ordenação criado por David Musser em 1997. Ele começa com o quicksort e muda para o heapsort quando a profundidade da recursividade excede um nível baseado no (logaritmo do) número de elementos a ser classificados. É o melhor dos dois mundos, com um tempo de execução de pior caso de O(n log n) e desempenho prático comparável ao quicksort em conjuntos de dados típicos. Uma vez que ambos os algoritmos que utiliza são ordenações de comparação, ele também é uma ordenação por comparação.

Em quicksort, uma das operações críticas é a escolha do pivô: o elemento em torno do qual a lista é particionada. O algoritmo mais simples de seleção do pivô é tomar o primeiro ou o último elemento da lista como o pivô, obtendo um comportamento pobre para o caso de entradas ordenadas ou quase totalmente ordenadas. A variante de Niklaus Wirth usa o elemento do meio para prevenir essas ocorrências, degenerando em O(n²) para seqüências inventadas. O algoritmo de seleção de pivô "mediana melhor-de-três" obtém a mediana do primeiro, médio e últimos elementos da lista; no entanto, mesmo que isso funcione bem em muitos exemplos do mundo real, ainda é possível inventar uma lista matadora de mediana melhor-de-três que irá causar desaceleração dramática de um quicksort com base nesta técnica de seleção do pivô. Essas contribuições poderiam potencialmente ser explorada por um agressor, por exemplo, enviar essa lista para um servidor de Internet para ordenação como um ataque de negação de serviço.

Musser relatou que em uma seqüência ''matadora de mediana melhor-de-três de 100.000 elementos, o tempo de excução do introsort foi de 1/200 do que o do quicksort "mediana melhor-de-três". Musser também considerou o efeito sobre o cache da pequena ordenação atrasada de Sedgewick, onde pequenos intervalos são classificados no final, em uma única passagem do insertion sort. Ele relatou que seria possível dobrar o número de erros de cache, mas que o seu desempenho com deques foi significativamente melhor e deve ser mantido para modelos de bibliotecas, em parte porque o ganho em outros casos, de fazer as ordenações imediatamente não foi grande.

Da mesma forma, Musser também introduziu o algoritmo de seleção de pior caso linear com tempo comparável ao algoritmo de Hoare, uma simples adaptação do quicksort que é o algoritmo de seleção mais eficiente utilizado na prática. Isso é chamado seleção por introspecção ou "Introselect".

Implementação

O introsort pode ser escrito da seguinte forma na linguagem de programação python 3:

def introsort(array):
    max_depth = math.log(len(array),2)
    size = len(array)
    pivot = size-1

    if size <= 1:
        return
    elif pivot > max_depth:
        heapsort(array)
    else:
        introsort(array[0:p], max_depth - 1)
        introsort(array[p+1:n], max_depth - 1)

Ligações externas

• «"A guide to Introsort"». Artigo criado ao longo de um projeto de pesquisa pelo aluno Ralph Unden. Contém uma implementação completa em Java.