Algoritmos Elementares de Ordenação
UnB-\(\gamma\)

Table of Contents

1. Introdução

Nesta aula vamos começar a trabalhar com algoritmos elementares de ordenação, em especial: BubbleSort; Selection Sort; Insertion Sort.

Antes de começar a trabalhar com os algoritmos de ordenação vamos definir as "regras do jogo", o contexto, a terminologia e o arcabouço mínimo que se espera para começar a implementar os algoritmos de ordenação.

Nas seções abaixo você encontra todo o conjunto de vídeos explicando cada um dos algoritmos. Além disso temos na seção 3 um compilado dos tempos de execução dos algoritmos tratados. Por fim na seção 4 expõe um resumo sobre os algoritmos tratados na seção abaixo.

Não esqueça:

2. Entenda os Algoritmos passo a passo


3. Tempo de execução dos Algoritmos Elementares de Ordenação

4. Sumarização dos algoritmos

5. Exercícios

5.1. Implemente

  • cada um dos algoritmos discutidos em aula (evite consultar o material e deduza os passos);

5.2. Compare o tempo de execução dos algoritmos

  • Gere entradas aleatórias com 100000 elementos (experimente outras variações de tamanho também)
  • Para gerar uma entrada aleatória em bash
for((i=0;i<100000;i++)); do echo $RANDOM; done > aleatorio.in
  • Caso prefira implementar em C
srand(time(NULL));
for(int i=0;i<100000;i++) printf("%d\n",rand());

  • compile o código e execute da seguinte forma: 

    ./meuprograma > aleatorio.in
    • O seu programa deve ler o conjunto de números da entrada padrão, e você poderá verificar o tempo executado através dos comandos:
    time ./bubblesort < aleatorio.in > bubblesort.out
    • assim o seu programa irá ler o conteúdo do arquivo aleatorio.in como se fosse digitado pelo teclado e toda a saída será gravada no arquivo bubblesort.out (você pode trocar o nome do arquivo se assim desejar [recomendo um arquivo diferente para cada algoritmo implementado].
    • Crie variações dos arquivos, gere arquivos maiores, menores, ordenados, ordenados reversamente… E compare o tempo entre esses arquivos, há diferença?

5.3. Verifique a quantidade de operações executadas

  • Modifique a sua implementação de forma a mostrar a quantidade de operações de troca e quantas comparações foram feitas.
  • Compare o resultado com todos os algoritmos implementados para diversas entradas

5.4. Escreva uma função que coloque em ordem lexicográfica um vetor de strings

5.5. Resolva a Terceira questão desta prova

5.6. Resolva a Segunda questão desta prova

5.7. Defina o conceito de estabilidade de um algoritmo de ordenação.

  • Liste quais algoritmos trabalhados nesta aula são estáveis e quais não são

5.8. Ordenando um registro

Suponha que cada elemento de um vetor é um registro com dois campos: 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 bb fiquem em ordem lexicográfica.

5.9. Execute o benchmark disponibilizado no Github

Faça o git clone do repositório https://github.com/bcribas/benchmark-ordenacao e siga as instruções do README para executar o experimento com algumas implementações.

Author: Bruno Ribas

Created: 2022-01-27 Thu 21:35

Validate