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;
}