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
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.
– Kevin Kouketsu
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
@anonimo I saw the algorithm of
BubbleSort
, but he uses awhile()
and within it afor()
, leaving the algorithmO(n²)
, it is possible to do what I am trying to do inO(n)
? Where it does the full scan, leaving every vector completely ordered ?– user148754
@Kevinkouketsu this will be the end, but this end may not mean that the vector is fully ordered, no?
– user148754
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.
– anonimo
@anonymously look, I changed the question.
– user148754
I think your right loop should start from left+1 instead of 1 and go to tam, not tam-1.
– anonimo
@almost expensive anonymity! OUTPUT was this:
213456789
– user148754
In the index of the comparison and in the exchange do not use right + 1, use only right.
– anonimo
@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.
– user148754
@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.
– anonimo