Algoritmos de Ordenação

Neste momento, são considerados apenas os algoritmos de ordenação por comparação de elementos (chaves). Existem outros algoritmos de ordenação, que não requerem a comparação de elementos, que serão adicionados a este documento no futuro.

A ordenação de elementos é, de acordo com diversos autores, um dos problemas mais fundamentais no estudo de algoritmos. Estes algoritmos são bastante utilizados como solução final, ou como parte da solução de diversos problemas.

O estudo dos algoritmos de ordenação, além de trazer uma série de ferramentas que podem ser diretamente aplicada no desenvolvimento de sistemas, nos permite estudar e aplicar técnicas de desenvolvimento de algoritmos, análise de algoritmos, e nos dá a oportunidade de aprender a avaliar os diferentes algoritmos e possibilidades de implementação, que influenciarão o resultado final do programa em execução.

Os algoritmos apresentados aqui são:

  1. Insertion
  2. Selection
  3. Bubble
  4. Mergesort
  5. Quicksort
  6. Heapsort
  7. Introsort

Ao final, é apresentado um quadro com o Resumo dos Algoritmos, que mostra algumas das principais características de cada um dos algoritmos apresentados.

Problema da Ordenação

Dada uma seqüência de n elementos $\langle a_1, a_2, \ldots , a_n \rangle$, esta seqüência de elementos é dita ordenada como uma seqüência $\langle a_1^\prime, a_2^\prime, \ldots , a_n^\prime \rangle$, de tal forma que $a_1^\prime.k \leq a_2^\prime.k \leq \ldots \leq a_n^\prime.k$.

Quando estudamos algoritmos de ordenação, a seqüência de elementos é, normalmente, representada apenas por números inteiros. No entanto, na prática, raramente o conjunto de dados será um conjunto de números isolados, provavelmente o conjunto de elementos será um conjunto de registros, formados por diveros campos, onde um campo sera a chave (k) que identifica o registro (por exemplo, o nome de uma pessoa ou a placa de um carro).

Os algoritmos de ordenação são desenvolvidos como um método de ordenar estas chaves, independente do elemento consistir de um único valor ou de um registro de vários campos. Traduzir um algoritmo que ordena apenas números inteiros para um programa que ordena registros complexos é uma tarefa conceitualmente simples, apesar de que podem ocorrer algumas características que dificultaram a manipulação dos registos no programa, mas que não afetam a complexidade do algoritmo.

Características dos Algoritmos de Ordenação

Ao avaliarmos algoritmos, podemos levar em consideração diversos aspectos, como tempo de execução, consumo de memória, acessos a disco, número de escritas, paralelismo, comunicação, entre diversas outras características. Para os algoritmos de ordenação, estamos preocupados com apenas um conjunto dessas características.

Quando selecionamos um algoritmo de ordenação para ser implementado em um sistema, devemos levar em consideração o número e a característica das operações executadas, o consumo de memória auxiliar para a execução do algoritmo, e como o algoritmo se comporta com relação a estabilidade das chaves de igual valor.

Operações executadas

O tempo de execução de um algoritmo está intimamente ligado ao número de operações que o algoritmo executa, pois, em geral, ao criarmos um algoritmo, assumimos que o custo individual de cada operação é constante, o que acaba não acontecendo quando implementamos o algoritmo e o executamos em um computador.

Para um algoritmo de ordenação, duas operações são mais relevantes, e determinam o quanto um algoritmo será mais eficiente que o outro. Estas duas operações são a comparação entre dois elementos e as trocas de posição dos elementos dentro da estrutura.

O número de comparações é importante pois quanto mais comparações são executadas pelo algoritmo, maior o número de acesso de leitura aos dados, e o processo de comparação de uma chave qualquer pode demandar um grande esforço computacional pelo processador (embora os exemplos aqui utilizados sejam apenas inteiros, que tem uma comparação rápida em qualquer arquitetura de computador moderna, lembre-se que não existe essa restrição para a implantação dos algoritmos, e podemos ter que comparar chaves com diversos tipos de dados).

O número de trocas também é importante, pois determina o número de escritas que serão efetuadas pelo algoritmo. Embora o número de escritas quando os dados estão armazenados em memória RAM não tenha um impacto maior que a leitura, sendo apenas uma operação a mais a ser executadas pelo algoritmo, caso os dados estejam armazenados em memória flash, por exemplo, um algoritmo que efetue mais escritas que outro pode se tornar não apenas menos eficiente, mas reduzir o tempo de vida útil do dispositvo, uma vez que memórias flash para armazenamento de dados tem um tempo de vida medido em número de escritas, e esta é uma operação bem mais lenta nesses dispositivos.

Quando o algoritmo executa apenas em memória, estamos preocupados com o número total de operações, e estas serão a soma das comparações e das trocas. Este número está diretamente relacionado com o tempo de execução do algoritmo e é medido em relação ao tamanho da entrada do algoritmo, ou seja, o tamanho da seqüência de elementos que precisa ser ordenada.

Consumo de memória

O consumo de memória de um algoritmo é importante principalmente em sistemas embarcados que possuem limitações com relação a este recurso, ou em sistemas que processam um volume muito grande de informações, onde este recurso, apesar de abundande, pode não ser muito grande em relação ao número de dados que devem ser manipulados.

Outra característica importante com relação ao consumo de memória é a capacidade do algoritmo de levar em consideração a localidade dos dados e utilizar de maneira mais eficiente a memória cache. Embora esta característica não será abordada neste documento, pode ser uma característica importante em sistemas específicos.

Estabilidade de chaves

Um algoritmo de ordenação é dito estável com relação às chaves quando dois elementos, com chaves de igual valor, mantém a sua ordem relativa após a ordenação dos elementos.

Por exemplo, dado a seguinte seqüencia de elementos,

$$ \langle\, \textbf{(3,B)},(2,D),(1,D),(4,A),\textbf{(3,A)},(5,C) \,\rangle $$

se a seqüência for ordenada por um algoritmo de ordenação estável, e a chave fosse o primeiro elemento (inteiro), teríamos como resultado

$$ \langle\, (1,D),(2,D),\textbf{(3,B)},\textbf{(3,A)},(4,A),(5,C) \,\rangle $$

No entanto, se um algoritmo não estável fosse utilizado, poderíamos ter o seguinte resultado

$$ \langle\, (1,D),(2,D),\textbf{(3,A)},\textbf{(3,B)},(4,A),(5,C) \,\rangle $$

Note a inversão dos elementos (3,B) e (3,A) em relação a posição na seqüencia original, quando da ordenação com o algoritmo instável com relação às chaves.

A estabilidade é importante quando temos vários níveis de ordenação. Por exemplo, em uma lista de pessoas, onde os registros possuem campos para o sobrenome e o primeiro nome, queremos obter a ordenação por sobrenome, e então pelo primeiro nome. Neste caso, ordenamos pelo primeiro nome (chave secundária de ordenação), utilizando qualquer tipo de algoritmo de ordenação (estável ou não estável), e após, utilizamos um algoritmo estável para ordenar pelo sobrenome. Após a execução, teremos uma lista ordenada por sobrenome, porém, quando os sobrenomes forem os mesmos, a ordem do primeiro nome será mantida.

Vamos fazer semelhante com a lista de dados anterior.

$$ \langle\, (3,B),(2,D),(1,D),(4,A),(3,A),(5,C) \,\rangle $$

Ordenando pelo segundo campo (letra), obtemos:

$$ \langle\, (4,A),(3,A),(3,B),(5,C),(2,D),(1,D) \,\rangle $$

Agora, ordenamos pelo primeiro campo (número):

$$ \langle\, (1,D),(2,D),(3,A),(3,B),(4,A),(5,C) \,\rangle $$

Como o algoritmo é estável, conseguimos manter a ordenação das letras para chaves iguais.

Algoritmos de ordenação simples

Os algoritmos de ordenação simples compartilham algumas características comuns entre si, como a implementação simples e o baixo consumo de memória, sendo normalmente executdos inplace, ou seja, na mesma estrutura que armazena os dados a serem ordenados.

Em alguns casos, estes algoritmos são também suficientemente eficientes para pequenos volumes de dados. Uma característica interessante que é aproveitada por alguns algoritmos mais eficientes (e complexos), quando o número de elementos a ser ordenados é pequeno.

Outra característica desses algoritmos é a baixa eficiência esperada, quando o número de elementos a ser ordenados é maior. Estes algoritmos são reconhecidos pela sua ineficiência nesses casos.

Insertion Sort

O insertion sort é um algoritmo de ordenação que a cada iteração, adiciona um novo elemento à coleção de elementos já ordenados. Este novo elemento é inserido mantendo a ordenação da coleção.

Entre suas principais características estão a simples implementação (existe uma implementação do algoritmo escrita com 3 linhas em linguagem C), a possibilidade de utilizar o algoritmo online, para manter a seqüência ordenada mesmo com a inserção de novos elementos. Além disso, o algoritmo é estável com relação às chaves, mantendo a posição relativa das chaves originais com mesmo valor.

O algoritmo inicia a ordenação da seqüência de elementos com uma sub-lista dos elementos que já esteja ordenada. Esta lista inicial possui um único elemento, uma vez que em uma lista de um único elemento, todos os elementos respeitam a restrição para que a lista esteja ordenada.

Na primeira iteração, o segundo elemento da seqüência a ser ordenada é inserido na lista de elementos já ordenados, mantendo esta lista ordenada. Ao final da primeira iteração, teremos uma lista ordenada de dois elementos. A cada nova iteração, o próximo elemento da seqüência é selecionado, e adicionado à lista ordenada, aumentando-a em um elemento. Esta adição é realizada movendo o elemento até que a lista esteja novamente ordenada.

A Figura 1 mostra uma animação da execução do algoritmo Insertion Sort, o Algoritmo 1 mostra uma implementação em Python do algoritmo de ordenação por inserção.

Algoritmo Insertion Sort

Implementação em Pyton do Insertion Sort

def insertion_sort(data):
    for i in range(1,len(data)):
        j = i - 1
        while j >= 0 and data[i] < data[j]
            data[i], data[j] = data[j], data[i]
            j--
            i--
    return data

O algoritmo Insertion Sort, possui dois laços de iteração. No laço mais externo, o algoritmo itera sobre todos os elementos da seqüência original, e a cada execução do laço mais interno, faz com que o algoritmo itere sobre todos os elementos já ordenados.

Dessa forma, temos um algoritmo que executa n iteraçoes (tamanho da entrada), que executa k iterações sobre os elementos já ordenados. Como $k = n$, o algoritmo executa $n*n$ operações. De fato, o algoritmo _Insertion Sort_ tem um custo de execução de $O(n^2)$.

Note que o número de operações de troca são similares ao número de operações de comparação (também na ordem de $n^2$). Este número de trocas pode ser diminuido utilizando-se uma [lista encadeada] como estrutura de dados de armazenamento.

Caso os dados de entrada já estejam ordenados, o algoritmo não irá executar nenhuma iteração no laço interno, executando apenas n comparações.

No entanto, o algoritmo pode realizar todas as operações na estrutura de dados original, não sendo necessária memória auxiliar para executá-lo. Diz-se então, o algoritmo pode ser executado inplace, ou que seu consumo de memória é constante, independente do tamanho da entrada, sendo, com relação ao consumo de memória, um algoritmo de ordem $O(1)$.

Para garantir a estabilidade do algoritmo é importante que o teste do laço interno utilize a comparação $<$ e não $\leq$. Caso fosse utilizado $\leq$, o comportamento das chaves não seria estável.

Selection Sort

O Selection Sort é o algoritmo de ordenação que tem, provavelmente, o conceito mais simples de compreender, no entanto, é um algoritmo que, em geral, é menos eficiente até mesmo que o insertion sort, para a maioria dos casos. Além da ineficiência, o algoritmo não é estável com relação as chaves quando implementado utilizando vetores e sem uso de memória auxiliar.

O algoritmo divide os dados em duas partes, uma sub-lista de elementos já ordenados, que é criada do menor para o maior, e uma sub-lista com os elementos ainda não selecionados, formada pelos outros elementos da seqüência. A cada iteração, o algoritmo seleciona o menor elemento da sub-lista de elementos não ordenados e adiciona ao final da sub-lista de elementos já ordenados.

A Figura 2 mostra uma animação da execução do algoritmo Selection Sort, o Algoritmo 2 mostra uma implementação em Python do algoritmo de ordenação por seleção.

Algoritmo Selection Sort

Implementação em Python do Selection Sort

def selection_sort(data):
    for i in range(0,len(data)-1):
        index = i
        for j in range(i+1,len(data)):
            if data[j] < data[index]:
                index = j
        data[i],data[index] = data[index],data[i]
    return data

Uma vantagem do Selection Sort sobre outros algoritmos é o reduzido número de trocas efetuadas, apesar do alto número de comparações, o que pode fazer com que o algoritmo seja interessante quando o custo de escritas seja alto (como, por exemplo, quando se utiliza memória flash).

O custo de execução do algoritmo é $O(n^2)$. Podemos ver isso facilmente, pois para achar o menor elemento, na primeira iteração, são necessárias $(n-1)$ comparações, na segunda iteração $(n-2)$ comparações, e assim por diante, até que nas duas últimas iterações serão realizadas 2 e 1 comparações. Somando o número de comparações de cada iteração para obter o número total de comparações, temos que

$$(n-1) + (n-2) + \ldots + 2 + 1 = \frac{n(n-1)}{2}$$

O número de trocas, no entanto é apenas $O(n)$, pois as trocas são realizadas no laço externo, que é executado apenas uma vez para cada elemento da seqüência.

O algoritmo também não garante a estabilidade das chaves quando implementado com consumo de memória constante ($O(1)$) para ordenar vetores. Como no exemplo abaixo:

$$ (2,b) (4,c) (2,a) (1,b) (3,a) $$

Na primeira iteração, o menor elemento é o elemento $(1,b)$, que será trocado com o primeiro elemento da seqüência.

$$ \textbf{(2,b)} (4,c) \textbf{(2,a)} \textit{(1,b)} (3,a) $$

Após a troca, a ordem original dos elementos $(2,a)$ e $(2,b)$ foi alterada, e não há garantia que seja recuperada.

$$ \textit{(1,b)} (4,c) \textbf{(2,a) (2,b)} (3,a) $$

O algoritmo pode ser implementado como um algoritmo de ordenação estável utilizando listas encadeadas, ou copiando os dados para um outro vetor.

Bubble Sort

O algoritmo de ordenação Bubble Sort faz parte de uma família de algoritmos de ordenação simples, porém altamente ineficientes que só apresentam vantagens por interesse acadêmico, pela facilidade de análise e interesse teórico sobre os algoritmos.

O Bubble Sort funciona comparando elemento a elemento da seqüência e trocando os elementos de posição caso estejam em posições trocadas. A cada iteração do algoritmo, o elemento de maior valor será posicionado na sua posição final (Algoritmo 3).

Implementação em Python do Bubble Sort

def bubble_sort(data):
    for i in range(0,len(data)):
        for j in range(len(data)-1,i,-1):
            if data[j] < data[j-1]:
                data[j],data[j-1] = data[j-1],data[j]
    return data

A Figura 3 mostra a animação de uma execução do algoritmo em um conjunto de dados.

Algoritmo Bubble Sort

O algoritmo realiza um grande número de comparações e trocas entre os elementos, sendo um algoritmo de ordem $O(n^2)$. No entanto, o algoritmo pode ser otimizado para trabalhar razoavemente bem em seqüências onde o número de elementos fora do lugar é pequeno. Neste caso, é possível implementar o algoritmo como mostra o Algoritmo 4. Devido a forma como o algoritmo funciona, quando uma iteração termina sem realizar substituições, o algoritmo pode ser encerrado, pois a seqüência já está ordenada.

Implementação em Python do Bubble Sort com otimização

def bubble_sort(data):
    for i in range(0,len(data)-1):
        swap = False
        for j in range(len(data)-1,i,-1):
            if data[j] < data[j-1]:
                data[j],data[j-1] = data[j-1],data[j]
                swap = True
        if swap == True:
            break
    return data

Como o algoritmo só troca chaves que estejam invertidas, quando chaves iguais estão adjacentes, não é efetuada nenhuma troca, fazendo com que o algoritmo garanta a estabilidade das chaves.

Além da estabilidade, o algoritmo pode executar todas as operações inplace, não necessitando de memória para armazenamento temporário dos dados ordenados.

Algoritmos de ordenação eficientes

Algoritmos eficientes de ordenação baseados em comparaçào de elementos possuem um limite de eficiência de $O(n \lg n)$ (onde $\lg n$ é o logaritmo de base 2 de n - $\log_2n$). Embora mais complexos que os algoritmos de ordenação simples, estes algoritmos são normalmente muito eficientes para conjuntos de dados randômicos, no entanto podem ter sua eficiência reduzida em alguns casos, como dados já ordenados, ou com a odrenação invertida da chave, ou quando os dados estão parcialmente ordenados. Muitos destes algoritmos são também instáveis com relação às chaves, o que pode ser uma característica importante para a aplicação.

Os algoritmos de ordenação eficientes mais conhecidos são o Quicksort, o Mergesort e o Heapsort. Outros algoritmos eficientos são baseados nestes algoritmos, com modificações que minimizam ou resolvem deficiências que os algoritmos originais podem ter, como os algoritmos Timsort, baseado no mergesort, e o algoritmo Introsort, baseado nos algoritmos quicksort e heapsort.

Merge Sort

O algoritmo Merge Sort é um algoritmo de ordenação que segue o paradigma de divisão e conquista. Concetualmente, o algortimo funciona dividindo a seqüênca a ser ordenada em duas sub-listas, e então, recursivamente divide cada uma das sub-listas em duas listas, até que as listas possuam um único elemento. A partir deste momento, as sub-listas adjacentes são fundidas em uma lista de forma que nova lista também esteja ordenada. O Algoritmo 5 mostra o pseudo-código para a versão recursiva do algoritmo.

Algoritmo Merge Sort

mergesort(data, start, end):
    if (start - end) > 1:
        midpoint = start + ((start+ end)/2)
        merge_sort(data, start, midpoint)
        merge_sort(data, midpoint+1, end)
        merge(data, start, midpoint, end)

A parte mais importante do algoritmo é a função de fusão das sub-listas. A função apresentada aqui (Algoritmo 6) assume uma que as sub-listas são parte da lista original, e que ambas já estão ordenadas. Para que esta rotina funcione com eficiência, é necessário que seja utilizada uma cópia das sublistas.

Função merge do Mergesort

merge(data, start, midpoint, end):
    L = copy_array(data, start, midpoint)
    R = copy_arary(data, midpoint+1, end)
    i = 0
    j = 0
    for k = start to end:
        if i <= midpoint  and  (j > end or L[i] <= R[j]))
            data[k] = L[i]
            i++
        else
            data[k] = R[j]
            j++

O custo do algoritmo Mergesort apresenta custo de execução $O(N \lg N)$, quando implementado como apresentado aqui, com consumo de memória $O(N)$. Existem implementações que utilizam uma quantidade constante de memória auxiliar, no entanto, a função de fusão das sub-listas é mais complexa e menos eficiente, sendo executada com $O(N \lg^2 N)$ operações.

O algoritmo Mergesort apresenta três vantagens em relação aos outros algoritmos eficientes, ser conceitualmente simples, ter garantia de eficiência independente da distribuição dos dados de entrada, e por ser um algoritmo estável com relação às chaves.

Diversos sistemas utilizam o mergesort ou varições do algoritmo. Entre os sistemas que utilizam variações do mergesort estão a lingugem Perl, desde a versão 5.8, a linguagem Java, que o utiliza desde a versão 1.3, e a partir do JDK 7 utiliza o Timsort, algoritmo híbrido baseado no mergesort e no insertion sort, também utilizado na linguagem Python.

Quick Sort

O algoritmo de ordenação Quicksort é um algoritmo de ordenação, desenvolvido por divisão e conquista, que ordena os dados criando duas listas, onde uma das listas contém os valores menores que um determinado valor (pivot) e a outra lista contém os números maiores que este valor, logo, após uma iteração, a posição do elemento utilizado como pivot é conhecida. As duas listas criadas são então ordenadas, com o mesmo algoritmo, recursivamente. O Algoritmo 7 mostra o pseudocodigo para o quicksort.

O particionamento é o ponto chave do quicksort, e é desenvolvido de forma que consiga rearranjar os dados da lista, sem o uso de memória auxiliar. A eficiência desse algoritmo é muito importante para determinar a eficiência do algoritmo de ordenação. Encontramos na literatura dois esquemas de particionamento geralmente adotados na implementação do quicksort, os esquemas de Loruto e Hoare. Uma alternativa a estes esquemas de particionamento quando se esperam muitos valores iguais é o particionamento de Dijkstra.

O algoritmo Quicksort deve ser modificado de acordo com o resultado do esquema de particionamento utilizado. A utilização do particionamento de Lomuto exige a implementação do quicksort utilizando o Algoritmo 7, uma vez que o esquema de particionamento posiciona o elemento que representa o pivot na posição final que ocupará.

Algoritmo Quicksort utilizando o particionamento de Lomuto

quicksort(data, start, end)
    if start < end
        pivot = select_pivot(data, start, end)

        midpoint = lomuto_partition(data, start, end, pivot)

        quicksort(data, start, midpoint - 1)
        quicksort(data, midpoint + 1, end)

Utilizando o particionamento de Hoare o algoritmo quicksort deve ser alterado, modificando as chamadas recursivas, pois o particionamento divide as listas, mas não posiciona o pivot numa posição definitiva, logo, o índice retornado pelo esquema de particionamento deve ser novamente utilizado nas chamadas recursivas. A alteração faz com que a chamada recursivas para a lista dos valores menores seja modificada para quicksort(data, start, midpoint), ao invés de quicksort(data, start, midpoint - 1) como mostra o Algoritmo 8.

Algoritmo Quicksort modificado para o Particionamento de Hoare

quicksort(data, start, end)
    if start < end
        pivot = select_pivot(data, start, end)

        midpoint = hoare_partition(data, start, end, pivot)

        quicksort(data, start, midpoint)
        quicksort(data, midpoint + 1, end)

Utilizando o particionamento de Dijkstra, o algortimo quicksort deve levar em consideração que o esquema de particionamento retorna os limites dos conjuntos de valores menores e maiores que o pivot, uma vez que o pivot pode ser um conjunto de elementos com o mesmo valor. A implementação utilizando este esquema de particionamento pode ser vista no Algoritmo 9.

Algoritmo Quicksort modificado para o Particionamento de Dijkstra

quicksort(data, start, end)
    if start < end
        pivot = select_pivot(data, start, end)

        min,max = dijkstra_partition(data, start, end, pivot)

        quicksort(data, start, min)
        quicksort(data, mak, end)

O algoritmo Quicksort, é um dos algoritmos de ordenação por comparação mais eficientes, e artigos comparando-o a outros algoritmos afirmam que este seria o algoritmo mais eficiente para dados randômicos. No entanto, existem casos especiais, onde, dependendo da distribuição dos dados de entrada, a eficiência do algoritmo é diminuída, ficondo comparável a dos algoritmos simples.

Em geral, o algoritmo quicksort realiza a ordenação de uma lista de $N$ elementos executando $O(N \log_2 N)$ operações. Porém dependendo da escolha do pivot, o algoritmo de particionamento pode não conseguir dividir a lista em duas, separando apenas um elemento. Por exemplo, ao ordernar a lista $\langle 1,2,3,4,5,6 \rangle$, ao utilizar o particionamento de Lomuto (Algooritmo 7), o resultado seria $\langle 1,2,3,4,5 \rangle$, como lista com os valores menores que o pivot, o pivot $6$ na sua posição definitiva, e uma lista vazia como a lista dos valores maiores que o pivot. Ao chamar recursivamente o algoritmo, o mesmo aconteceria com a nova lista, e como resultado, o algoritmo seria executado N vezes, e a cada vez, seriam processados todos os elementos restantes da lista. Este comportamento, é o mesmo apresentado pelo algoritmo Selection Sort, cujo número de operações necessárias para ordenar uma lista de N elementos é $O(N^2)$.

Mesmo utilizando o particionamento de Hoare, que não escolhe, necessariamente, um elemento existente na lista a ser particionada, ou seja, independente da forma como se escolha o pivot, ou do esquema de particionamento utilizado, sempre pode haver uma ordenação dos dados com o qual o algoritmo Quicksort tem um comportamento ineficiente.

Apesar de eficiente para conjuntos randômicos de dados, o algoritmo pode, em algumas sub-listas, degenerar para o comportamento menos eficiente, fazendo com que não exista garantia do custo total de execução, o que pode impedir o uso do algoritmo em algumas aplicações, como aplicações de tempo real, onde deve haver garantia no tempo de entrega das operações.

O consumo de memória do algoritmo no entanto é relativamente baixo, levando-se em consideração que o algoritmo executa uma série de chamadas recursivas, o que faz quem que utilize memória da pilha de chamadas. Esse consumo é de $O(\lg N)$, mas só é garantido se a cada recursão, a lista maior for ordenada antes da lista menor. O mesmo comportamento ocorre na implementação iterativa, que é realizada simulando-se as chamadas recursivas em uma pilha.

Outra característica do algortimo quicksort é que para manter a eficiência, ao ser implementado utilizando vetores, é não garantir a estabilidade das chaves. Existem implementações estáveis implementadas utilizando listas encadeadas, ou que ou sacrificam a eficiência. Quando implementado em listas encadeadas, o algoritmo não utiliza técnicas que procuram evitar o uso de valores "ruins" de pivots, devido ao alto custo do acesso randômico a elementos de uma lista.

Heapsort

O Heapsort é um algoritmo de ordenação por comparação que utiliza uma estrutura de heap para organizar os elementos e otimizar o processo de ordenação. Pode ser visto como um Selection Sort melhorado, dividindo os dados em uma região contendo os não ordenados, e em outra, os já ordenados, e a cada iteração seleciona o maior elemento da região não ordenada e o move para a região já ordenada. Como utiliza um heap máximo, a seleção do maior elemento é muito eficiente $O(1)$, ao contrário da procura linear executada pelo selection sort.

O algoritmo heapsort (Algoritmo 10) possui duas fases, sendo a primeira, a criação de um heap máximo a partir dos dados, e a segunda, a fase de ordenação por seleção do maior elemento do heap, e o seu posicionamento no final do array. Como tanto a criação do heap, quanto a ordenação dos elementos pode ser executada inplace, o heapsort apresenta como vantagem o baixo custo com relação ao consumo de memória. Ao contrário do Quicksort, que necessita de memória para a pilha de recursão, o heapsort não exige nenhuma memória para armazenamento auxiliar, podendo ser implementado com consumo de memória constante, independente do tamanho dos dados a serem ordenados ($O(1)$).

Algoritmo de ordenação Heapsort

heapsort(data[]):
    heap = heapify(data)
    while not heap.empty
        next = heap.size - 1
        data[next] = heap.pop()

O laço de execução do algoritmo deve executar uma vez para cada um dos elementos a serem ordenados ($N$), onde a operação pop() do heap será executada, cada vez com custo $O(\lg N)$, que mostra, claramente, que o custo do algoritmo será $O(N\lg N)$. Este custo é garantido, independente do custo de construção do heap (que pode ser até linear, $O(N)$), e independente da organização original dos dados (ao contrário, por exemplo, do Quicksort). Esta é outra vantagem do algoritmo heapsort, pois matém sua eficiência em qualquer caso.

Apesar da eficiência teórica, em geral, o Quicksort é um algoritmo mais eficiente que o Heapsort, e variações do Quicksort e do Mergesort são mais utilizadas em diversos sistemas.

Algoritmos de Ordenação Híbridos

Nos algoritmos de ordenação por comparação apresentados são encontradas diversas vantagens e desvantagens em cada um deles. Uma das formas de amenizar as desvantagens de um algoritmo, é modificá-lo com características de outro algoritmo, tentando dessa forma obter um algoritmo com as vantagens de um, mas sem as suas desvantagens (ou, ao menos, atenuando-as). Estes algoritmos que misturam técnicas são os algoritmos de ordenação por comparação híbridos.

Introsort

O algoritmo de ordenação Introsort foi desenvolvido por David Musser para garantir um algoritmo de ordenação genérico para a biblioteca padrão da linguagem C++ que tivesse um caso médio eficiente, e um pior caso ótimo.

O introsort inicia executando o quicksort, e monitora as recursões, de forma que, quando há indícios que o quicksort está degenerando em direção ao seu pior caso, substitui o algoritmo e ordena os dados restantes utilizando o heapsort, que embora seja mais lento, na média, não sofre do problema de eficiência no pior caso.

Sabendo que idealmente, o quicksort executaria, no melhor caso, $lg N$ recursões (onde $lg N$ representa $\log_2 N$), podemos definir um limite máximo de recursões, e ao atingir este número de recursões, trocar o algoritmo. Podemos, por exemplo, aceitar que o quicksort precise executar 50% mais operações que o normal, e se passar disso, inicia-se o heapsort. Esta implementação do introsort é apresentada como o Algoritmo 11, onde o ponto de entrada é a função sort(), que calculará o número máximo de recursões, e iniciará a ordenação.

Algoritmo de ordenação Introsort

sort(data):
    lg_n = int(log(length(data)) / log(2))
    max_depth = lg_n + (lg_n / 2)
    introsort(data, 0, length(data), max_depth)

introsort(data, start, end, depth):
    if end - start <= 1
        return
    if depth > 0
        p = partition(data, start, end)
        introsort(data, start, p, depth - 1)
        introsort(data, p + 1, end, depth - 1)
    else:
        heapsort(A)

Os algoritmos de particionamento utilizados para o Quicksort são os mesmos utilizados pelo Introsort.

Resumo dos Algoritmos de Ordenação

Algoritmo Melhor Caso Caso Médio Pior Caso Memória Estável
Insertion $O(N)$ $O(N^2)$ $O(N^2)$ $O(1)$ Sim
Selection $O(N^2)$ $O(N^2)$ $O(N^2)$ $O(1)$ Não
Buble $O(N)$ $O(N^2)$ $O(N^2)$ $O(1)$ Sim
Mergesort $O(N\lg N)$ $O(N\lg^2 N)$ $O(N)$ Sim
Quicksort $O(N\lg N)$ $O(N\lg N)$ $O(N^2)$ $O(\lg N)$ Não
Heapsort $O(N\lg N)$ $O(N\lg N)$ $O(N\lg N)$ $O(1)$ Não
Introsort $O(N\lg N)$ $O(N\lg N)$ $O(N\lg N)$ $O(\lg N)$ Não