Algoritmos de ordenação

Todos os dias, ao usarmos sistemas computacionais, usarmos um recurso que parece trivial, mas que merece especial atenção de nós, profissionais da área de Computação. Trata-se da ordenação de registros.

Esse recurso é muito utilizado não apenas em programas de produtividade, como uma planilha do Google Docs, mas também nas plataformas de compra e redes sociais.

• Já parou para pensar que, quando você lista os itens por menor preço no Mercado Livre, está aplicando uma ordenação nos resultados da busca?
• Da mesma forma, a ordem que as publicações aparecem no feed do Instagram certamente é diferente da ordem que as mesmas publicações podem aparecer para outro usuário que segue as mesmas contas.

🤯 Entendendo a importância

Como comentado anteriormente, de tão comum, a ordenação de registros pode parecer banal, mas não é. Além de proporcionar comodidade, como no caso do Mercado Livre, a ordenação de registros facilita a recuperação de dados.

Embora faça muito sentido no contexto computacional, essa ideia também se aplica aos seres humanos. Antes dos smartphones ficarem populares, usávamos agendas de telefone, em que as pessoas eram listadas em ordem alfabética.

Logo, se a ideia é encontar o número de telefone do Tibúrcio, não faz sentido começar a busca pela letra A. Pode-se pular para a segunda metade da lista.

🔑 O conceito de chave

Você pode ter observado que, nas aulas sobre estruturas de dados, usamos uma estrutura chamada REGISTRO, que continha um único membro: a variável int chave:

typedef struct{
    int chave;
} REGISTRO;

Como explicado durante as aulas, esse atributo chave existe por uma razão especial. Agora, descobriremos qual é. O atributo chave é utilizado para controlar a ordenação do algoritmo.

De fato, em uma lista de itens, podemos ter diversos membros na estrutura REGISTRO. Entretanto, para ordenar o vetor, consideraremos apenas um desses atributos: o atributo chave.

🧐 Aspectos do algoritmo

Como discutiremos na aula de hoje, os algoritmos de ordenação são muito importantes e, por isso, possuem diversas características interessantes. Aqui, vamos discutir algumas delas:

Estabilidade do algortimo

Um algoritmo de ordenação é considerado estável se, durante o processo de ordenação, os itens com chaves iguais continuam na mesma ordem original. Observe o exemplo a seguir:

Observe que dois personagens possuem a mesma chave, H. No vetor original, a imagem de Harry aparece antes da imagem de Hermione. Um algoritmo estável irá manter essa precedência ao ordenar o vetor.

Um algoritmo não estável, por sua vez, mudará a ordem dos elementos. Observe que Hermione, no último caso, passa a aparecer antes de Harry.

Uso de memória (in situ)

Os algoritmos de ordenação também são analisados quanto ao uso de memória. Se o algoritmo é capaz de ordenar o vetor sem ter de copiá-lo, é dito que esse algoritmo é in situ. Ziviani (2017) reforça que os algoritmos de ordenação para listas encadeadas são usados apenas em ocasiões especiais, já que fazem uso de espaço adicional para armazenar os apontadores.

Desempenho

Os algoritmos de ordenação interna (que atuam na memória principal) são classificados como simples ou eficientes. Os algoritmos que adotam métodos simples são úteis quando o vetor a ser ordenado é pequeno. Esses algoritmos tem custo de O(n²). Os métodos eficientes, por sua vez, requerem apenas O(n lg n) comparações.

Nos algoritmos de ordenação, as operações relevantes para o cálculo são as comparações e atribuições. Em Projeto e Análise de Algoritmos, o cálculo de complexidade do algoritmo é apresentado a fundo.