[Código] Metodos de Ordenacao

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.