Tópicos abordados na aula.

• Primeira aula (25, 26 de Fevereiro):

Algoritmos simples de ordenação.
Objetivo: Voltar a fazer programas em C.

• BubbleSort - Idéia: Comparar elementos adjacentes trocando-os se necessário. Após percorrer o vetor uma vez pode-se garantir que o maior elemento estará na última posição. Repetir o procedimento para os elementos restantes, até que não sejam feitas mais trocas.
• InsertionSort - Idéia: Por indução: Suponha que sabemos como ordenar n-1 números e são dados n números. Podemos ordenar n-1 números e então colocar o n-ésimo número no seu lugar, para isto percorremos os números ordenados até o lugar correto para a inserção ser encontrado.
• SelectionSort - Idéia: Encontrar o maior elemento e colocá-lo em último lugar (trocando-o com o elemento que estiver nesta posição). Continuar recursivamente para os elementos restantes.
• MergeSort - Idéia: Dividir a sequência original em duas sequências (quase) do mesmo tamanho, e depois ordená-las. Em seguida, juntar as sequências mantendo-as ordenadas. Este procedimento é aplicado recursivamente.
• ShellSort - Este é mais complicado, ai vai uma referência: Sedgewick.

• Uma implementação para gcc (linux): sorttime.c
• Testes de tempo para 1000, 10000 e 50000 elementos.