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]:
- Compare 7 e 2: troque, obtendo [2, 7, 5, 1, 4];
- Compare 7 e 5: troque, obtendo [2, 5, 7, 1, 4];
- Compare 7 e 1: troque, obtendo [2, 5, 1, 7, 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]
| Algoritmo | Caso médio | Pior caso |
| Bubble Sort | O(n²) | O(n²) |
| Selection Sort | O(n²) | O(n²) |
| Insertion Sort | O(n²) | O(n²) |
| Quick Sort | O(n log n) | O(n²) |
| Merge Sort | O(n log n) | O(n log n) |
| Heap Sort | O(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]
| Algoritmo | Estável na versão usual | Memória auxiliar considerada |
| Bubble Sort | Sim | O(1) |
| Selection Sort | Não | O(1) |
| Insertion Sort | Sim | O(1) |
| Quick Sort | Não | Pilha O(log n) típica; O(n) no pior caso da versão recursiva simples |
| Merge Sort | Sim | O(n) em vetores na versão clássica |
| Heap Sort | Não | O(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ção | Critério determinante | Candidato a avaliar |
| Poucos elementos ou poucas inversões | Aproveitar a organização existente | Insertion Sort |
| Estabilidade e pior caso O(n log n) | Preservar empates com memória auxiliar disponível | Merge Sort |
| Pior caso O(n log n) e espaço constante | Restringir memória adicional | Heap Sort iterativo |
| Vetor de uso geral sem exigência de estabilidade | Bom desempenho esperado e estratégia de pivôs | Quick Sort ou variante adequada |
| Inteiros em faixa curta | Evitar comparações entre pares de chaves | Counting Sort |
| Chaves de vários dígitos bem definidos | Processar partes da representação | Radix 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
![[BLACK FRIDAY 2026] R$ 2 por dia – Cabeçalho](https://blog-preparatorio-static.infra.grancursosonline.com.br/wp-content/uploads/2026/10/23113511/black-friday-2026-2reais-por-dia-cabecalho.webp)
![[BLACK FRIDAY 2026] R$ 2 por dia – Post](https://blog-preparatorio-static.infra.grancursosonline.com.br/wp-content/uploads/2026/10/23113838/black-friday-2026-2reais-por-dia-post.webp)


