[Curso de AEeD - Aula 09] Ordenação - Seleção

Algoritmo de seleção

Esta seção trata de outro algoritmo de ordenação bem conhecido.  Ele usa a seguinte estratégia: seleciona o menor elemento do vetor, depois o segundo menor, depois o terceiro menor, e assim por diante:

// Esta função rearranja o vetor v[0..n-1]
// em ordem crescente.

void
selecao (int n, int v[])
{
   int i, j, min, x;
   for (i = 0; i < n-1; ++i) {
      min = i;
      for (j = i+1; j < n; ++j)
         if (v[j] < v[min])  min = j;
      x = v[i]; v[i] = v[min]; v[min] = x;
   }
}

Para entender por que o algoritmo está correto, basta observar que no início de cada repetição do for externo, imediatamente antes da comparação de i com n-1, valem os seguintes invariantes:

1. o vetor  v[0..n-1]  é uma permutação do vetor original,
2. v[0..i-1] está em ordem crescente e
3. v[i-1]  ≤  v[i..n-1].

A tradução do terceiro invariante para linguagem humana é a seguinte: v[0..i-1] contém todos os elementos pequenos do vetor original e v[i..n-1] contém todos os elementos grandes.

0	crescente			i-1	i					n-1
110	120	120	130	140	999	666	999	666	999	666
pequenos					grandes

Os três invariantes garantem que no início de cada iteração v[0], . . , v[i-1] já estão em suas posições definitivas.  No início da última iteração, o vetor está em ordem crescente, como desejado.

Desempenho do algoritmo de seleção

Tal como o algoritmo de inserção, o algoritmo de seleção faz cerca de n2/2 comparações entre elementos do vetor no pior caso.  Diferentemente do algoritmo de inserção, o algoritmo de seleção também faz cerca de n2/2 no melhor caso.  Assim, o consumo de tempo do algoritmo é sempre proporcional a n2.

Em vista dessa análise (e de outras observações que faremos nos exercícios) o algoritmo de inserção é preferível ao de seleção.

Animações do algoritmo de seleção

• Applet de R. Sedgewick
• Animação de algoritmos de ordenação, de Nicholas André Pinho de Oliveira
• Select-sort com dança cigana, Universidade Sapientia (Romênia)

Exercícios 3

1. Escreva uma versão recursiva do algoritmo de ordenação por seleção.
2. Na função selecao, que acontece se trocarmos for (i = 0  por  for (i = 1?  Que acontece se trocarmos for (i = 0; i < n-1  por  for (i = 0; i < n ?
3. Na função selecao, troque a comparação  v[j] < v[min]  por  v[j] <= v[min].  A nova função continua correta?
4. Pior caso.  Descreva e analise uma instância de pior caso para o algoritmo de seleção, ou seja, um vetor v[0..n-1] que leva o algoritmo a executar o maior número possível de comparações.
5. Melhor caso.  Descreva e analise uma instância de melhor caso para o algoritmo de seleção, ou seja, um vetor v[0..n-1] que leva o algoritmo a executar o menor número possível de comparações.
6. Movimentação de dados.  Quantas vezes, no pior caso, o algoritmo de seleção copia um elemento do vetor de um lugar para outro?  Quantas vezes isso ocorre no melhor caso?
7. Escreva uma função que permute os elementos de um vetor inteiro v[0..n-1] de modo que eles fiquem em ordem decrescente. Inspire-se no algoritmo de seleção.

Exercícios 4

1. Ordenação de strings.  Escreva uma função que coloque em ordem lexicográfica um vetor de strings. Use o algoritmo de inserção.
2. Ordenação de arquivo.  Escreva uma função que rearranje as linhas de um arquivo de texto em ordem lexicográfica.  Compare com o utilitário sort.
3. Ordenação de structs.  Suponha que cada elemento de um vetor é um registro com dois campos: um é um inteiro e outro uma string:

      struct registro {int aa; char *bb;};
   

   Escreva uma função que rearranje o vetor de modo que os campos aa fiquem em ordem crescente.  Escreva outra função que rearranje o vetor de modo que os campos bbfiquem em ordem lexicográfica.
4. Desafio.  Invente um algoritmo de ordenação que seja mais rápido que o de inserção e o de seleção.
5. Embaralhamento aleatório?  Considere a seguinte antítese do problema de ordenação: fazer um embaralhamento aleatório dos elementos de um vetor v[0..n-1], ou seja, rearranjar os elementos do vetor de modo que todas as permutações sejam igualmente prováveis. Discuta e critique a seguinte solução (ela foi usada na distribuição européia do Windows 7 da Microsoft):

   void insercao_aleatoria (int n, int v[]) {
      int i, j, x;
      for (j = 1; j < n; ++j) {
         x = v[j];
         for (i = j-1; i >= 0 ; --i) {
            if (rand() > RAND_MAX/2) 
               v[i+1] = v[i];
            else break; }
         v[i+1] = x; } }
   

6. Ordenação de lista encadeada.  Escreva uma função que ordene uma lista encadeada. Inspire-se no algoritmo de inserção para vetores.  (Sua função precisa devolver alguma coisa?).
7. Ordenação de lista encadeada.  Escreva um função para ordenar uma lista encadeada. Imite o algoritmo de seleção para vetores.  (Sua função precisa devolver alguma coisa?).

Exercícios 5: aplicações

Muitos problemas podem ser reduzidos à ordenação de um vetor, ou seja, podem ser resolvidos com o auxílio de um algoritmo de ordenação (não necessariamente um dos algoritmos discutidos neste capítulo).

1. Anagramas.  Uma palavra é anagrama de outra se a sequência de letras de uma é permutação da sequência de letras da outra.  Por exemplo, aberto é anagrama derebato.  Digamos que duas palavras são equivalentes se uma é anagrama da outra.  Uma classe de equivalência de palavras é um conjunto de palavras duas a duas equivalentes.  Escreva um programa que receba um arquivo de texto contendo palavras (uma por linha) e extraia desse arquivo uma classe de equivalência máxima.   Aplique o seu programa a um arquivo que contém todas as palavras do português brasileiro.  (O arquivo é grande; portanto, o seu programa deverá ser muito eficiente.)
2. Valores distintos.  Dado um vetor v[0..n-1] de números inteiros, determinar quantos números distintos há no vetor (ou seja, determinar o tamanho do conjunto de elementos do vetor).
3. Mediana.  Seja v[0..n-1] um vetor de números inteiros, todos diferentes entre si.  A mediana do vetor é um elemento do vetor que seja maior que metade dos elementos do vetor e menor que (a outra) metade dos elementos.  Mais precisamente, a mediana de v[0..n-1] é um número m dotado de duas propriedades:  m é estritamente maior que exatamente ⌊(n-1)/2⌋ elementos do vetor e m é igual a algum elemento do vetor.  (Não confunda mediana com média. Por exemplo, a média de  1 2 99  é  51, enquanto a mediana é 2.)  Escreva um algoritmo que encontre a mediana de um vetor v[0..n-1] de números diferentes entre si.
4. Escalonamento de tarefas.  Suponha que n tarefas devem ser processadas em um único processador.  Dadas as durações t1, … , tn das tarefas, em que ordem elas devem ser processadas para minimizar o tempo médio de conclusão de uma tarefa?

Créditos para:

http://www.ime.usp.br/~pf/algoritmos/
Paulo Feofiloff
DCC-IME-USP