Why isn’t my vector getting sorted?

Asked

Viewed 69 times

0

I’m trying to create a code, where it orders a vector of integer for matter of size, where the rule is the same as bubbleSort:

  • Compare Left to Right
  • If the Left value is greater than the Right value, the Right value should go to Left and the Left value to Right.

Example:

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

This vector should look like:

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

Follow my code so far:

#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
c

  • Make two loops. One iterating between each item, the other iterating the index of the first + 1. The end will be when the first loop ends.

  • You have to do a full scan of the vector by comparing each element with the following and, if there is a switch, turn on the switched flag. Note that you are turning off the flag at each comparison and not just at each cycle. do { trocau = false; for (i=0; i<tam-1; i++) { /check order/} } while (switched);

  • @anonimo I saw the algorithm of BubbleSort, but he uses a while() and within it a for(), leaving the algorithm O(n²), it is possible to do what I am trying to do in O(n)? Where it does the full scan, leaving every vector completely ordered ?

  • @Kevinkouketsu this will be the end, but this end may not mean that the vector is fully ordered, no?

  • I don’t know any sort algorithm that is on average O(n). The best I’ve seen are O(n log n). But it’s been a long time since I’ve studied this subject.

  • @anonymously look, I changed the question.

  • 1

    I think your right loop should start from left+1 instead of 1 and go to tam, not tam-1.

  • @almost expensive anonymity! OUTPUT was this: 213456789

  • 1

    In the index of the comparison and in the exchange do not use right + 1, use only right.

  • @anonymo very good! Post an answer from you with my code and his correction, explain also what is happening to give that error and explain what is the correct way for other people to understand, I will sign your question as the correct one, if you can give me a punctuation also in the question, because it is not something trivial in a certain way.

  • @THIAGODEBONIS: In Wikipedia you find a detailed explanation of various sorting methods. I read that there is a method that is O(n) but that uses n processors and requires n² of memory, which certainly does not work for normal applications.

Show 6 more comments

1 answer

0


With the comments of this user, I was able to create a code for it. For others to know how it works, follow the code:

#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;
}

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.