O Desenvolvimento de sistema para análise de performance de algoritmos de ordenação de dados

...

analisar:

Se vale a pena inserir a verificação de ordenação (houve troca) no algoritmo

BubbleSort;

Se vale a pena usar o algoritmo InsertSort com elemento sentinela;

Se vale a pena usar um algoritmo InsertSort tendo o arranjo implementado

através de apontadores/cursores;

Se vale a pena inserir uma verificação (Min == i) para evitar a troca, no

método SelectSort.

A segunda parte será sobre os algoritmos de ordenação por comparação ditos

eficientes, como MergeSort, HeapSort e QuickSort, que tem complexidade de

tempo de O( n log n ). São fornecidas implementações convencionais e

versões otimizadas.

Aproveite os algoritmos implementados por você e verifique:

A entrada deve ser lida de um arquivo a ser fornecido como parâmetro em linha

de comando ( int main(int argc, char**argv) ) composta de vários conjuntos de

testes, onde cada linha do arquivo contém uma expressão aritmética a ser

avaliada, no seguinte formato:

Até que tamanho de entrada, vale a pena usar algoritmos O(n2) com relação

a algoritmos O(n log n).

3. Desenvolvimento de sistema para análise de performance de algoritmos de ordenação de dados

3.1 Conceitos gerais

3.1 Definição

4.Técnicas e métodos de classificação e busca e ordenação de dados

Em ciência da computação utilizamos diversar ferramentas para ordenar e organizar as informações que manipulamos, quando desenvolvemos e projetamos um sistema qualquer que seja, devemos planejar e estruturar todos os elementos usados pelo mesmo antes de executa lo, com o surgimento desse necessidade de manipular essas informações foi feito métodos pré definidos e universais para estruturar dados, economizar tempo de execução e espaço utilizado pela memória dos computadores.

Esses métodos são chamados de métodos de classificação ou ordenação de dados que são coletados de forma aleatória após passarem pelos métodos de classificação são ordenados de forma que seja necessário, logo após a classificação desses dados, fica muito mais facil a busca entre dados ordenados e a inserção de novos dados.

Para exemplificar esses métodos usamos a linguagem C# e Java, pelo fato de estarmos familiarizados por que utilizamos em laboratório, para compreender o algoritmo iremos comentar cada passo feito e cada elementos e suas funções, a seguir abaixo esta o exemplo :

- Criamos o método “Main()”

Função que executa primeiramente no programa, contendo todo o algoritmo de ordenação tudo o que estrutura o programa.

- Usamos as variaveis do tipo “INT”, que representam numeros inteiros que podem ser modificados ao decorrer do programa, por isso são chamados de variaveis, utilizamos para fazer os calculos necessários com os dados fornecidos pelo programa.Utilizamos as seguintes variaveis :

- Int (x)

- Int (y)

- Aux

- Vetor []

- Usamos o FOR (Looping com variavel de controle)

Essa estrutura permite serem feitas diversos tipo de operações diferentes inumeras vezes dentro do programa, podem ser inseridos valores, e fazer diversos calculos.A sintaxe pode ser representada da seguinte forma :

“PARA de até Passo Faça

FIM_PARA.”

- Usamos também o IF(Estrutura de condição)

Essa estrutura é baseada em duas condições “verdadeiro” ou “falso” se os valores dentro da condição forem verdadeiro ele executa o “bloco verdade”, que podem conter todo expressão possível, se as condições dos valores forem falsas o programa executa o “bloco mentira” que tambem podem conter diversos tipo de comandos.

4.1 Bubble Sort(Tipo bolha)

Esté método é considerado uns dos mais comuns e simples em estrutura de dados,o métodos bubble sort por flutuação (tipo bolha) tem um principio simples matemáticamente dizendo, o vetor é percorrido diversas vezes assim pocisionando o maior elemento no topo a cada vez percorrido,se caso os elementos forem facilmente ordenados o algoritmo percorre o vetor N vezes, onde N corresponde a quantidade de elementos no vetor,caso contrário o algoritmo percorre muito mais vezes, por isso não é recomendado o uso desse método de ordenação para programas que precissem de velocidade e tenha uma grande carga de dados, mas se caso seja necessário em um pequeno programa a ordenação dados esse métodos é bem simples e facil de entender e executar.

Podemos exemplifacar o método bubble sort assim :

- X[1]

4.2 Select Sort(Tipo seleção)

Este método de classificação está tambem entre os métodos mais simples e faceis de entender entre os métodos de classificação,entretanto está análisado entre como um método ineficiente em quantidade de dados grandes,porem tem vantagens de desempenho em algoritmos complicados onde a memória auxiliar é limitada, esse classificação percorre todos os elementos do vetor sucessivamente seleciona o menor elementos e o coloca em sua posição correta na fila,por isso é chamada de “select sort” porque o algoritmo simplesmente seleciona o elemento desejado ,e depois o coloca em sua devida ordem seja crescente ou decrescente.

4.3 Insertion Sort(Tipo inserção)

A ideia da algoritmo insertion sort é básica também, ele por si é um algortimo de alta complexidade