Algoritmo de Ordenamento em Vetor
Algoritmo Bubble Sort
Este algoritmo compara do início ao fim do vetor, pares adjacentes e ordena (troca valores) se for o caso.
Ver aspectos conceituais a animação aqui
Exercício 1:
Implementar em C++ a versão não otimizada do algoritmo Bubble sort de acordo com o sugerido na wikipedia.
Exercício 2:
Na versão otimizada evita-se continuar a análise de uma parte do vetor sabendo-se que já está ordenado para frente.
Implementar em C++ a versão otimizada do algoritmo Bubble sort de acordo com o sugerido na wikipedia.
Algoritmo Insert Sort
Este algoritmo é similar a organização ordenada que fazemos em um jogo de cartas. A ideia é sucessivamente ordenar o vetor da "esquerda" para a direita.
Ver aspectos conceituais a animação aqui
Exercício 3:
Implementar em C++ a versão do algoritmo Insert sort de acordo com o sugerido na wikipedia.
Exercício de Revisão 1
Considere um vetor global de estruturas já totalmente inicializado. Este vetor deve ser ordenado baseando-se no userID (um valor inteiro). Construir:
- uma função para ordenar o vetor usando o algoritmo insert sort;
- uma função para ordenar o vetor usando o algoritmo bubble sort;
- uma função para fazer busca binária no vetor basendo-se em um userID fornecido como parâmetro. A função deve retornar -1 se não encontrado ou o índice da estrutura encontrada.
#include <iostream>
#include <string>
using namespace std;
struct tipo_usuario{
string nome;
int userid;
}tabelaUsuarios[5] = {
{"Eraldo", 123},
{"Silvana", 254},
{"Lara", 57},
{"Maria", 96},
{"Vica",755}
};
void printTabela()
{
for (int i=0;i<5;i++){
cout << tabelaUsuarios[i].nome << " ID -> " << tabelaUsuarios[i].userid << endl;
}
}
void insertSort(struct tipo_usuario tabela[], int tamanho)
{
// versão aluna Maria
int i, j;
struct tipo_usuario aux, eleito;
for (i = 1; i < tamanho; i++) {
eleito = tabela[i];
j = i - 1;
while ((j >= 0) && (tabela[j].userid > eleito.userid)) {
aux = tabela[j+1];
tabela[j+1] = tabela[j];
tabela[j] = aux;
j--;
}
tabela[j + 1] = eleito;
}
}
}
void bubbleSort(struct tipo_usuario tabela[], int tamanho)
{
}
int binarySearchTabela(int userID){
//retorna o índice correspondente ao userID ou -1 se não encontrado
}
int main(){
insertSort();
printTabela();
return 0;
}