[Código] Metodos de Ordenacao

[Myho 2]

3 metodos simples e conhecidos de como ordenar um vetor.

 

 

// Funcao q realiza as trocas
void swap(int &num1, int &num2)
{
   int num3 = num1;
   num1 = num2;
   num2 = num3;
}

------------------------------------------------------------

void insertionSort(int *vetor, int tamanho)
{
   for( int i = 1; i < tamanho; i++ ) {
	  for( int j = i; j > 0; j-- ) {
		 if( vetor[j] < vetor[j-1] )
			swap( vetor[j], vetor[j-1] );
	  }
   }
}

-------------------------------------------------------------

void bubbleSort(int *vetor, int tamanho)
{
   for( int i=0; i < tamanho; i++ ){
	  for( int j = tamanho - 1; j > i; j-- ){
		 if( vetor[j] < vetor[j-1] ) 
			 swap( vetor[j], vetor[j-1] );
	  }	
   }
}

------------------------------------------------------------------

void selectionSort(int *vetor, int tamanho)
{
   int k;
   for( int i = 0; i < tamanho; i++ ){
	  k =i;
	  for( int j = tamanho - 1; j > i; j-- ){
		 if(vetor[j] < vetor[k]) 
			k = j;
	  }
	  swap( vetor[i], vetor[k] );
   }
}

-----------------------------------------------------

Aqui o codigo-fonte ( em c++ ) completo de um programa que testa o tempo gasto por cada metodo para ordenar um mesmo vetor. Recomendo comecar com valores entre 5000 e 10000 para comparacoes.

OBS- a funcao imprimeVetor esta comentada pois nao faz sentido imprimir todos os numeros de um vetor gigante.

Para testes com vetores menores, para obeservar se o vetor realmente esta ordenado, ai vale a pena mostrar os numeros.

 

#include <iostream>
#include <time.h>
#include <cstdlib>

using namespace std;

// FUNCAO QUE REALIZA AS TROCAS DE POSICOES
void swap(int &num1, int &num2)
{
   int num3 = num1;
   num1 = num2;
   num2 = num3;
}

// FUNCAO QUE FAZ UMA COPIA DE UM ARRAY
void copiaVetor(int *original, int *final, int tamanho)
{
   for (int i = 0; i < tamanho; i++)
	   final[i] = original[i];
}

// FUNCAO QUE PREENCHE UM VETOR COM NUMEROS ALEATORIOS
void geraNumeros(int *vetor, int tamanho, int range)
{
	for (int i = 0; i < tamanho; i++ ) {
		vetor[i] = rand() % range;
	}
}

// FUNCAO QUE IMPRIME UM VETOR
void imprimeVetor(int *vetor, int tamanho)
{
	for( int i = 0; i < tamanho; i++ )
		cout << vetor[i] << ' ';
	cout << endl;
}

void insertionSort(int *vetor, int tamanho)
{
	for( int i = 1; i < tamanho; i++ ) {
		for( int j = i; j > 0; j-- ) {
			if( vetor[j] < vetor[j-1] )
				swap( vetor[j], vetor[j-1] );
		}
	}
}

void bubbleSort(int *vetor, int tamanho)
{
   for( int i=0; i < tamanho; i++ ){
	  for( int j = tamanho - 1; j > i; j-- ){
		 if( vetor[j] < vetor[j-1] ) 
		   swap( vetor[j], vetor[j-1] );
	  }	
   }
}

void selectionSort(int *vetor, int tamanho)
{
	int k;
	for( int i = 0; i < tamanho; i++ ){
		k =i;
		for( int j = tamanho - 1; j > i; j-- ){
			if(vetor[j] < vetor[k]) 
				k = j;
		}
		swap( vetor[i], vetor[k] );
	}
}


int main()
{
	clock_t begin, end;
	srand(time(NULL));
	int tamanhoDoVetor;
	int *vetor; //VETOR QUE SERVIRA DE MODELO
	int *copiaDoVetor; // VETOR QUE APOS RECEBER A COPIA DO VETOR MODELO SERA ORDENADO
	cout << "Digite o tamanho do vetor: ";
	cin >> tamanhoDoVetor;
	vetor = new int[tamanhoDoVetor];
	copiaDoVetor = new int[tamanhoDoVetor];

	geraNumeros(vetor,tamanhoDoVetor,10*tamanhoDoVetor);

	copiaVetor(vetor,copiaDoVetor,tamanhoDoVetor);
	//cout << endl << "Vetor desordenado: "<< endl;
	//imprimeVetor(vetor, tamanhoDoVetor);
	begin = clock();
	selectionSort(copiaDoVetor,tamanhoDoVetor);
	end = clock();
	cout << "SelectionSort demorou: ";
	cout << ((double) (end - begin)) / CLOCKS_PER_SEC;
	cout << " segundos" << endl;
	//cout << "Vetor ordenado: " << endl;
	//imprimeVetor(copiaDoVetor,tamanhoDoVetor);


	copiaVetor(vetor,copiaDoVetor,tamanhoDoVetor);
	//cout << endl << "Vetor desordenado: "<< endl;
	//imprimeVetor(vetor, tamanhoDoVetor);
	begin = clock();
	insertionSort(copiaDoVetor,tamanhoDoVetor);
	end = clock();
	cout << "InsertionSort demorou: ";
	cout << ((double) (end - begin)) / CLOCKS_PER_SEC;
	cout << " segundos" << endl;
	//cout << "Vetor ordenado: " << endl;
	//imprimeVetor(copiaDoVetor,tamanhoDoVetor);


	copiaVetor(vetor,copiaDoVetor,tamanhoDoVetor);
	//cout << endl << "Vetor desordenado: "<< endl;
	//imprimeVetor(vetor, tamanhoDoVetor);
	begin = clock();
	bubbleSort(copiaDoVetor,tamanhoDoVetor);
	end = clock();
	cout << "BubbleSort demorou: ";
	cout << ((double) (end - begin)) / CLOCKS_PER_SEC;
	cout << " segundos" << endl;
	//cout << "Vetor ordenado: " << endl;
	//imprimeVetor(copiaDoVetor,tamanhoDoVetor);

	system("pause");
	return 0;
}

Obs2* Se escrever o codigo do swap dentro das proprias funcoes, o tempo de ordenacao diminui consideravelmente para o Bubble e Insertion, visto q estes dois utilizam muitos swaps. Para o selection nem ha diferenca, ja que sao poucas chamadas para o swap.

[quitZAUMMM 18]

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif

 

boa contribuição!!