Algoritmos de ordenação: conceitos e principais tipos

Compare os principais algoritmos de ordenação, como Bubble Sort, Quick Sort e Merge Sort, e entenda complexidade, estabilidade e aplicações em concursos de TI

Por
Publicado em
12 min. de leitura

Fala, meus consagrados! Beleza?

Algoritmos de ordenação são procedimentos que reorganizam elementos conforme um critério, como números em ordem crescente, nomes em ordem alfabética ou produtos do menor para o maior preço. Eles produzem uma sequência ordenada preservando os elementos que compõem a coleção. [1]

Embora diferentes algoritmos possam chegar ao mesmo resultado, o trabalho realizado e o uso de memória variam. Uma solução adequada para poucos registros pode ser inadequada para milhões de elementos. Também existem situações em que preservar a ordem dos empates é um requisito.

Neste artigo, vamos conhecer os principais métodos, comparar suas características e acompanhar exemplos que ajudam tanto na programação quanto no estudo para concursos públicos de TI.

O que são algoritmos de ordenação?

Ordenar significa estabelecer uma sequência segundo uma chave de ordenação. A chave é a informação comparada para posicionar cada registro: preço, data, idade ou nome, por exemplo. O registro pode conter outros dados que acompanham essa chave durante as movimentações. [1]

Considere a sequência [7, 2, 5, 1, 4]. Ao ordená-la de forma crescente, obtemos [1, 2, 4, 5, 7]. Nenhum elemento foi eliminado ou acrescentado; as posições foram reorganizadas.

Em uma lista de estudantes, ordenar pela nota significa movimentar o registro completo, mantendo cada nota associada à pessoa correta. Ordenar somente uma coluna e perder essa associação produziria uma informação incorreta, mesmo que os números estivessem em ordem.

Ordenação também pode facilitar outras operações. A busca binária em um vetor, por exemplo, pressupõe uma organização compatível com o critério usado na pesquisa. Entretanto, ordenar possui um custo: nem sempre compensa ordenar uma coleção apenas para realizar uma única busca. [17]

Como avaliar um algoritmo de ordenação?

Os critérios centrais são o tempo de execução, a memória auxiliar, a estabilidade e as características dos dados. Também importam o custo das comparações e das movimentações e a forma como os registros estão armazenados. [1]

A notação Big O expressa um limite superior assintótico para o crescimento do custo conforme aumenta o tamanho da entrada. Neste artigo, n representa a quantidade de elementos. O(n²) indica crescimento quadrático; O(n log n) representa um crescimento geralmente mais favorável para entradas grandes. [2]

Isso não informa o número exato de segundos. Hardware, implementação e tamanho dos registros também influenciam o desempenho. Além disso, Big O não é sinônimo de pior caso: podemos descrever o melhor caso, o caso médio e o pior caso usando essa notação. [2]

Para comparar métodos, precisamos manter claras essas hipóteses. Uma afirmação como “Quick Sort é O(n log n)” fica incompleta se não especificar a análise considerada.

Bubble Sort

O Bubble Sort compara elementos adjacentes e troca suas posições quando estão fora da ordem desejada. Repetindo as passagens pelo vetor, os elementos avançam até suas posições corretas. [3]

Vamos acompanhar a primeira passagem, da esquerda para a direita, em [7, 2, 5, 1, 4]:

  1. Compare 7 e 2: troque, obtendo [2, 7, 5, 1, 4];
  2. Compare 7 e 5: troque, obtendo [2, 5, 7, 1, 4];
  3. Compare 7 e 1: troque, obtendo [2, 5, 1, 7, 4];
  4. Compare 7 e 4: troque, obtendo [2, 5, 1, 4, 7].

O maior valor já ficou no final, mas o restante ainda precisa de ordenação. O método repete o processo sobre a parte que falta ordenar.

Os custos médio e de pior caso são O(n²). Com parada antecipada quando uma passagem não realiza trocas, o melhor caso é O(n) para um vetor já ordenado. Sem essa otimização, não podemos atribuir automaticamente o melhor caso linear ao código. A versão usual usa memória auxiliar constante e é estável quando não troca elementos de chaves iguais. [3]

Selection Sort

O Selection Sort procura o menor elemento da parte ainda não ordenada e o coloca na próxima posição disponível. Depois, repete a seleção sobre os elementos restantes. Também existe a organização simétrica, que seleciona o maior para o final. [4]

Em [7, 2, 5, 1, 4], o menor é 1. Trocando-o com o primeiro elemento, obtemos [1, 2, 5, 7, 4]. Na etapa seguinte, o menor da parte restante é 2, que já está na posição adequada.

Mesmo que o vetor esteja ordenado, a versão clássica continua procurando o menor de cada trecho. Por isso, o número de comparações é quadrático. Em contrapartida, o número de trocas é O(n), uma característica relevante quando movimentar registros custa caro. [4]

A implementação usual por troca direta utiliza O(1) de memória auxiliar e não é estável. Isso não significa que toda variante de seleção seja necessariamente instável: alterações no modo de movimentar os registros podem mudar essa propriedade. [4]

Insertion Sort

O Insertion Sort mantém uma parte inicial ordenada e insere cada novo elemento na posição correta dentro dela. A ideia lembra organizar cartas na mão: cada carta recebida é encaixada entre as que já estão organizadas. [5]

Começando com [7, 2, 5, 1, 4], inserimos 2 antes de 7 e obtemos [2, 7, 5, 1, 4]. Depois, inserimos 5 entre 2 e 7, produzindo [2, 5, 7, 1, 4]. O processo continua com os demais elementos.

O custo é O(n²) no caso médio e no pior caso. Para uma entrada já ordenada, a versão usual realiza apenas as verificações necessárias para cada inserção e tem custo O(n). Ele também pode funcionar bem em entradas pequenas ou com poucas inversões. [5, 6]

Uma inversão ocorre quando um elemento maior aparece antes de um menor. Quanto mais movimentações forem necessárias para corrigir essas situações, maior será o trabalho. A implementação tradicional é estável e usa memória auxiliar constante, desde que os elementos iguais sejam tratados preservando sua ordem. [6, 17]

Quick Sort e o particionamento

O Quick Sort escolhe um elemento chamado pivô, reorganiza o trecho em partições e ordena recursivamente as partes. A forma de escolher o pivô e as regras de particionamento variam entre implementações. [7]

Na ilustração, utilizamos o último elemento como pivô, com valor 4, e um particionamento do tipo Lomuto. Os menores valores vão para a esquerda; os maiores, para a direita. Como as chaves do exemplo são distintas, não precisamos representar empates.

Figura 1. Após essa partição, o pivô 4 ocupa sua posição definitiva, mas os trechos [2, 1] e [7, 5] ainda precisam ser ordenados.

Particionar não significa ordenar completamente cada lado. A condição importante é posicionar os elementos no lado adequado ao pivô. O algoritmo continua trabalhando sobre as partições. O comportamento exato, inclusive se o pivô fica em uma posição definitiva naquela etapa, depende do esquema utilizado. [7, 8]

Por que o pior caso pode ser quadrático?

Com divisões equilibradas, há cerca de log n níveis de trabalho e um custo total O(n log n). Quando as divisões repetidamente deixam uma parte vazia e outra com quase todos os elementos, o custo pode chegar a O(n²). [8]

Isso pode acontecer em um vetor já ordenado se a implementação sempre escolher o último elemento como pivô. O problema está na combinação entre entrada e estratégia; não é correto afirmar que qualquer Quick Sort sempre tem seu pior caso em uma entrada ordenada.

A aleatorização do pivô ajuda a obter custo esperado O(n log n) sob as hipóteses usuais da análise, mas não elimina toda execução de pior caso. Muitas chaves repetidas também exigem atenção: um particionamento em três regiões, para menores, iguais e maiores, pode ser mais adequado do que certas versões em duas partes. [8, 19]

Merge Sort

O Merge Sort divide a coleção em partes menores, ordena essas partes e realiza a intercalação dos resultados. Na versão clássica, a divisão ocorre aproximadamente ao meio, independentemente do valor de um pivô. Seu custo é O(n log n) no pior caso. [9]

Para ordenar [7, 2, 5, 1], podemos separar [7, 2] e [5, 1]. Depois de ordenar cada metade, temos [2, 7] e [1, 5]. Na intercalação, comparamos os primeiros elementos disponíveis: sai 1, depois 2, depois 5 e, por fim, 7.

A ideia central é combinar sequências que já estão ordenadas. Isso diferencia a intercalação do particionamento do Quick Sort: no Merge Sort, o trabalho de combinação reúne as partes ordenadas em uma nova sequência.

Em vetores, a implementação clássica utiliza O(n) de memória auxiliar. Pode ser estável quando, diante de chaves iguais, a intercalação escolhe primeiro o registro que veio da parte esquerda. Implementações para listas encadeadas possuem características de memória diferentes. [10]

Heap Sort

O Heap Sort utiliza uma estrutura chamada heap. Para ordenar crescentemente, uma organização comum é construir um heap máximo, em que cada pai tem chave maior ou igual à de seus filhos. Isso garante o maior elemento na raiz, mas não significa que todo o vetor já esteja ordenado. [11]

O algoritmo troca a raiz com o último elemento da região ativa, reduz essa região e restaura a propriedade de heap. Repetindo o processo, os maiores valores são posicionados no final.

A construção do heap por baixo para cima pode ser feita em O(n). Depois, cada restauração exige até O(log n) e as extrações levam ao custo total O(n log n) no pior caso. Uma implementação iterativa no próprio vetor usa O(1) de memória auxiliar e não preserva, em geral, a estabilidade. [11]

Sua vantagem é combinar limite de pior caso O(n log n) com baixo consumo adicional de memória. Isso não garante que seja o mais rápido em toda situação concreta: acessos à memória e constantes da implementação também interferem.

Comparação de complexidade dos principais algoritmos

A tabela apresenta limites de tempo usuais para versões clássicas em vetores. No caso médio de Quick Sort, considera-se uma distribuição adequada dos pivôs, como na análise com chaves distintas e escolha aleatória. [3–11]

AlgoritmoCaso médioPior caso
Bubble SortO(n²)O(n²)
Selection SortO(n²)O(n²)
Insertion SortO(n²)O(n²)
Quick SortO(n log n)O(n²)
Merge SortO(n log n)O(n log n)
Heap SortO(n log n)O(n log n)

No melhor caso, Insertion Sort e Bubble Sort com parada antecipada podem ser lineares. Selection Sort continua fazendo uma quantidade quadrática de comparações. O código da questão deve orientar a análise, porque otimizações podem alterar o comportamento observado. [3, 4, 6]

Não confunda comparações com trocas. Selection Sort faz poucas trocas em relação a vários métodos elementares, mas continua precisando procurar o próximo menor elemento. Reduzir uma operação não implica reduzir todas as medidas de custo na mesma proporção.

O que significa ordenação estável?

Um algoritmo é estável quando preserva a ordem relativa de registros que possuem a mesma chave. Se Ana aparece antes de Caio e ambos têm chave 2, uma ordenação estável apenas por essa chave mantém Ana antes de Caio. [12]

Figura 2. A chave numérica define a ordenação; o nome identifica o registro. As duas saídas estão em ordem numérica, mas somente a primeira preserva o empate entre Ana e Caio.

No exemplo, a instabilidade pode surgir em Selection Sort: ao trocar o menor registro, Bia, com o primeiro, Ana, o resultado fica Bia, Caio e Ana. Ana e Caio não foram comparados para uma troca direta, mas sua ordem relativa se inverteu.

Estabilidade é útil em ordenações por múltiplos critérios. Se uma lista foi ordenada por nome e depois recebe uma ordenação estável por turma, os estudantes de cada turma mantêm a ordem por nome. Um algoritmo instável pode preservar um empate em uma execução; a diferença é que não oferece essa garantia geral. [12, 16]

O que é um algoritmo de ordenação in-place?

Um método in-place reorganiza os elementos na área de armazenamento original, sem precisar manter outra coleção completa para armazenar os registros durante a ordenação. Entretanto, é necessário verificar a convenção adotada para contabilizar memória auxiliar e pilha de chamadas. [13]

Em uma definição estrita de espaço auxiliar constante, exige-se O(1) de memória adicional. Na literatura, Quick Sort frequentemente é classificado como in-place porque seu particionamento ocorre no próprio vetor, embora a versão recursiva utilize pilha. Por isso, a classificação deve vir acompanhada do custo de espaço.

Na versão recursiva simples de Quick Sort, a pilha ocupa tipicamente O(log n) em partições equilibradas e pode atingir O(n) em uma execução degenerada. Recorrer apenas sobre a parte menor e tratar a maior iterativamente permite limitar a pilha a O(log n), mesmo mantendo a possibilidade de tempo quadrático. [8]

AlgoritmoEstável na versão usualMemória auxiliar considerada
Bubble SortSimO(1)
Selection SortNãoO(1)
Insertion SortSimO(1)
Quick SortNãoPilha O(log n) típica; O(n) no pior caso da versão recursiva simples
Merge SortSimO(n) em vetores na versão clássica
Heap SortNãoO(1) com restauração iterativa do heap

Estabilidade e uso de memória são propriedades diferentes. Insertion Sort combina estabilidade e espaço constante; Heap Sort tem espaço constante, mas é usualmente instável. Também não basta uma função alterar a coleção original para concluir que seu espaço auxiliar é O(1).

Quando usar Counting Sort ou Radix Sort?

Os métodos anteriores ordenam comparando chaves. Counting Sort e Radix Sort exploram a estrutura das chaves, o que pode permitir custos mais favoráveis em domínios apropriados. Eles não são substitutos universais para ordenações por comparação. [15, 18]

O Counting Sort conta ocorrências de chaves de um domínio discreto e usa essas contagens para organizar a saída. Na versão para inteiros em uma faixa de tamanho k, o custo é O(n + k). A implementação estável tradicional utiliza uma saída auxiliar e estruturas de contagem, com espaço O(n + k). [14]

Para [2, 0, 2, 1], as contagens são duas ocorrências de 2, uma de 0 e uma de 1. A sequência ordenada é [0, 1, 2, 2]. Se estivermos movimentando registros completos, será necessário posicioná-los de maneira a preservar os dados associados e, quando exigido, a estabilidade.

Considere ordenar muitas notas inteiras entre zero e cem: há apenas 101 valores possíveis. Nesse cenário, o tamanho da faixa pode ser administrável. Já poucos elementos espalhados entre zero e um bilhão tornam inadequada a alocação direta de um contador para cada valor possível. Importa o tamanho da faixa, não apenas a quantidade de valores distintos observados. [18]

O Radix Sort processa partes da chave em etapas. Na versão LSD, começa pelo dígito menos significativo e avança para os demais. A ordenação de cada etapa precisa ser estável para preservar o trabalho das etapas anteriores. Counting Sort pode cumprir esse papel. [15]

Com os números [21, 13, 12], uma passagem estável pelas unidades produz [21, 12, 13]. A passagem pelas dezenas produz [12, 13, 21]. Ao desempatar a dezena 1, a estabilidade mantém 12 antes de 13, conforme a ordem estabelecida pelas unidades.

Usando Counting Sort estável por dígito, o tempo é O(d(n + b)) e o espaço auxiliar é O(n + b), com reaproveitamento entre passagens. Aqui, d é a quantidade de dígitos processados e b é a base utilizada. Não se deve chamar esse custo de linear sem indicar as hipóteses sobre esses parâmetros. [14, 15]

Esses métodos são candidatos quando as chaves têm representação adequada e os custos de contagem ou de processamento por dígito compensam. Números negativos, textos de tamanhos variados e critérios especiais exigem adaptações.

Como escolher o algoritmo de ordenação?

A escolha deve começar pelos requisitos dos dados e da aplicação. Pergunte se a estabilidade é necessária, qual é a memória disponível, se existe exigência de pior caso e como são as chaves. Depois, considere se a entrada já está quase ordenada.

SituaçãoCritério determinanteCandidato a avaliar
Poucos elementos ou poucas inversõesAproveitar a organização existenteInsertion Sort
Estabilidade e pior caso O(n log n)Preservar empates com memória auxiliar disponívelMerge Sort
Pior caso O(n log n) e espaço constanteRestringir memória adicionalHeap Sort iterativo
Vetor de uso geral sem exigência de estabilidadeBom desempenho esperado e estratégia de pivôsQuick Sort ou variante adequada
Inteiros em faixa curtaEvitar comparações entre pares de chavesCounting Sort
Chaves de vários dígitos bem definidosProcessar partes da representaçãoRadix Sort

Esses critérios orientam a avaliação, sem estabelecer um vencedor universal. Um teste de desempenho só é útil quando representa os tamanhos, os registros e os padrões de entrada reais.

No desenvolvimento de sistemas, também é importante conhecer a biblioteca da linguagem. Em Python, sorted produz uma nova lista e list.sort modifica a lista existente; ambas as operações são estáveis. A escolha entre elas envolve o comportamento desejado para a coleção original. [16]

Algoritmos de ordenação em concursos públicos de TI

Para organizar o estudo, priorize complexidade, estabilidade, memória auxiliar e reconhecimento do procedimento pelo pseudocódigo. Confira como a banca e o edital tratam cada um desses pontos e pratique com as convenções de pseudocódigo utilizadas nas questões.

Bubble Sort costuma ser reconhecido por comparações e trocas entre vizinhos. Selection Sort procura um mínimo ou máximo no trecho restante antes da troca. Insertion Sort guarda um elemento e desloca os anteriores para inseri-lo na parte ordenada.

Observe o pseudocódigo, com índices iniciando em zero e avaliação lógica da esquerda para a direita com curto-circuito:

Para i de 1 até n – 1, inclusive, faça
chave <- A[i]
j <- i – 1
Enquanto j >= 0 e A[j] > chave, faça
A[j + 1] <- A[j]
j <- j – 1
FimEnquanto
A[j + 1] <- chave
FimPara

O procedimento é Insertion Sort. A parte à esquerda está ordenada e os elementos maiores são deslocados para abrir espaço à chave. Na entrada [3, 1, 2], a primeira inserção gera [1, 3, 2]; a segunda, [1, 2, 3].

O teste usa A[j] > chave, e não A[j] >= chave. Essa diferença permite que o elemento em processamento seja inserido depois dos anteriores com a mesma chave, preservando o empate nessa implementação. [17]

Ao analisar o pior caso, descreva uma entrada que o provoque no código apresentado. No Quick Sort, verifique o pivô e a partição; no Insertion Sort, acompanhe quantos deslocamentos cada inserção exige. Para memória, conte também a pilha quando houver recursão.

Por fim, execute um teste de mesa. Registre as alterações após cada passagem, inserção, partição ou extração. Reconhecer a transformação dos dados ajuda a interpretar variações de código que não utilizam os nomes dos algoritmos.

Espero que tenham gostado! 

Forte abraço e até a próxima jornada!
_________________________

Professor Rogerão Araújo

FAQ sobre algoritmos

O que são algoritmos de ordenação?

São procedimentos que reorganizam elementos segundo uma chave, como preço, data ou nome. A sequência final deve obedecer ao critério escolhido e manter os mesmos elementos da coleção original. [1]

Qual é a diferença entre Bubble Sort, Selection Sort e Insertion Sort?

Bubble Sort compara e troca vizinhos; Selection Sort escolhe o menor ou maior do trecho restante; Insertion Sort encaixa cada elemento na parte já ordenada. Todos têm custo quadrático no pior caso, mas diferem em trocas, melhor caso e estabilidade. [3–6]

Como funciona o Quick Sort?

Escolhe um pivô, particiona o trecho e ordena recursivamente as partes. Seu custo médio usual é O(n log n), sob as hipóteses da análise, e o pior caso pode ser O(n²). A estratégia de pivôs e a regra de particionamento influenciam o comportamento. [7, 8]

Qual é a diferença entre Quick Sort e Merge Sort?

Quick Sort reorganiza os dados em torno de pivôs; Merge Sort divide a coleção e intercala partes ordenadas. Na versão clássica em vetores, Merge Sort garante O(n log n) no pior caso e utiliza O(n) de memória auxiliar. Quick Sort pode ter pior caso quadrático. [7, 9, 10]

O que significa dizer que um algoritmo de ordenação é estável?

Significa que ele preserva a ordem relativa dos registros com chaves iguais. Se Ana aparece antes de Caio e ambos têm a mesma chave, a ordenação estável mantém Ana antes de Caio ao ordenar apenas por essa chave. [12]

O que é um algoritmo de ordenação in-place?

É um método que reorganiza os elementos na área original, sem outra coleção completa para os registros. Para uma análise precisa, confira a definição de espaço auxiliar adotada e contabilize a pilha de chamadas de implementações recursivas. [13]

Quando usar Counting Sort ou Radix Sort?

Counting Sort é candidato para chaves inteiras em uma faixa pequena o suficiente para contagem direta. Radix Sort pode ser adequado para chaves processadas por dígitos. Avalie faixa, quantidade de dígitos, base, memória e estabilidade das passagens. [14, 15]

O que mais cai sobre algoritmos de ordenação em concursos públicos?

Para a revisão, priorize complexidade por caso, estabilidade, espaço auxiliar e identificação por pseudocódigo. Questões também podem exigir o resultado de passagens, partições, intercalações e operações com heap. Pratique testes de mesa e verifique as condições de pior caso no código apresentado, conforme o edital.

Referências técnicas

[1] NIST – Sort: https://xlinux.nist.gov/dads/HTML/sort.html

[2] NIST – Big-O notation: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

[3] NIST – Bubble sort: https://xlinux.nist.gov/dads/HTML/bubblesort.html

[4] NIST – Selection sort: https://xlinux.nist.gov/dads/HTML/selectionSort.html

[5] NIST – Insertion sort: https://xlinux.nist.gov/dads/HTML/insertionSort.html

[6] OpenDSA – Insertion Sort: https://opendsa-server.cs.vt.edu/OpenDSA/Books/Catalog/html/InsertionSort.html

[7] NIST – Quicksort: https://xlinux.nist.gov/dads/HTML/quicksort.html

[8] OpenDSA – Quicksort: https://opendsa-server.cs.vt.edu/OpenDSA/Books/Catalog/html/Quicksort.html

[9] NIST – Merge sort: https://xlinux.nist.gov/dads/HTML/mergesort.html

[10] OpenDSA – Implementing Mergesort: https://opendsa-server.cs.vt.edu/OpenDSA/Books/Catalog/html/MergesortImpl.html

[11] OpenDSA – Heapsort: https://opendsa-server.cs.vt.edu/OpenDSA/Books/Catalog/html/Heapsort.html

[12] NIST – Stable: https://xlinux.nist.gov/dads/HTML/stable.html

[13] NIST – In-place sort: https://xlinux.nist.gov/dads/HTML/inplacesort.html

[14] MIT OpenCourseWare – Recitation 7: Sort Stability, Counting Sort and Radix Sort: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/cb7df5fee9cb62e0810616491cdd1194_MIT6_006F11_rec07.pdf

[15] NIST – Radix sort: https://xlinux.nist.gov/dads/HTML/radixsort.html

[16] Python – Sorting Techniques: https://docs.python.org/3/howto/sorting.html

[17] Cornell University – Sorting Algorithms: https://www.cs.cornell.edu/courses/cs2110/2026fa/lectures/lec07/

[18] NIST – Counting sort: https://xlinux.nist.gov/dads/HTML/countingsort.html

[19] Princeton University – Quicksort e particionamento em três regiões: https://algs4.cs.princeton.edu/23quicksort/index.php

Por
Publicado em
12 min. de leitura

Deixe um comentário

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *