Trabalho de ordenção

Trabalho de Ordenação de Dados
Data Entrega: 20/10/2010
Grupos de 5 alunos
Forma de entrega:
• Impresso contendo algoritmos implementados, definição e explicação do funcionamento dos métodos pesquisados, vetores aleatórios gerados em cada uma das dimensões, tabela com valores de tempo preenchidos, gráficos devidamente traçados e as respostas para as questões abaixo:
o Trace um gráfico de linha para cada método e avalie qual foi mais eficiente.
o O algoritmo mais eficiente para o vetor de 1000 elementos é o mais eficiente para o vetor com 200000 elementos? Caso sua resposta seja não, explique por que isso ocorre.
• Apresentação elaborada em PowerPoint com explicação oral da tabela e do gráfico.
Este trabalho esta constituído de:
- Pesquisa sobre algoritmos de Ordenação
Faça uma pesquisa sobre os seguintes métodos de ordenação e explique o funcionamento de cada um dos métodos pesquisados.
a) Bubble Sort
b) Insertion Sort
c) Selection Sort

- Implementação e Análise Comparativa de Desempenho de Algoritmos
Codifique os algoritmos Bubble Sort, Insertion Sort e Selection Sort para realizar a ordenação de 10 vetores. Execute cada uma das implementações de forma que possibilite o preenchimento da tabela abaixo. Considere os seguintes pontos:
• Utilize o código abaixo para gerar vetores de números aleatórios em todas as dimensões descritas na tabela.

Código:

#include <iostream>
//biblioteca para uso da função srand e rand para gerar números //aleatórios
#include <stdlib.h>
//biblioteca para uso da função time
#include <time.h>
using namespace std;
//definição do tamanho do vetor
int const DIMENSAO = 1000;

void main()
{   
   int i, vetor[DIMENSAO];
   //cria os números aleatórios
   srand((unsigned)time( NULL ));
   for (i = 0; i < DIMENSAO; i++)
      //atribui um valor aleatório para cada posição do vetor
      vetor[i] = rand();   
for (i = 0; i < DIMENSAO; i++)
   //apenas imprime o vetor
      cout << vetor[i] << "\t";
}

• Aplique os três métodos de ordenação sobre o mesmo vetor gerado em cada dimensão. Por exemplo, após gerar o vetor de 1000 posições aplique sobre ele os três métodos de ordenação: Bubble Sort, Insertion Sort e Selection Sort. Anote o tempo decorrido da execução de cada método na tabela abaixo.

	Tempo em segundos
Dimensão	Bubble Sort	Insertion Sort	Selection Sort
1000	00:00	00:00	00:00
2000	00:00	00:00	00:00
4000	00:00	00:01	00:00
6000	00:00	00:01	00:00
8000	00:01	00:02	00:00
10000	00:02	00:03	00:00
20000	00:05	00:04	00:01
40000	00:21	00:14	00:02
60000	00:45	00:033	00:05
80000	01:23	00:57	00:10
2000000	08:53	?	?

Ribeirão Preto, 22 de setembro de 2010

Hoje vou falar um pouco sobre os algoritmos de ordenação de dados.
Sabemos que as principais linguagens de programação atuais (para não afirmar todas) possuem alguma função para essa tarefa, ou seja, com apenas uma chamada de função (sort(), qsort(), qsort(), etc...) conseguimos ordenar determinada estrutura de dados. Mas muitas vezes precisamos fazer alguma coisa enquanto estamos ordenando esses dados, seja para adicionar mais coisas aos dados, seja para guardar determinadas informações desse processo. Para isso temos que implementar nós mesmos essa função.
Abaixo vou explicar um pouco sobre os principais algoritmos existentes.
Algoritmo de ordenação por inserção
Esse algoritmo, como muitos outros, é baseado em ações que nós (como pessoas) fazemos no dia-a-dia para resolver o problema. Lembra quando você está jogando baralho, e suas cartas já estão na mesa e você precisa colocá-las na mão de uma forma ordenada? Essa ordenação deve ser feita de uma maneira que você esteja acostumado a escolher uma carta facilmente para jogar mais rápido e melhor... É exatamente isso que o algoritmo de ordenação por inserção faz por baixo dos panos. A idéia principal dele é: adiciona-se um item qualquer à estrutura de dados, depois, para cada item que ainda não esteja na estrutura, antes de adicioná-la, comparar com cada item que já está nela (consequentemente já ordenada) até encontrar a posição a ser encaixada. É exatamente o que fazemos com o baralho. Essa opção é boa quando temos uma entrada pequena de dados, para entradas grandes pode se consumir muito tempo de processamento.

Código:

void entrada(int t[10]);
void Inserction(int vetor[10]);
void exibir(int v[10]);

void main ()
{
   int vet[10];
   entrada(vet);
   Inserction(vet);
   exibir(vet);
}

void entrada(int t[10])
{
   int i;
   for(i = 0; i < 10; i++)
   {
      cin >> t[i];
   }
}


void Inserction(int vetor[10])
{

  int j,i,key;

  for(j=1;j<10;j++){

      key = vetor[j];
      i = j -1;

      while(i>(-1) && vetor[i]>key){

        vetor[i+1] = vetor[i];
        i = i -1;
        }

      vetor[i+1] = key;       
  }

}


void exibir(int v[10])
{
   int i;
   for(i = 0; i < 10; i++)
   {
      cout << v[i] <<"\n";
   }
}

Algoritmo Bubblesort
Talvez um dos mais populares dos algoritmos para ordenação seja o bubblesort, isso pela fácil memorização de como funciona e como é fácil a sua implementação. Ele consiste basicamente em intercalar elementos, por isso se enquadra na categoria de ordenação por intercalação, a implementação dele é simples. Com uma estrutura de dados desordenada inicia-se o algoritmo pelo primeiro elemento, depois faz-se a comparação dele com todos os que estão depois dele na estrutura desordenada, portanto com 4 linhas de código dá para se implementar.

Código:

#include "Bubblesort.h"
void bubblesort(vetor &a, tamanho n)
{
 for(indice j= n-1; j>0; j--){
  for(i=0;i<j;i++){
  if(a[i+1] < a[i]){
    swap(a[i+1], a[i]);
  }
  }
 }
}
#include<iostream>
using namespace std;


void entrada(int ent[10]);
void bubblesort(int a[10], int &n);
void exibir(int ex[10]);


void main()
{
   int t[10], r;
   entrada(t);
   bubblesort(t, r);
   exibir(t);
}

void entrada(int ent[10])
{   
   int i;
   for(i = 0; i < 10; i++)
   {
      cin >> ent[i];
   }
}


void bubblesort(int a[10], int &n)
{
   int j, i;
   n = 10;
   for(j = n-1; j>0; j--)
   {
   for(i=0;i<j;i++)
   {
      if(a[i+1] < a[i])
      {
      swap(a[i+1], a[i]);
      }
   }
   }
}


void exibir(int ex[10])
{
   int i;
   for(i = 0; i < 10; i++)
   {
      cout << ex[i];
   }
}

O selection sort (do inglês, ordenação por seleção) é um algoritmo de ordenação baseado em se passar sempre o menor valor do vetor para a primeira posição (ou o maior dependendo da ordem requerida), depois o de segundo menor valor para a segunda posição, e assim é feito sucessivamente com os (n-1) elementos restantes, até os últimos dois elementos.

Código:

template<class T>
void selection_sort( std::vector<T> &lista )
{
  for( std::vector<T>::iterator it = lista.begin(); it != lista.end()-1; ++it )
  {
    std::iter_swap( it, std::min_element( it, lista.end() ) );
  }
}

Referencia: C++ como programar 3ª edição.

CAPÍTULO 4 - ARRAYS
4.6 Ordenando arrays / pag 283.

Ordenar dados (i.e., colocar os dados segundo uma determinada ordem, como ascendente ou descendente) é uma das
aplicações computacionais mais importantes. Um banco classifica todos os cheques pelos números das contas para que
possa preparar os extratos de cada conta no final do mês. As companhias telefônicas classificam suas listas pelo á 1
timo nome e, dentro disso, pelo primeiro nome, para que fique fácil encontrar números de telefone. Pratica- mente
todas as organizações devem classificar algum dado e, em muitos casos, quantidades muito grandes de dados.
Classificar dados é um problema fascinante, que tem atraído alguns dos esforços mais intensos de pesquisa no campo
da Ciência da Computação. Neste capítulo, analisamos o que talvez seja o esquema mais simples de classificação. Nos
exercícios e no Capítulo 15, investigamos esquemas mais complexos, que levam a um desempenho muito superior.
1 Dica de desempenho 4.5
f Freqüentemente, os algoritmos mais simples apresentam um desempenho muito ruim. Sua virtude reside no fato de
que são fáceis de escrever testar e depurar Algumas vezes, porém, são necessários algoritmos
mais complexos para se atingir o melhor desempenho possível.
O programa na Fig. 4.16 classifica os valores dos elementos de um array a de dez elementos em ordem ascendente. A
técnica utilizada é chamada de bubble sort, ou sinking sort, porque os valores menores “sobem” gradualmente para o
topo do array, da mesma forma que bolhas de ar sobem na água, enquanto os valores maiores afundam (submergem)
para a parte de baixo do array. A técnica faz diversas passagens pelo array. Em cada passagem, são comparados pares
sucessivos de elementos. Se um par estiver na ordem crescente (ou se os valores forem iguais), os valores são deixados
como estão. Se um par estiver na ordem decrescente, seus valores são permutados no array.

Código:

// Este programa classifica os valores de um array em ordem ascendente
#include <iostream>
#include <iomanip>
using namespace std;
const int arraySize = 10;

void main()
{
    int a[ arraySize ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 };
    int i, hold, pass;
   
    cout<< "Itens de dados na ordem original\n";
    for ( i = 0; i < arraySize; i++)
    cout<< setw( 4 )<< a[ i ];
   
    for ( int pass = 0; pass < arraySize - 1; pass++ ) // passagens
        for ( i = 0; i < arraySize - 1; i++ ) // uma passagem
            if ( a[ i ] > a[ i + 1 ] ) // uma comparação
            {
                hold = a[ i ]; // uma permuta
                a[ i ] = a[ i + 1 ];
                a[ i + 1 ]= hold;
            }
    cout<< "\nltens de dados em ordem ascendente\n";
   
    for ( i = 0; i < arraySize; i++)
        cout<< setw( 4 )<< a[ i ];
    cout<< endl; 
    system("pause");
}

Itens de dados na ordem original
2 6 4 8 10 12 89 68 45 37
Itens de dados em ordem ascendente
2 4 6 8 10 12 37 45 68 89
Fig. 4.16 Ordenando um array com o bubble sort (parte 1 de 2).
Fig. 4.16 Ordenando um array com o bubble sort(parte 2 de 2)
Inicialmente, o programa compara a [ O ] com a [ 1 ] , depois a [ 1 ] com a [ 2 ] , depois a [ 2 ] com a [ 3 ] e assim por
diante, até completar a passagem, comparando a [ 8 ] com a [ 9 ] . Observe que, embora existam 10 elementos, são
realizadas apenas nove comparações. Tendo em vista o modo como são feitas as comparações, um valor grande pode se
mover para baixo várias posições, mas um valor pequeno só pode se mover para cima uma única posição. Na primeira
passagem, garante-se que o maior valor “submergirá” para o elemento mais baixo (para o “fundo”) do array, a [ 9 ] . Na
segunda passagem, garante-se que o segundo maior valor submergirá para a [ 8 ] . Na nona passagem, o nono maior
valor submerge para a [ 1 ]. Isso deixa o menor valor em a [ O ], sendo necessárias apenas nove passadas no array para
classificá-lo, embora ele tenha dez elementos.
A classificação é realizada pelo laço for aninhado. Se for necessária uma permuta, ela é realizada pelas três
atribuições seguintes
hold = a[ i ];
a[ i ] = a[ i + 1 ];
a[ i + 1 ] = hold;
hold armazena temporariamente um dos valores que está sendo permutado. A permuta não pode
ser realizada somente com as duas atribuições seguintes
a[ i ] = a[ i + 1 ];
a[ i + 1 ] = a[ i ];
Se, por exemplo, a [ i ] é 7 e a [ i + 1 ] é 5, depois da primeira atribuição ambos os valores serão iguais a 5 e o valor 7
será perdido. Daí necessitarmos da variável extra hold.
A principal virtude do bubble sort reside no fato de que ele é fácil de programar. Entretanto, o bubble sort é lento.
Isso se toma perceptível durante a classificação de arrays grandes. Nos exercícios, desenvolveremos versões mais
eficientes do bubble sort e investigaremos algoritmos de classificação muito mais eficientes do que o bubble sort.
Cursos mais avançados investigam classificação e pesquisa em arrays com maior profundidade.

Capítulo 5 Ponteiro e Strings
5.6 Bubble sort usando chamada por referência / pag 334.

Modifiquemos o programa bubble sort para usar duas funções - bubbleSort e swap.
A função bubbleSort executa a ordenação do array. Ela chama a função swap para permutar os elementos de array array[j] e array[j+1]. Lembre-se de que C++ força obrigatoriamente a ocultação de informação entre funções, de modo que swap não tem acesso a elementos individuais do array em bubble sort. Como bubbleSort quer que swap tenha acesso a elementos do array devem ser trocados de posição, bubbleSort passa cada um destes elementos através de uma chamada por referência para swap - o endereço de cada elemento de array é passado explicitamente. Embora arrays inteiros sejam automaticamente passados por chamadas por referência, elementos individuais de array são escalares e sçao normalmente passados por chamadas por valor. Portanto, bubbleSort usa o operador de endereço ( & ) para cada elemento de array na chamada swap, como segue, para fazer a chamada por referência:

Código:

// fig. 5.15: fig05_15.cpp
//Este programa põe valores em um array, classifica os valores em
// ordem crescente e imprime o array resultante.
#include <iostream>

using std::cout;
using std::endl;

#include <iomanip>

using std::setw;

void bubbleSort(int *, const int );

void main()
{
    const int arraySize = 10;
    int a[ arraySize ] = {2, 6, 4, 8, 10, 12, 89, 68, 45, 37};
    int i;

    cout<< "Itens de dados na ordem original\n";

    for(i = 0; i < arraySize; i++)
        cout<< setw ( 4 ) << a[ i ];
   
    bubbleSort(a, arraySize); //Classifica o array
    cout<< "\nItens de dados em ordem ascendente\n";

    for(i = 0; i < arraySize; i++)
        cout<< setw ( 4 ) << a[ i ];

    cout<< endl;
}

void bubbleSort(int *array, const int size)
{
    void swap(int * const; int * const);

    for(int pass = 0; pass < size -1; pass++)
        for(int j = 0; j < size - 1; j++)
            if(array[j] > array[ j + 1 ])
                swap( &array[ j ], &array[ j + 1 ]);
}

void swap(int * const element1Ptr, int * const element2Ptr)
{
    int hold= *element1Ptr;
    *element1Ptr = *element2Ptr;
    *element2Ptr = hold;
}

A função swap recebe &array[ j ] na variável ponteiro element1Ptr. Por causa do princípio de ocultamento de informação, swap não tem permissão de conhece o nome array[ j ], mas swap pode usar element1Prt como sinônimo para array[ j ]. Deste modo, quando swap referencia elemente1Ptr, ela está na realidade referenciando array[ j ] em bubbleSort. Semelhante, quando swap referencia elemente2Ptr, ela está na realidade array[ j + 1 ] em bubbleSort.

Muito embora não seja permitido a swap dizer

hold = array[ j ];
array [ j ] = array [ j + 1 ];
array[ j + 1 ] = hold;

exatamente o memso efeito é obtido por

hold= *element1Ptr;
*element1Ptr = *element2Ptr;
*element2Ptr = hold;

Várias características da função bubbleSort devem ser comentadas. O cabeçalho de função declara array como int * array, em vez de int vetor array[ ], para indicar que bubbleSort recebe como argumento um array unidimensional (repetindo, estas notações são intercambiáveis). O argumento size receba uma cópia de um valor em main e modificar a cópia não possa mudar o valor em main, bubbleSort não precisa alterar size para realizar sua tarefa. O tamanho do array permanece fixo durante a execução de bubbleSort. Então, size é declarado const para assegurar que não seja modificado. Se o tamanho do array fosse modificado durante o processo de classificação não seria executado corretamente.
O protótipo para a função swap é incluído no corpo da função bubbleSort porque ela é a única função que chama swap. Colocar o protótipo em bubbleSort restringe de modo adequado as chamadas a swap àquelas feitas por bubbleSort. Outras funções que tentam chamar swap não têm acesso a um protótipo de função apropriado. Isto normalmente resulta em um erro de sintaxe porque C++ exige portótipos de função.

Capítulo 5 Ponteiro e Strings
5.27 Saídas do programa bubble sort / pag 352

O parâmetro seguinte aparece no cabeçalho de função para bubble:

bool( *compare )( int, int )

Isto diz para bubble esperar um argumento que é um ponteiro para uma função que recebe dois argumentos de tipo inteiro, retornando um resultado de tipo booleano. Os parênteses são necessário em volta de *compare porque* tem uma precedência mais baixa que os parênteses em volta dos argumentos da função. Se não incluíssemos os parênteses, a declaração teria sido

bool *compare( int, int )

que declara uma função que recebe dosi interios como argumentos e retorna um ponteiro para um booleano. O argumento corresponde, no protótipo de função de bubble, é
bool (*)( int, int )
Note que foram incluídos só tipos, mas para fins de documentação o programador pode incluir nomes que o compilador ignorará.
A função passada para bubble é chamada em um comando if como segue

if ( (*compare) ( work[ count ], work[count + 1] ) )

Da mesma maneira que um ponteiro para uma variável é derreferenciado para acessar o valor da variável, um ponteiro para uma função é derreferenciado para executar a função.
A chamada para a função podia ter sido feita sem derreferenciar o ponteiro, como em

if ( compare( work[ count ], work[ count + 1 ]))

que utiliza o ponteiro diretamente como o nome da função. Preferimos o primeiro método de chamar uma função através de um ponteiro, porque explicitamente mostra que compare é um ponteiro para uma funçao que é derreferenciado para chamar a mesma. O segundo método de chamar uma função através de um ponteiro faz compare se parecer com uma função real. Isso pode ser confuso para um usuário do programa que gostaria de ver a definição da função compare e acha que ela nunca é definida no arquivo.
Um uso para ponteiros de função é encontrado em sistemas orientados paor menus. Um usuário é solicitado aselecionar uma opção de um menu (por exemplo, de até 5). Cada opção é tratada por uma função diferente. Os ponteiros para cada função são armazenados em um array de ponteiros para funções. A escolha do usuário é usada como subscrito do array e o ponteiro que está na posição determinada por esse subscrito no array é usado para chamar a função.
O programa da abaixo fornece um exemplo genérico do mecanismo de declarar e usar uma array de ponteiros para funções. Três funções são definidas - function1, function2 e function3 - cada uma aceitando um argumento do tipo inteiro e não retornando nada. Os ponteiros para estas três funções são armazenados no array f, que édeclarado como segue:
Adeclaração é lida começando no conjunto mais à esquerda de parênteses, como "f é um array de 3 ponteiros para funções que aceitam um int como argumento e retornam void". O array é inicializado com os nomes da três funções (que, repetimos, são ponteiros). Quando o usuário digita um valor entre 0 e 2, o valor é usado como o subscrito do array de ponteiros para funções. A chamada da função é feita como segue:
Na chamada, f[ choice ] seleciona o pontiro nacposição choice do array. O ponteiro é derreferenciado para chamar a função choice é passado como argumento para a função. Cada função imprime o valor do seu argumento e seu nome de função para indicar que a função foi chamada corretamente.

Código:

//Fig. 5.28: fig05_28.cpp]
//Demonstrando um array de ponteiros para funções
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

void function1 ( int );
void function2 ( int );
void function3 ( int );

void main()
{
   void (*f[ 3 ])( int ) = { function1, function2, function3}
   int choice;

   cout<< "Digite um número entre 0 e 2, 3 para terminar: ";
   cin>> choice;
   while( choice >=0 && choice < 3)
   {
      (*f[ choice ])( choice );
      cout<< "Digite um número entre 0 e 2, 3 para terminar: ";
      cin>> choice;
   }

   cout<< "Execução do programa terminada." << endl;   
}

void function1( int a )
{
   cout<< "Você digitou " << a << ", de modo que function1 foi chamada.\n\n";
}

void function2( int b )
{
   cout<< "Você digitou " << b << ", de modo que function2 foi chamada.\n\n";
}

void function3( int c )
{
   cout<< "Você digitou " << c << ", de modo que function3 foi chamada.\n\n";
}

Referência: C++ como programar 5ª edção, pag 787.

Efeciência da classificação por seleção.

A classificação por seleção é um algoritmo de classificação fácil de implementar, mas ineficiente. a primeira iteração do algoritmo seleciona o menor elemento no vetor e o permuta pelo primeiro elemento. A segunda iteração seleciona o segundo menor elemento (que é o menor dos elementos restantes) e o permuta pelo segundo elemento. O algoritmo continua até que a última iteração selecione o segundo maior elemento e permute-o pelo penúltimo elemento, deixando o maior elemento no último índice. Depois da iésima iteração, os menores i elementos do vetor serão classificadas na ordem crescente dos primeiros i elementos do vetor.
O algoritmo de classificação por seleção itera n-1 vezes, colocando a cada passagem o menor elemento restante em sua posição classificada. Localizar o menor elemento restante requer n-1 comparações durante a primeira iteração, n-2 durante a segunda iteração e, então n-3,... , 3, 2, 1. Isso resulta em um total de n(n-1)/2 ou (n^2-n)/2 comparações. Na notação O (ordem), os menores termos são eliminados e as constantes são ignoradas, deixando um O final de O (n2) Lese (ordem de n ao quadrado ou ordem do quadrado de n).

Referência: Procedimentos e Funções

Ordenação por Seleção (Selection Sort) :

Código:

void SelectionSort(int V[100], int N, int Ordenado[100])
{
     int M = 0, i;
     while(N > 0)
     {
            i = MenorElemento(V, N);
            Ordenado[M] = V[i];
            V[i] = V[N - 1];
            N--;
            M++;
     }
}

N = 11; M = 0;

3	20	78	15	56	23	2	1	19	28	6
1	0	0	0	0	0	0	0	0	0	0

N = 10; M = 1;

3	20	78	15	56	23	2	6	19	28
1	2	0	0	0	0	0	0	0	0	0

N = 9; M = 2;

3	20	78	15	56	23	28	6	19
1	2	3	0	0	0	0	0	0	0	0

Problema :

Como ordenar um vetor sem alterar os dados do vetor original V ?

Algoritmo :

• Percorra o vetor (V)

• Para cada elemento (aux) de V, insira uma cópia de aux na primeira posição livre do vetor auxiliar (Ordenado).

• Se o valor de aux for menor que do elemento anterior, então troque aux com o anterior.

• Senão saia do laço.

• Repita as trocas até que aux chegue na primeira posição.

Referência: C++ como programar 5ª edção, pag 788.

Eficiência da classificação por inserção.

A classificação por inserção é outro algoritmo de classificação simples, mas ineficiente. A primeira iteração desse algoritmo seleciona o segundo elemento no vetor e se for menor que o primeiro elemento, permuta o pelo primeiro elemento. A segunda iteração examina o terceiro elemento e o insere na posição correta com relação aos dois primeiros elementos de modo que todos os três elementos estejam na rode. Na i-ésima iteração desse algoritmo, os primeiros i elementos no vetor original estarão classificados.
A classificação por inserção itera n-1 vezes, inserindo um elemento na posição apropriada nos elementos classificados até agora.
Para cada interação determinar onde inserir o elemento requer comparar o elemento a cada um dos elementos precedentes no vetor. No pior caso isso exigira n-1 comparações. Cada instrução de repetição individual executa o tempo O (n). Para determinar a notação O, as instruções aninhadas querem dizer que você deve multiplicar o numero de comparações. Para cada iteração de um loop externo, haverá um certo numero de iterações do loop interno. Nesse algoritmo, para cada O (n), iteração do loop externo, há O (n) iterações do loop interno, resultando em um O de O (n*n) ou O (n^2).

Referência: Procedimentos e Funções

Ordenação por Inserção (Insertion Sort) :

Código:

void InsertionSort( int V[100], int N, int Ordenado[100])
{
     int M = 0, i, j, k;
     for (i = 0; i < N; i++)
     {
          Ordenado[M] = V[i];  k = M;
          for (j = M - 1; j >= 0; j--)
               if (Ordenado[k] < Ordenado[j] )
                 Troca(&Ordenado[k--], &Ordenado[j]);
         else
                 break;
          M++;
     }
}

M = 0; i = 0;

2	15	1	3	6	23	57
2	0	0	0	0	0	0	0	0	0	0

M = 1; i = 1;

2	15	1	3	6	23	57
2	15	0	0	0	0	0	0	0	0	0
2	15	0	0	0	0	0	0	0	0	0

M = 2; i = 2;

2	15	1	3	6	23	57
2	15	1	0	0	0	0	0	0	0	0
2	1	15	0	0	0	0	0	0	0	0
1	2	15	0	0	0	0	0	0	0	0

M = 3; i = 3;

2	15	1	3	6	23	57
1	2	15	3	0	0	0	0	0	0	0
1	2	3	15	0	0	0	0	0	0	0
1	2	3	15	0	0	0	0	0	0	0

M = 4; i = 4;

2	15	1	3	6	23	57
1	2	3	15	6	0	0	0	0	0	0
1	2	3	6	15	0	0	0	0	0	0
1	2	3	6	15	0	0	0	0	0	0

Problema :

Como ordenar um vetor sem o uso de um vetor auxiliar (Ordenado) ?

Algoritmo :

• Para cada elemento i do vetor V.

• Se o valor de i + 1 for menor que i

• Então troque i + 1 com i.

• Senão incremente o valor de i.

• Repita este processo até i chegue ao fim do vetor.

• Repita todo o processo até que todos os elementos do vetor tenham sido comparados.

De: Lendo e medindo o tempo em C e C++: função time()

Bom, chega de teoria e encheção de lingüiça e vamos para o código de uma vez por todas. A função mais conhecida para pegar a data e hora é a função time() da C runtime, que retorna quantidade de segundos desde o "Unix Epoch", que é meia noite (00:00:00) de 1 de Janeiro de 1970.

Características da função time():

• Retorna a quantidade de segundos desde 1 de Janeiro de 1970. Ou seja, a sua precisão máxima é de um segundo. Ou seja, não serve para medir performance. (ou seja, vou explicar mais sobre isso depois)

• O horário retornado é GMT, para pegar o horário local é necessário fazer manualmente o cálculo para ajuste de fuso horário. Para usar o horário local é necessário usar a função get_timezone (ou _tzset no Visual C++) para ler a diferença do fuso que você usará para fazer o cálculo depois.

• Como o retorno da função é um número inteiro, é muito fácil fazer contas com ele. Para avançar a data em dois dias, por exemplo, é só somar [60 * 60 * 24 * 2].

• Durante o inicio dos tempos do unix o retorno era do tipo int de 32 bits. Fazendo uma conta simples com os limites de um inteiro, vemos que o limite de medição é algum dia no ano de 2038, criando uma nova e repaginada versão do bug do milênio. Nas versões mais atuais dessa função o retorno é um int64, o que empurra o limite para uma data bem longínqua, quando provavelmente não haverá mais programadores vivos no universo.

• Por ser uma função da C runtime, está disponível em qualquer compilador C e C++ (qualquer == qualquer compilador não-exótico para plataformas não-exóticas). É provavelmente a função mais multiplataforma de todas que eu vou mostrar

Como um trecho de código vale mais do que 0xFFFFFFFFFFFFFFFF palavras, here we go:

Código:

#include <stdio.h>
#include <tchar.h>
#include <time.h>
#include <iostream>
#include <iomanip>
#include <string>

using namespace std;

void print_time(time_t t)
{
  tm* formatted_time;

  //
  // essa função "quebra" essa quantidade de segundos e dia, mês, ano, etc
  //
  formatted_time = gmtime(&t);

  //
  // isso vai mostrar algo como "2009/12/07 14:42:57"
  // note que é necessário somar 1900 na data para pegar o ano corrente
  //
  cout << setfill('0') <<
    setw(4) << formatted_time->tm_year+1900 << "/" <<
    setw(2) << formatted_time->tm_mon+1 << "/" <<
    setw(2) << formatted_time->tm_mday << " " <<
    setw(2) << formatted_time->tm_hour << ":" <<
    setw(2) << formatted_time->tm_min << ":" <<
    setw(2) << formatted_time->tm_sec << endl;
}


int main()
{
  time_t t;

  //
  // pega o número de segundos desde 1970
  //
  t = time(NULL);

  //
  // mostra na tela, formatado
  //
  print_time(t);

  //
  // pega o fuso horário da máquina para pegar o horário local
  // ao invés de GMT.
  //
  long timezone;

  _tzset(); // carrega as configurações de fuso

  _get_timezone(&timezone); // lê a diferença do fuso

  cout << timezone << endl;

  //
  // ajusta o horário pelo fuso
  //
  t -= timezone;

  print_time(t);

  //
  // avança da data em 2 dias
  //
  t += 48 * 60 * 60;

  //
  // mostra novamente
  //
  print_time(t);

  return 0;
}


Eai galera, blz??

Postando minha contribuição.

Segue o código implementado do algoritmo de Selection Sort

Código:

#include <stdio.h>
#include <tchar.h>
#include <time.h>
#include <iostream>
#include <iomanip>
#include <string>

//definição do DIMENSAOanho do vetor
int const DIMENSAO = 200000; 
//#define DIMENSAO 200000

void print_time(time_t t);
void SelectionSort(int V[DIMENSAO], int N, int Ordenado[DIMENSAO]);
int MenorElemento(int V[DIMENSAO], int N);
using namespace std;

void main ()
{
   time_t t;
   int ordenado[DIMENSAO];
   
   int i, vetor[DIMENSAO];
   //cria os números aleatórios
   srand((unsigned)time( NULL ));
   for (i = 0; i < DIMENSAO; i++)
    //atribui um valor aleatório para cada posição do vetor
    vetor[i] = rand(); 
   /*
   for (i = 0; i < DIMENSAO; i++)
   //apenas imprime o vetor
    cout << vetor[i] << "\t";
   */
   
   t = time(NULL);
  long timezone;

  _tzset(); // carrega as configurações de fuso

  _get_timezone(&timezone); // lê a diferença do fuso

  //
  // ajusta o horário pelo fuso
  //
  t -= timezone;

  cout<< "Inicio da ordenacao: ";
  print_time(t);

   //CHAMADA A FUNÇÃO DE ORDENAÇÃO
    SelectionSort (vetor, DIMENSAO, ordenado);
   //FIM DA ORDENAÇÃO

   t = time(NULL);
  _tzset(); // carrega as configurações de fuso

  _get_timezone(&timezone); // lê a diferença do fuso

  //
  // ajusta o horário pelo fuso
  //
  t -= timezone;
  cout<< "Fim da ordenacao: ";
  print_time(t);
   /*
     for (i = 0; i < DIMENSAO; i++)
   //apenas imprime o vetor
    cout << ordenado[i] << "\t";
   */
   system ("PAUSE");
}

void SelectionSort(int V[DIMENSAO], int N, int Ordenado[DIMENSAO])
{
    int M = 0, i;
    while(N > 0)
    {
            i = MenorElemento(V, N);
            Ordenado[M] = V[i];
            V[i] = V[N - 1];
            N--;
            M++;
    }
}

int MenorElemento(int V[DIMENSAO], int N)
{
   int min = V[0], posicao = 0;
   int i;

   for (i=1;i<N;i++){
      if (V[i]< min){
         min= V[i];
         posicao = i;
      }
   }
   return posicao;
}

void print_time(time_t t)
{
  tm* formatted_time;

  //
  // essa função "quebra" essa quantidade de segundos e dia, mês, ano, etc
  //
  formatted_time = gmtime(&t);

  //
  // isso vai mostrar algo como "2009/12/07 14:42:57"
  // note que é necessário somar 1900 na data para pegar o ano corrente
  //
  cout << setfill('0') <<
    setw(4) << formatted_time->tm_year+1900 << "/" <<
    setw(2) << formatted_time->tm_mon+1 << "/" <<
    setw(2) << formatted_time->tm_mday << " " <<
    setw(2) << formatted_time->tm_hour << ":" <<
    setw(2) << formatted_time->tm_min << ":" <<
    setw(2) << formatted_time->tm_sec << endl;
}

Implementado todos os metodos de implemtentação

Código:

#include <iostream> //biblioteca para uso da função srand e rand para gerar números //aleatórios
#include <stdlib.h>
#include <time.h> //biblioteca para uso da função time
#include <iomanip>
#include <string>
using namespace std;
int const DIMENSAO = 1000; //definição do tamanho do vetor

int menu(int DIMENSAO);
void bubbleSort(int *, const int );
void swap(int * const element1Ptr, int * const element2Ptr);
void print_time(time_t t);
void InsertionSort( int V[DIMENSAO], int N, int Ordenado[DIMENSAO]);
void SelectionSort(int V[DIMENSAO], int N, int Ordenado[DIMENSAO]);
int MenorElemento(int V[DIMENSAO], int N);

void main()
{
  int i, vetor[DIMENSAO], op, op2;
  time_t t;
    srand((unsigned)time( NULL )); //cria os números aleatórios
  for (i = 0; i < DIMENSAO; i++)
    vetor[i] = rand(); //atribui um valor aleatório para cada posição do vetor
  for (i = 0; i < DIMENSAO; i++)
    cout << vetor[i] << "\t"; //apenas imprime o vetor
  cout<< "\n\n\n\n";
  do{

    op=menu(DIMENSAO);
    if(op == 1 )
    {
        t = time(NULL);
        long timezone;

        _tzset(); // carrega as configurações de fuso

        _get_timezone(&timezone); // lê a diferença do fuso
   
        //
        // ajusta o horário pelo fuso
        //
        t -= timezone;

        cout<< "Inicio da ordenacao: ";
        print_time(t);
   
        bubbleSort(vetor, DIMENSAO);
   
        t = time(NULL);
        _tzset(); // carrega as configurações de fuso

        _get_timezone(&timezone); // lê a diferença do fuso

        //
        // ajusta o horário pelo fuso
        //
        t -= timezone;
        cout<< "Fim da ordenacao: ";
        print_time(t);
        system("pause");
        do{
            system("cls");
            cout<< "Gostaria de imprimir o vetor ordenado? s/n\n";
            cin>> op2;
            if(op2 != 'n' || op2 != 'N' || op2 != 's' || op2 != 'S')
            {
                system("cls");
                cout<< "A opcao e invalida, digite s ou S para sim ou n ou N pra nao\n";
                system("pause");
            }
        }while(op2 != 'n' || op2 != 'N' || op2 != 's' || op2 != 'S');
        if(op2 == 's' || op2 == 'S')
        {
            for (i = 0; i < DIMENSAO; i++)
                cout << vetor[i] << "\t"; //apenas imprime o vetor
              cout<< "\n\n\n\n";   
        }       
      }
      else
        if(op == 2)
            {
        int ordenado[DIMENSAO];
        t = time(NULL);
        long timezone;
   
        _tzset(); // carrega as configurações de fuso
   
        _get_timezone(&timezone); // lê a diferença do fuso

        //
        // ajusta o horário pelo fuso
        //
        t -= timezone;

        cout<< "Inicio da ordenacao: ";
        print_time(t);
   
        SelectionSort (vetor, DIMENSAO, ordenado);

        t = time(NULL);
        _tzset(); // carrega as configurações de fuso

        _get_timezone(&timezone); // lê a diferença do fuso

        //
        // ajusta o horário pelo fuso
        //
        t -= timezone;
        cout<< "Fim da ordenacao: ";
        print_time(t);
        system("pause");
        do{
            system("cls");
            cout<< "Gostaria de imprimir o vetor ordenado? s/n\n";
            cin>> op2;
            if(op2 != 'n' || op2 != 'N' || op2 != 's' || op2 != 'S')
            {
                system("cls");
                cout<< "A opcao e invalida, digite s ou S para sim ou n ou N pra nao\n";
                system("pause");
            }
        }while(op2 != 'n' || op2 != 'N' || op2 != 's' || op2 != 'S');
        if(op2 == 's' || op2 == 'S')
        {
            for (i = 0; i < DIMENSAO; i++)
                cout << ordenado[i] << "\t"; //apenas imprime o vetor
              cout<< "\n\n\n\n";   
        }   
        }
        else
      if(op == 3)
      {
        int Ordenado[DIMENSAO];
        t = time(NULL);
        long timezone;

        _tzset(); // carrega as configurações de fuso

        _get_timezone(&timezone); // lê a diferença do fuso

        //
        // ajusta o horário pelo fuso
        //
        t -= timezone;

        cout<< "Inicio da ordenacao: ";
        print_time(t);

        InsertionSort(vetor, DIMENSAO ,Ordenado);
 
        t = time(NULL);
        _tzset(); // carrega as configurações de fuso

        _get_timezone(&timezone); // lê a diferença do fuso

        //
        // ajusta o horário pelo fuso
        //
        t -= timezone;
        cout<< "Fim da ordenacao: ";
        print_time(t);   
        system("pause");
        do{
            system("cls");
            cout<< "Gostaria de imprimir o vetor ordenado? s/n\n";
            cin>> op2;
            if(op2 != 'n' || op2 != 'N' || op2 != 's' || op2 != 'S')
            {
                system("cls");
                cout<< "A opcao e invalida, digite s ou S para sim ou n ou N pra nao\n";
                system("pause");
            }
        }while(op2 != 'n' || op2 != 'N' || op2 != 's' || op2 != 'S');
        if(op2 == 's' || op2 == 'S')
        {
            for (i = 0; i < DIMENSAO; i++)
                cout << Ordenado[i] << "\t"; //apenas imprime o vetor
              cout<< "\n\n\n\n";   
        }   
        }
  }while(op != 4);
}

int menu(int DIMENSAO)
{
  int op;
  do{
    system("cls");
    cout<< "============================================\n";
    cout<< "\tVetor de " << DIMENSAO << endl;
    cout<< "============================================\n";
    cout<< "\t1- Ordenar por Bubble Sort\n";
    cout<< "\t2- Ordenar por Insertion Sort\n";
    cout<< "\t3- Ordenar por Selection Sort\n";
    cout<< "\t4- Sair\n";
    cout<< "============================================\n";
    cout<< "\n\tDigite a opcao desejada\n\t";
    cin>> op;
    if(op < 1 || op > 4)
    {
        system("cls");
        cout<< "\tOpcao invalida tende novamente\n";
        system("pause");
    }
  }while(op < 1 || op > 4);
 
  return op; 
}

void bubbleSort(int *array, const int size)
{
    void swap(int * const, int * const);

    for(int pass = 0; pass < size -1; pass++)
        for(int j = 0; j < size - 1; j++)
            if(array[j] > array[ j + 1 ])
                swap( &array[ j ], &array[ j + 1 ]);
}

void swap(int * const element1Ptr, int * const element2Ptr)
{
    int hold= *element1Ptr;
    *element1Ptr = *element2Ptr;
    *element2Ptr = hold;
}

void print_time(time_t t)
{
  tm* formatted_time;

  //
  // essa função "quebra" essa quantidade de segundos e dia, mês, ano, etc
  //
  formatted_time = gmtime(&t);

  //
  // isso vai mostrar algo como "2009/12/07 14:42:57"
  // note que é necessário somar 1900 na data para pegar o ano corrente
  //
  cout << setfill('0') <<
    setw(4) << formatted_time->tm_year+1900 << "/" <<
    setw(2) << formatted_time->tm_mon+1 << "/" <<
    setw(2) << formatted_time->tm_mday << " " <<
    setw(2) << formatted_time->tm_hour << ":" <<
    setw(2) << formatted_time->tm_min << ":" <<
    setw(2) << formatted_time->tm_sec << endl;
}

void InsertionSort( int V[DIMENSAO], int N, int Ordenado[DIMENSAO])
{
    int M = 0, i, j, k;
    for (i = 0; i < N; i++)
    {
          Ordenado[M] = V[i];  k = M;
          for (j = M - 1; j >= 0; j--)
              if (Ordenado[k] < Ordenado[j] )
                swap(&Ordenado[k--], &Ordenado[j]);
        else
                break;
          M++;
    }
}

void SelectionSort(int V[DIMENSAO], int N, int Ordenado[DIMENSAO])
{
    int M = 0, i;
    while(N > 0)
    {
            i = MenorElemento(V, N);
            Ordenado[M] = V[i];
            V[i] = V[N - 1];
            N--;
            M++;
    }
}

int MenorElemento(int V[DIMENSAO], int N)
{
  int min = V[0], posicao = 0;
  int i;

  for (i=1;i<N;i++){
      if (V[i]< min){
        min= V[i];
        posicao = i;
      }
  }
  return posicao;
}

ok galera. vou postar meus apontamentos(cod. + tabela em segundos.).

Código:

#include <iostream>
//biblioteca para uso da função srand e rand para gerar números //aleatórios
#include <stdlib.h>
//biblioteca para uso da função time
#include <time.h>
using namespace std;
//definição do tamanho do vetor
int const DIMENSAO = 1000;
void bubble_sort(int vetor[DIMENSAO]);
void insertion_sort(int vetor[DIMENSAO]);
void selection_sort(int vetor[DIMENSAO]);
int menu();

void main()
{ 
  int i, v[DIMENSAO], op;
  double segundos;
  time_t start, end;
  //cria os números aleatórios
  srand((unsigned)time( NULL ));
  for (i = 0; i < DIMENSAO; i++)
      //atribui um valor aleatório para cada posição do vetor
      v[i] = rand();
  cout<<"Os valores foram assignados no vetor aleatoriamente.\n";
  do{
     op=menu();
     if(op==1)
     {
        cout<<"Aguarde, ordenando vetor de "<<DIMENSAO <<" posicoes.";
        time (&start);
        bubble_sort(v);
        time  (&end);
        segundos = difftime (end,start);
        cout<<"Vetor ordenado em "<<segundos <<" segundo(s)\n\n";
     }
     else
        if(op==2)
        {
           cout<<"Aguarde, ordenando vetor de "<<DIMENSAO <<" posicoes.";
           time(&start);
           insertion_sort(v);
           time(&end);
           segundos = difftime (end,start);
           cout<<"Vetor ordenado em "<<segundos <<" segundo(s)\n\n";}
        else
           if(op==3)
           {
              cout<<"Aguarde, ordenando vetor de "<<DIMENSAO <<" posicoes.";
              time(&start);
              selection_sort(v);
              time(&end);
              segundos = difftime(end,start);
              cout<<"Vetor ordenado em "<<segundos <<" segundo(s)\n\n";}
           else
              if(op==4)
                 for (i = 0; i < DIMENSAO; i++)//apenas imprime o vetor
                    cout << v[i] << "\n";
              else
                 if(op==5) //sair.
                 {
                    //cria os números aleatórios
  srand((unsigned)time( NULL ));
  for (i = 0; i < DIMENSAO; i++)
      //atribui um valor aleatório para cada posição do vetor
      v[i] = rand();
  cout<<"Os valores foram assignados no vetor aleatoriamente.\n";
                 }
                 else
                    if(op==6)
                    {}

  }while(op!=6);
}
void bubble_sort(int vetor[DIMENSAO])
{
   int pass, i, aux;
    for ( pass = 0; pass < DIMENSAO - 1; pass++ ) // passagens
        for ( i = 0; i < DIMENSAO - 1; i++ ) // uma passagem
            if ( vetor[ i ] > vetor[ i + 1 ] ) // uma comparação
            {
                aux = vetor[ i ]; // uma permuta
                vetor[ i ] = vetor[ i + 1 ];
                vetor[ i + 1 ]= aux;
         }
}
void insertion_sort(int vetor[DIMENSAO])
{
   int j ,i ,key;
   for(j=0 ; j<=DIMENSAO-1;j++)
   {
      key = vetor[j];
      i = j -1;
      while(i>(-1) && vetor[i]>key)
      {
         vetor[i+1] = vetor[i];
         i = i -1;
      }
      vetor[i+1] = key;
   }


}
void selection_sort(int vetor[DIMENSAO])
{
    int i, j, min;
  for (i = 0; i < (DIMENSAO-1); i++) {
    min = i;
    for (j = (i+1); j < DIMENSAO; j++) {
      if(vetor[j] < vetor[min]) {
        min = j;
      }
    }
    if (i != min) {
      int swap = vetor[i];
      vetor[i] = vetor[min];
      vetor[min] = swap;
    
    }
  }
}
int menu()
{
   int opcao;
   do{
      cout<<"Escolha o metodo de ordenacao:\n\n";
      cout<<"1 - BUBBLE SORT\n2 - INSERTION SORT\n3 - SELECTION SORT\n4 - IMPRIME VETOR\n5 - DESORDENA VETOR\n6 - SAIR\n\n";
      cin>>opcao;
      if(opcao<1||opcao>6)
      cout<<"Opcao invalida";
     }while(opcao<1||opcao>6);
      return opcao;
}

dimensão	bubble	insertion	selection
1000	0	0	0
2000	0	0	0
4000	0	0	0
8000	1	0	0
10000	1	0	0
20000	3	1	1
40000	11	2	4
60000	26	6	8
80000	47	10	15
200000	294	61	92