Estou tentando criar um código, onde o mesmo ordena um vetor de integer
por questão de tamanho, onde a regra é a mesma do bubbleSort:
- Irá comparar o valor da Esquerda com o da Direita
- Caso o valor da Esquerda for maior do que o da Direita, o valor da Direita deverá ir para a Esquerda e o valor da Esquerda para a Direita.
Exemplo:
int A[] = { 5, 1, 8, 4, 3, 10, 6, 2, 9, 7 };
Este vetor deverá ficar como:
int A[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
Segue meu código até o momento:
#include <iostream>
using namespace std;
void bubbleSort(int v[], int tam) {
for(int esquerda = 0; esquerda < tam-1; esquerda++) {
for(int direita = esquerda+1; direita < tam; direita++) {
if(v[esquerda] > v[direita+1]) {
int aux = v[direita+1];
v[direita+1] = v[esquerda];
v[esquerda] = aux;
}
}
}
printf("ACABOU!\n");
for(int i = 0; i < 9; i++) {
printf("%d", v[i]);
}
}
int main()
{
int A[] = { 5, 1, 8, 4, 3, 10, 6, 2, 9, 7 };
bubbleSort(A, 10);
return 0;
}
OUTPUT:
ACABOU!
213456789
BubbleSort
, porém ele utiliza umwhile()
e dentro dele umfor()
, deixando o algoritmoO(n²)
, é possível fazer o que estou tentando emO(n)
? Onde ele faz a varredura completa, deixando todo vetor completamente ordenado ?