0

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
11
  • Faça dois loops. Um iterando entre cada item, o outro iterando do índice do primeiro + 1. O fim será quando o primeiro loop acabar. Commented 11/06/2019 às 19:16
  • Você tem que fazer uma varredura completa no vetor comparando cada elemento com o seguinte e, se houver uma troca, ligar a flag trocou. Note que você está desligando a flag a cada comparação e não apenas a cada ciclo. do { trocou = false; for (i=0; i<tam-1; i++) { /*verifica ordem*/} } while (trocou);
    – anonimo
    Commented 11/06/2019 às 19:17
  • @anonimo eu vi o algoritmo do BubbleSort, porém ele utiliza um while() e dentro dele um for(), deixando o algoritmo O(n²), é possível fazer o que estou tentando em O(n)? Onde ele faz a varredura completa, deixando todo vetor completamente ordenado ?
    – user148754
    Commented 11/06/2019 às 19:19
  • 1
    Creio que seu loop com a variação de direita deva partir de esquerda+1 e não de 1 e deva ir até tam, e não tam-1.
    – anonimo
    Commented 11/06/2019 às 20:02
  • 1
    Nos índices da comparação e na troca não use direita + 1, use apenas direita.
    – anonimo
    Commented 11/06/2019 às 20:14

1 Resposta 1

0

Com os comentários deste usuário, consegui criar um código para o mesmo. Para os demais ficarem sabendo o funcionamento, segue o código:

#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]) {
                int aux = v[direita];
                v[direita] = v[esquerda];
                v[esquerda] = aux;
            }
        }
    }

    printf("ACABOU!\n");
    for(int i = 0; i < tam-1; i++) {
        printf("%d", v[i]);
    }
}


int main()
{
    int A[] = { 5, 1, 8, 4, 3, 10, 6, 2, 9, 7 };
    bubbleSort(A, 10);

    return 0;
}

Você deve fazer log-in para responder a esta pergunta.