Algoritimo

UNIVERSIDADE FEDERAL DE MINAS GERAIS

Gabriel Laguárdia de Lima

Algorítimos e Estruturas de Dados II
Trabalho Prático I
Algorítimos de Ordenação

BELO HORIZONTE – MINAS GERAIS
2011
Introdução:
Os algorítimos de ordenação,cujo objetivo é pegar uma determinada sequencia de termos e coloca-los em uma ordem específica, são muito utilizados na computação, possuindo deversas finalidades.
A possibilidade se acessar dados de modo mais eficiente e a facilidade de manipulação destes que tais algoritimos proporcionam são algumas das razões que os levam a ser tão utilizados. Para isso, foram criados diversos algorítimos de ordenação, buscando sempre, otimizar o tempo de execução, com uma complexidade cada vez menor, afim assim, de se obter o melhor desempenho possível.
Na busca por uma eficiencia máxima, os algorítimos serão estudados e testados, medindo-se os tempos de execução, e calculando as suas complexidades, buscando definir, para cada situação (tipo, tamnho e a forma em que os dados do vetor estão distribuidos), qual é o melhor a ser utilizado.

Desenvolvimento:

Apresentação dos Algorítimos a serem estudados:
Para este estudo, considerarei os algoritmos de ordenação: BubbleSort, SelectionSort, InsertionSort, QuickSort, MergeSort eLaguaSort,que ordenam um vetor em ordem crescente.
Implementação dos algorítimos em C++ e suas respectivas complexidades na notação O:
Obs: A explicação detalhada dos algorítimos virá após a apresentantação destes.

Bubble Sort:

voidbubblesort (int v[], int n)
{
int trocas; for(int i=0;i<n;i++) { trocas=0; for(int j=0;j<((n-i)-1);j++) if(v[j]>v[j+1]) { troca(v[j],v[j+1]); trocas++; } if(trocas==0) break; }
}

Complexidade:

fn=3+5*i=1n[6+9*n-i]=452n2+152n+3

Logo: O (n2)
Selection Sort:

void selection(int v[],int n)
{
for(int i=0;i<(n-1);i++)
for(int