Introdução aos Algoritmos de Ordenação em Python

Algoritmos de Ordenação

Ordenar conjuntos de coisas é uma tarefa costumeira em nossa vida. Em se tratando de computadores, como geralmente lidamos com grandes volumes de dados, é desejável ter alguma ordem nesses dados para facilitar sua manipulação.

Por exemplo, procurar sua música favorita é mais fácil se a lista de músicas está ordenada. Encontrar a mediana de uma lista de elementos é também muito mais fácil se a lista estiver ordenada. Além disso, em algumas situações desejamos rearranjar um conjunto de dados de modo que items com o mesmo valor apareçam um do lado do outro. Isso também pode ser feito se ordenarmos o conjunto de dados.

Além desses exemplos, existem outras muitas situações em que é preciso ou conveniente ordenar uma lista de elementos. Nessa seção veremos várias estratégias para ordenar os elementos de uma lista.

Definição da tarefa de ordenação

De modo geral, podemos definir o problema de ordenação como:

Descrição da entrada: Uma sequência $n$ items $R_1, R_2, \dots, R_n$, chamados registros.
Descrição da tarefa: Ordenar o conjunto de registros em ordem crescente (ou decrescente) de chaves.
Descrição da saída: Retornar a sequência de entrada, ordenada na ordem especificada (crescente ou decrescente).

Cada registro mencionado na definição acima possui uma chave que governa o processo de ordenação. Dados adicionais, além da chave, podem estar presentes, mas não têm efeito na ordenação, exceto que eles devem ser carregados (movidos) como parte do registro. Entretanto, no nosso caso, para simplificar as explicações, os registros serão números inteiros ou strings, ou seja, cada registro é composto unicamente da chave. Além disso, sempre ordenaremos os registros em ordem crescente (novamente, para simplificar as explicações). Assim, podemos definir novamente o problema como abaixo:

Descrição da entrada: Uma sequência $S$ de $n$ números inteiros ou de strings.
Descrição da tarefa: Ordenar os elementos da sequência em ordem crescente.
Descrição da saída: Retornar a sequência $S$ de entrada, ordenada em ordem crescente.

Neste capítulo, aprenderemos diversos algoritmos para resolver o problema de se ordenar uma lista de elementos. Como você verá, os algoritmos de ordenação ilustram vários conceitos importantes em Ciência da Computação e usam vários paradigmas (estratégias) de projeto de algoritmos que, se assimilados, nos ajudarão a entender muitos outros algoritmos.

Além disso, conhecer bem os diversos algoritmos de ordenação fará com que você seja capaz de decidir qual algoritmo é melhor para uma dada tarefa, o que nem sempre é algo trivial. Portanto, é importante que você entenda bem o funcionamento dos algoritmos e as estratégias que cada um deles usa para resolver o problema de ordenação.

Eficiência de algoritmos de ordenação

Como veremos adiante, a eficiência (sua complexidade assintótica) de um algoritmo de ordenação é determinada em termos de dois fatores:

Número de comparações de elementos feitas pelo algoritmo.
Número de vezes que elementos são trocados de lugar durante a execução do algoritmo.

Para cada um dos algoritmos de ordenação explicados, além de discutir seu funcionamento, responderemos também algumas perguntas importantes:

Qual é a complexidade assintótica do algoritmo no pior caso? Em algumas situações discutiremos também o caso médio de alguns algoritmos.
O algoritmo é in-place? Um algoritmo de ordenação in-place é um algoritmo que ordena o vetor de entrada sem usar um vetor auxiliar.
O algoritmo é estável? Um algoritmo de ordenação é estável se dois objetos com chaves idênticas aparecem na mesma ordem no vetor ordenado em que eles apareciam no vetor de entrada. Em outras palavras, algoritmos de ordenação estáveis preservam a ordem relativa entre elementos com chaves iguais. Por exemplo, se um algoritmo estável for usado, e ordenarmos a seguinte lista [maçã, banana, melancia, uva], obteríamos a lista [banana, maçã, melancia, uva], ao passo que se usarmos um algoritmo não-estável, melancia poderia aparecer antes de maçã na lista.

O algoritmo de ordenação ideal

Um algoritmo ideal de ordenação deveria ter as seguintes propriedades:

Ser estável.
Ser in-place.
Possuir complexidade $O(n \log n)$ no pior caso. Explicaremos o por quê disso nas próximas seções.
Realizar $O(n)$ trocas de elementos (swaps) no pior caso.
Possuir complexidade $O(n)$ se o vetor de entrada estiver parcialmente ordenado ou se existirem poucas chaves distintas.

A tabela abaixo resume essas propriedades dos algoritmos que estudaremos nesta seção:

Tabela 1. Algoritmos de ordenação
Algoritmo	Inplace	Estável	Pior Caso	Caso Médio	Melhor caso
Seleção	Sim	Não	$O(n^2)$	$O(n^2)$	$O(n^2)$
Inserção	Sim	Sim	$O(n^2)$	$O(n^2)$	$O(n)$
Mergesort	Não	Sim	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$
Quicksort	Sim	Não	$O(n^2)$	$O(n \log n)$	$O(n \log n)$
Heapsort	Sim	Não	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$
???	Sim	Sim	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$

Como mostrado na última linha da tabela acima, nenhum algoritmo de ordenação possui todas as propriedades desejáveis. A melhor escolha de algoritmo de ordenação depende do contexto de uso do algoritmo. Portanto, é importante conhecer bem os algoritmos, entender como eles funcionam, e saber em quais situações cada um deles é melhor.

Playground


			
				# Use este espaço para praticar o que você aprendeu nesta seção.
				
				# Basta digitar o código no espaço abaixo e clicar 'run'.