Bubble Sort §

---

O algoritmo de bubble sort consiste em comparar pares consecutivos e, caso necessário, trocas as posições quando o elemento a esquerda for maior do que a da direita.

Note

Bubble sort é o algoritmo de ordenação com o pior desempenho com uma complexidade de tempo .

Implementação:

void bubble_sort(int v[], int n) {
	// repetir (n – 1) vezes
	for (int i = 1; i < n; ++i) {
		// percorrer cada posição do vetor
		for (int j = 0; j < n - 1; ++i) {
			// se elemento atual for maior que o próximo
			if (v[i] > v[i + 1]) {
				// trocar os elementos entre as 2 posições
				trocar(v, i, i + 1);
			}
		}
	}
}

Existe uma variação desse algoritmo chamado de bubble sort com sentinela que basicamente adicionar uma variável booleana “sentinela”, inicialmente com valor false, para indicar se houve alguma alteração no vetor. Se alguma troca for feita o valor é alterado para true, caso contrário, para false e então o algoritmo é encerrado.

Implementação:

void bubble_sort(int v[], int n) {
	for (int i = 1; i <= n - 1; ++i) {
		bool sentinela = false; 
		for (int j = 0; j < n - 1; ++i) {
			if (v[i] > v[i + 1]) {
				trocar(v, i, i + 1);
				mudou = true;
			}
		}
 
		if (!sentinela) {
			return;
		}
	}
}

Referências §

---