Ordenação de um vetor: seleção

Esta página foi extraída (com algumas modificações) do capítulo 7, seção 7.1, do livro de Eric Roberts.   Convém lembrar que um vetor v[0..n-1] está em ordem crescente se

v[0]   <   v[1]   <   . . .   <   v[n-1] .

(Algumas pessoas preferem dizer "ordem não-decrescente".)

O algoritmo de seleção

// A função SelectionSort rearranja um vetor // array[0..n-1] em ordem crescente. void SelectionSort( int array[], int n) { int lh, rh, i, temp; for (lh = 0; /*A*/ lh < n; lh++) { rh = lh; for (i = lh + 1; i < n; i++) if (array[i] < array[rh]) rh = i; temp = array[lh]; array[lh] = array[rh]; array[rh] = temp; } }

Para entender o algoritmo, basta observar a seguinte propriedade invariante, válida no início de cada iteração, ou seja, a cada passagem pelo ponto A:

• array[0] < array[1] <  . . .   < array[lh-1]
• array[lh-1] < array[lh..n-1]

Essas propriedades invariantes podem ser reescritas de maneira mais informal:

• o vetor array[0..lh-1] contém os elementos pequenos do vetor original e está em ordem crescente;
• o vetor array[lh..n-1] contém os elementos grandes do vetor original.

Exercícios

1. Algumas pessoas gostam de trocar as últimas três linhas de código pelas que estão abaixo. Discuta (comente, critique) essa variante do código.

         if (lh < rh) {
            temp = array[lh];
            array[lh] = array[rh];
            array[rh] = temp;
         }
   

2. [Importante!]  Escreva uma função que receba vetores a[0..n-1] e b[0..n-1] e devolva 1  se  b[0..n-1] está em ordem crescente e é uma permutação de a[0..n-1].  Se uma dessas propriedades não estiver satisfeita, sua função deve devolver 0. Por exemplo, se a[0..n-1] e b[0..n-1] forem os vetores

           66 33 22 99 33 22          22 33 33 66 66 99
   

   então sua função deve devolver 0.

Versão recursiva do algoritmo

// A função abaixo rearranja em ordem crescente // um vetor array[low..high]. void SelectionSortR( int array[], int low, int high) { int rh, i, temp; if (low < high) { rh = low; for (i = low + 1; i <= high; i++) { if (array[i] < array[rh]) rh = i; } temp = array[low]; array[low] = array[rh]; array[rh] = temp; SelectionSortR( array, low+1, high); } }

Consumo de tempo

O consumo de tempo do algoritmo é proporcional ao número de comparações entre elementos do vetor. No pior caso esse número é

(n-1) + (n-2) + ... + 2 + 1,

ou seja, igual a (n² - n)/2.  Para simplificar, dizemos que o consumo de tempo "é da ordem de n²".

Exercícios

3. [Roberts exr.2, p.318]  Escreva uma função que implemente o algoritmo de ordenação-por-inserção. No começo de cada iteração, array[0..lh-1] está em ordem crescente e o algoritmo insere o array[lh] na posição correta em array[0..lh-1]. Escreva duas versões: uma iterativa e uma recursiva.

4. [Bom!]  Escreva uma função que receba um arquivo texto, coloque as linhas do texto em ordem lexicográfica e grave o arquivo ordenado.

Animação de algoritmos de ordenação (universidade de Carlton, Canadá).