1  Resumo da matéria

1.1  Ordenação

Mas em média... é N^2...
1.1.3  Ordenação por selecção
Introd.
Algoritmo
Análise
Análise da procura: n/2 comparações
elemento i: (N-i)/2 comparações + 1 troca
N trocas + N^2 comparações
1.1.4  Ordenação por inserção
Introd.
Algoritmo básico
Análise
elemento i: procura: i/2 comparações, i/2 trocas
N^2
Pequenas (?) melhorias:
Evitar trocas
(1/2 trocas)
A guarda do ciclo interior
Algoritmo melhorado
Discussão
1.1.5  Ordenação de Shell
Introd.
Algoritmo
Análise complicada: aprox. N^1,25
1.1.6  Ordanação rápida
Introd. (Hoare).  Filosofia (dividir para conquistar).
Ideia básica: escolher pivot, colocá-lo no lugar certo.
Algoritmo
Análise:
Pior: N^2
Média: N lg(N).
Mostrar exemplo de crescimento.
1.1.7  Ordenação de fusão?
1.1.8  Ordenação de "heap"?

1.2  Leitura recomendada

2  Exercícios

Módulo de ordenação

Ficheiro de interface ordena.h

#ifndef ORDENA_H
#define ORDENA_H

namespace Ordena {
    // Funções de ordenação.  Ordenam n valores contidos na matriz matriz.

    // Ordenacao de permutacao (bolha):
    void bolha(int matriz[], int n);

    // Ordenação de selecção:
    void seleccao(int matriz[], int n);

    // Ordenação de insercao:
    void insercao(int matriz[], int n);

    // Ordenação de Shell:
    void shell(int matriz[], int n);

    // Ordenação rápida:
    void rapida(int matriz[], int n);

    // Ordenação por fusão e de "heap" por fazer...

    // Funcao para verificar se uma ordenacao teve sucesso. matriz deve ser a
    // matriz já ordenada e copia uma cópia da matriz antes de ordenar.  Ambas
    // têm dimensão n.  Devolve true se matriz é versão ordenada de copia.
    bool verifica(int matriz[], int copia[], int n);

}

#endif // ORDENA_H

Ficheiro de implementação ordena.cpp

#include "ordena.h"

namespace { // para o procedimento ser local ao módulo.

    // Procedimento de troca de valores:
    inline void troca(int& a, int& b) {
        int aux = a;
        a = b;
        b = aux;
    }

}

void Ordena::bolha(int m[], int n) {
    if(n <= 1)
        return;

    // A completar...
}

void Ordena::seleccao(int m[], int n) {
    if(n <= 1)
        return;

    // A completar...
}

void Ordena::insercao(int m[], int n) {
    if(n <= 1)
        return;

    // A completar...
}

void Ordena::shell(int m[], int n) {
    if(n <= 1)
        return;

    for(int h = n / 2; h != 0; h /= 2)
        for(int i = h; i != n; ++i) {
            int aux = m[i];
            int j = i;
            for(; j >= h && m[j - h] > aux; j -= h)
                m[j] = m[j - h];
            m[j] = aux;
        }
}

namespace { // para as funções e procedimentos serem locais ao módulo.

    inline int particiona(int m[], int e, int d) {
        // A completar...
    }

    inline void rapidaRecursiva(int m[], int e, int d) {
        if(e >= d)
            return;

        int i = particiona(m, e, d);
        rapidaRecursiva(m, e, i - 1);
        rapidaRecursiva(m, i + 1, d);
    }

}

void Ordena::rapida(int m[], int n) {
    rapidaRecursiva(m, 0, n - 1);
}

bool Ordena::verifica(int matriz[], int copia[], int n)
{
    if(n == 1)
        return true;

    // Estão por ordem?
    for(int i = 0; i != n - 1; ++i)
        if(matriz[i] > matriz[i + 1])
            return false;

    // Constam todos?
    int onde = 0;
    for(int i = 0; i != n; ++i) {
        if(i == 0 || matriz[i] != matriz[i - 1])
            onde = 0;
        else
            ++onde;
        for(; onde != n && copia[onde] != matriz[i]; ++onde)
           ;
        if(onde == n)
            return false;
    }

    return true;
}

2.  Utilize o programa abaixo para verificar os tempos de execução dos vários procedimentos de ordenação.  Preencha a seguinte tabela:
 

Número de valores	Número de testes	Bolha	Selecção	Inserção	Shell	Rápida
2	1000000
10	100000
100	10000
1000	100
10000	1

Conclua.

Programa de cálculo dos tempos tempos.cpp

#include <iostream>
#include <string>
#include <ctime>                // para clock() e clock_t
#include <cstdlib>              // para rand() e srand()

#include "ordena.h"

using namespace std;

// Devolve aleatório entre de e a (exclusivé):
inline int aleatorio(int de, int a) {
    return de + int((rand() / (RAND_MAX + 1.0)) * (a - de));
}

// Devolve o tempo médio (em ms [milisegundos]) que a função ordena demora a
// ordenar numero_de_valores valores numa matriz.  O cálculo é feito com base
// em numero_de_testes testes.
// Nota: o cálculo do tempo de preenchimento das matrizes pode introduzir
// alguns erros nas estimativas.
double testa(void ordena(int [], int),
             int numero_de_testes, int numero_de_valores)
{
    // Valores na matriz de teste entre 0 e maximo (exclusivé):
    const int maximo = 1000;

    // Semente para os números aleatórios:
    const int semente = 345345;

    // Criar matriz para os valores:
    int* matriz = new int[numero_de_valores];

    // Inicializa-se o gerador de números aleatórios (todos os testes
    // feitos com os mesmos valores, para que a comparação seja justa).

    // Ciclo para cálculo do tempo gasto no preenchimento da matriz:
    srand(semente);
    clock_t descontos = clock();

    for(int teste = 0; teste != numero_de_testes; ++teste)
        // Preenchimento da matriz:
        for(int i = 0; i != numero_de_valores; ++i)
            matriz[i] = aleatorio(0, maximo);

    descontos = clock() - descontos;

    // Ciclo para cálculo do tempo gasto nas ordenações:
    srand(semente);
    clock_t total = clock();

    for(int teste = 0; teste != numero_de_testes; ++teste) {
        // Preenchimento da matriz:
        for(int i = 0; i != numero_de_valores; ++i)
            matriz[i] = aleatorio(0, maximo);

        // Ordenação:
        ordena(matriz, numero_de_valores);
    }

    // Cálculo do tempo (descontanto tempo de preenchimento das matrizes):
    total = clock() - total - descontos;

    delete[] matriz;

    // Cálculo e devolvução do tempo em ms:
    return double(total) / CLOCKS_PER_SEC / numero_de_testes * 1000;
}

int main(int argc, char *argv[])
{
    // Três argumentos: nome do programa, número de valores a ordenar
    // e número de testes.
    if(argc < 3) {
        cerr << "Invocar com número de valores e de testes." << endl;
        return 0;
    }

    int numero_de_valores = atol(argv[1]);
    int numero_de_testes = atol(argv[2]);

    cout << "Fazendo " << numero_de_testes << " testes com "
         << numero_de_valores << " elementos" << endl << endl;

    cout << "Ordenação por permutação ou bolha (1ª versão) "
         << testa(Ordena::bolha, numero_de_testes, numero_de_valores)
         << " ms" << endl;
    cout << "Ordenação por selecção (1ª versão) "
         << testa(Ordena::seleccao, numero_de_testes, numero_de_valores)
         << " ms" << endl;
    cout << "Ordenação por inserção (1ª versão) "
         << testa(Ordena::insercao, numero_de_testes, numero_de_valores)
         << " ms" << endl;
    cout << "Ordenação de Shell (1ª versão) "
         << testa(Ordena::shell, numero_de_testes, numero_de_valores)
         << " ms" << endl;
    cout << "Ordenação rápida (1ª versão) "
         << testa(Ordena::rapida, numero_de_testes, numero_de_valores)
         << " ms" << endl;
}

3.a)  A guarda do ciclo interior da ordenação por inserção é a conjunção de duas condições.  Consegue eliminar uma?  Como?  Verifique a sua optimização repetindo os testes acima.

Sugestão:  Se o valor do primeiro elemento da matriz fosse o mais pequeno de todos (uma sentinela)...

3.b)  Uma técnica semelhante pode ser usada no algoritmo de ordenação rápida, pelo menos para um dos dois ciclos interiores, sendo que neste caso a sentinela já lá está, é só necessário vê-la...

4.  Mais optimizações da ordenação rápida.

4.a)  Dos valores na tabela dos tempos que construiu facilmente se conclui que a ordenação rápida é mais lenta que a ordenação por inserção até cerca de 10 valores.  Optimize a ordenação rápida deixando por ordenar todos os troços com menos de 10 valores.  No final use a ordenação por inserção para fazer os ajustes finais.  Verifique os tempos e conclua.

4.b)  As chamadas a funções são onerosas computacionalmente.  Optimize a ordenação rápida de modo a não ser recursiva mas sim iterativa.  Use uma pilha onde coloca os troços a processar (coloque na pilha sempre os troços maiores, deixando os mais pequenos para processamento imediato!).  Verifique os tempos.  Justificou-se o esforço?

5.  Passe os procedimentos e funções a modelos para que se tornem genéricos.

6.  Implemente procedimentos de ordenação usando os algoritmos de fusão (merge) e de heap.

3  Referências

# Existem 10 exemplares na biblioteca do ISCTE.