Programar em C/Algoritmos de ordenação

Insertion sort

void insertion_sort(int tabela[], int largura){
	int i, memoria, contador; 
	bool marcador; 
	for(i=1; i<largura; i++){
		memoria = tabela[i];
		contador = i-1;
		do{
			marcador = false;
			if(tabela[contador] > memoria){
				tabela[contador+1] = tabela[contador];
				contador--;
				marcador = true;
			}
			if(contador < 0) marcador = false;
		}while(marcador);
	}
	tabela[contador+1] = memoria;
}

Selection sort

void selectionSort3( int vetorDesordenado[], int tamanhoVetor ){ //Funçao selection recebendo vetor e tamanho
	int i, j, posicaoValorMinimo;
	for (i = 0; i < ( tamanhoVetor - 1 ); i++){ //Loop para percorrer o vetor
		posicaoValorMinimo = i; //O valor minimo de posiçao do vetor a ser percorrido e 0
		for (j = ( i + 1 ); j < tamanhoVetor; j++){ 			//Percorreremos o vetor da posiçao 1 ate o tamanho estimado 
			if( vetorDesordenado[j] < vetorDesordenado[posicaoValorMinimo]){ //Se a posiçao que vamos verificar for menos que a posiçao que temos em maos
				posicaoValorMinimo = j; //A variavel 'j' recebe esse valor
			}
		}
		if ( i != posicaoValorMinimo ){
			trocarPosicaoValores( &vetorDesordenado[i], &vetorDesordenado[posicaoValorMinimo] );//vamos chamar uma outra funçao para trocar as posiçoes de lugares  
		}
	}
}
void trocarPosicaoValores( int *posicaoA, int *posicaoB ){ //Funçao para trocar as posiçoes que estamos olhando
	int temporario;
	temporario = *posicaoA;
	*posicaoA = *posicaoB;
	*posicaoB = temporario;     
}

Bubble sort

O bubble sort, ou ordenação por flutuação (literalmente "por bolha"), é um algoritmo de ordenação dos mais simples. A ideia é percorrer o vetor diversas vezes, a cada passagem fazendo flutuar para o topo o maior elemento da sequência. Essa movimentação lembra a forma como as bolhas em um tanque de água procuram seu próprio nível, e disso vem o nome do algoritmo.

No melhor caso, o algoritmo executa $n$ operações relevantes, onde n representa o número de elementos do vetor. No pior caso, são feitas $n^{2}$ operações. A complexidade desse algoritmo é de Ordem quadrática. Por isso, ele não é recomendado para programas que precisem de velocidade e operem com quantidade elevada de dados.

Código da Função

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

Código da Função Melhorado

Termina a execução quando nenhuma troca é realizada após uma passada pelo vetor.

void BubbleSort(int vetor[], int tamanho){
	int memoria, troca, i, j;
	troca=1; /*A variável "troca" será a verificação da troca em cada passada*/
	for(j=tamanho-1; (j>=1) && (troca==1); j--){
		troca=0; /*Se o valor continuar 0 na próxima passada quer dizer que não houve troca e a função é encerrada.*/
		for(i=0; i<j; i++){
				if(vetor[i]>vetor[i+1]){
					memoria=vetor[i];
					vetor[i]=vetor[i+1];
					vetor[i+1]=memoria;
					troca=1; /*Se houve troca, "troca" recebe 1 para continuar rodando.*/
			}
		}
	}
}