Mudanças entre as edições de "Algoritmo de Ordenamento em Vetor"
(Uma revisão intermediária pelo mesmo usuário não está sendo mostrada) | |||
Linha 30: | Linha 30: | ||
Considere um vetor global de estruturas já totalmente inicializado. Este vetor deve ser ordenado baseando-se no userID (um valor inteiro). Construir: | 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. | |
<syntaxhighlight lang=C> | <syntaxhighlight lang=C> | ||
Linha 60: | Linha 60: | ||
void insertSort(struct tipo_usuario tabela[], int tamanho) | 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; | ||
+ | } | ||
+ | } | ||
} | } | ||
Edição atual tal como às 15h22min de 26 de abril de 2022
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;
}