Bubble sort problem

[GonlyG]

I have to bubble sort (compare pairs) of numbers in an array until the numbers are in an ascending order, then output number of passes followed by number of swaps. However, I'm stuck as I don't know how to keep on passing through the bubble until each number in the array is greater than the previous (except the first, which is the least). I could list all the arrays [if (array[0]<array[1]<array[2].....)] but, surely there is a better way. In pseudo-code, it would probably look like:
Get num1, num2
[if num2 > num1,
swap (num1, num2);swap++)
pass++
Do until array is in ascending order

This is what I have so far:

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int a, b, c, passes, swaps;
cin>>a;
b=0; c=1;
int array [a];
for (int i=0; i<a;i++){
cin>>array[b]>>array[c];
if (array[c]>array[b])
{swap(array[b],array[c]); swaps++;}
b++; c++;}
cout<<passes<<" "<<swaps;}

any hints/tips?

[jlb]

You may want to start with a program that actually compiles without any warnings or errors.

 In function 'int main()':
8:13: warning: ISO C++ forbids variable length array 'array' [-Wvla]
14:7: warning: 'passes' is used uninitialized in this function [-Wuninitialized]
14:25: warning: 'swaps' may be used uninitialized in this function [-Wmaybe-uninitialized]

You should also start using a consistent indentation style and a little whitespace would help make your program much easier to read.

https://en.wikipedia.org/wiki/Indent_style

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int a, b = 0, c = 0, passes = 0, swaps = 0;

    cin >> a;

    int array[a];

    for (int i = 0; i < a; i++)
    {
        cin >> array[b] >> array[c];
        if (array[c] > array[b])
        {
            swap(array[b], array[c]);
            swaps++;
        }
        b++;
        c++;
    }
    cout << passes << " " << swaps;
    
    return 0;
}

You probably should re-examine your documentation for the bubble sort and you may want to consider using a function for the sort routine.

[GonlyG]

thanks for the tip, I tried creating a function in addition to my main code:

#include <iostream>
#include <algorithm>
using namespace std;
int Bubblesort (int array []){
       int b = 0, c = 0, passes = 0, swaps = 0;
         {passes++;
            for (int i = 0; i < 23; i++)
        {cin >> array[b] >> array[c];
       
             if (array[c] > array[b])
            {
             swap(array[b], array[c]);
                swaps++;
            }
        b++;
        c++;
            } 
        } //while the array is not complete, or "do until this function changes nothing"
    return (passes, swaps);
}
int main()
{
    int a; 
    cin >> a;
    int array[a];
    cout<< Bubblesort(array[a]); 
}
   

I'm still not sure how to test if the array is not complete. (And also, is the function correct? I'm not sure how to fix the error "invalid conversion from 'int' to 'int*'", and also an error " note: initializing argument 1 of 'int Bubblesort(int*)'"

[jlb]

Look at this snippet: cout<< Bubblesort(array[a]); Here you are passing a single instance of your array class, you should be passing the entire array. You should also be passing the number of elements that are in the array to this function.

Next look at this snippet:

int a; 
    cin >> a;
    int array[a];

In this snippet you are creating what is called a VLA (Variable Length Array). This is not allowed in a C++ program. You either need to create an array of much larger dimensions or use dynamic memory (new/delete) to create the array.

You really should consider making another function that retrieves the data from the user and fills the array elements. Use your bubble sort function just to sort the array. Keep your functions small doing as little as possible. This'll make testing and troubleshooting the functions much easier.

You also need to find and review some documentation for your bubble sort since what you have is not a bubble sort.

[GonlyG]

I tried this:

#include <iostream>
#include <algorithm>
using namespace std;
int Bubblesort (int array []){
       int b = 0, c = 0, passes = 0, swaps = 0;
         {passes++;
            for (int i = 0; i < 23; i++)
        {cin >> array[b] >> array[c];
       
             if (array[c] > array[b])
            {
             swap(array[b], array[c]);
                swaps++;
            }
        b++;
        c++;
            } 
        } //while the array is not complete, or "do until this function changes nothing"
    return (passes, swaps);
}
int GetArray (int a){
    cin >> a;
   int array [1000];
   int b=0;
   for (int i=0; i<a;i++){
       cin>>array[b];
       b++;
   }
   return 0;
}
int main()
{
    int a;
    cin>>a;
    GetArray(a);
    int array [1000];
    cout<< Bubblesort(array); 
}
   

So I'm getting somewhere but I still am not sure how to keep on passing it through until the sequence is complete.

No errors except return passes, swaps.

[dhayden]

Programming requires you to tell the compiler exactly what you want it to do. It isn't like person-to-person instructions. So you need to understand exactly what the different things in your program do.

Right now GetArray is populating the array declared at line 23. But since that's a local variable, it disappears when GetArray returns to main(). So you should declare the array inside main and pass it to GetArray().

// Read "a" integers from cin and put them into "array"
int GetArray(int a, int array[]) {
...
}
...
int main()
{
    int a;
    int array[1000];
    cin >> a;
    GetArray(a, array);
    ...
}

Make sure you understand what's going on here. You will need to change your implementation of GetArray to use the "a" parameter that's passed in. In other words, GetArray() should not read a, it should just popualate the array.

Next, I would creat a separate function to print out the array:

// Print the values in array, which has "size" elements in it.
void PrintArray(int size, int array[])
{
    ....
}

You'll need this anyway, but the for now, you can use it to make sure that GetArray is working. Just call PrintArray right after calling GetArray. This will tell you if you're reading the numbers correctly. Trust me, I've seen plenty of people go nuts trying to get their sorting routine to work, only to discover that they weren't reading the input correctly in the first place.

Now the BubbleSort() function should only sort the numbers. Right now BubbleSort is trying to read numbers from cin also.

You need to tell BubbleSort how many numbers are in the array. Also, it shouldn't return anything. It just sorts the array. So it should be

void BubbleSort(int size, int array[]) {
    ....
}

Print the result of the sorted array in main, right after you call BubbleSort(). For testing, you might want to print the array after each pass through the loop inside BubbleSort also. You can remove that code once the sort is working correctly.

[jlb]

Your GetArray() function should look more like:

int GetArray (int array[], size_t array_size)
{
    int a = 0;
    // Make sure you don't under or over flow your array.
    while(a < 1 || a > array_size)
    {
       cout << "Please enter the number of elements in your array: ";
        cin >> a;
    }
    int i;
    for(i = 0; i < a; i++)
    {
        cin >> array[i];
    }
    return i;
}

And it should be called like:

...
    const size_t MAX_ARRAY = 1000;
    int array[MAX_ARRAY];
    size_t number_of_elements = GetArray(array, MAX_ARRAY);
...

Your bubble sort function signature should look similar, but instead of passing MAX_ARRAY you would pass the number_of_elements. And you really don't need to return anything from this function.

Perhaps you should also review how to pass things to and from functions?
http://www.cplusplus.com/doc/tutorial/functions/

Also as I said your bubble sort function should just be sorting the array, not getting the values from the user. And you really really need to find and study some documentation for the bubble sort algorithm. Perhaps something like:
https://en.wikipedia.org/wiki/Bubble_sort
or
http://www.algolist.net/Algorithms/Sorting/Bubble_sort

You should note that this sort has two loops, one embedded within the other.

[GonlyG]

dang, this is harder than i thought it would be.

#include <iostream>
#include <algorithm>
using namespace std;
int* Bubblesort (int size, int array []){
       int b = 0, c = 0, swaps=0, passes = 0;
       bool swapped = true;
        do {swapped = false;
            passes++;
            for (int i = 0; i < size; i++)
        {if (array[c] > array[b])
            { swap(array[b], array[c]);
                swaps++;
                swapped = true;
            }
        b++;
        c++;}
        } while (swapped == true);
return array;} 
int GetArray (int array[], size_t array_size)
{
    int a = 0;
    while(a < 1 || a > array_size)
    {
       //number of elements in array
        cin >> a;
    }
    int i;
    for(i = 0; i < a; i++)
    {
        cin >> array[i];
    }
    return i;
}
int main()
{
     const size_t MAX_ARRAY = 1000;
    int array[MAX_ARRAY];
    size_t number_of_elements = GetArray(array, MAX_ARRAY);
    cout<< Bubblesort(number_of_elements, array); 
}
   
   

I got the weird message "0x7ffcbfb55c00". Is this one of the "run from command line" problems?

[dhayden]

That's closer.

First, I suggest that you indent your code in BubbleSort to match the functional level of the statements.

The problem right now is that you're comparing/swapping using b and c as the index, but you don't reset them to zero inside the loop. My advice is to not use b & c at all. Instead, use i and i+1. The only trick is that i should go from the first item to the second-to-last one:

for (int i = 0; i < size-1; i++) {
    if (array[i] > array[i+1]) {
        ....
}

Once you get this working, consider an optimization: After the first pass through the loop, you're guaranteed that the largest item will have "bubbled up" to the last position. So the next time, you can actually go to size-2 instead of size-1. On the 3rd pass you can go to size-3 etc.

[GonlyG]

followed your advice.

#include <iostream>
#include <algorithm>
using namespace std;
   int* Bubblesort (int size, int array []){
       int swaps=0, passes = 0;
       bool swapped = true;
do {swapped = false;
            passes++;
            for (int i = 0; i < size-1; i++)
            {if (array[i] > array[i+1])
                { swap(array[i], array[i+1]);
                swaps++;
                swapped = true;
                 } 
            }
size--;} while (swapped == true);
                                                           } 

int GetArray (int array[], size_t array_size)
{
    int a = 0;
    while(a < 1 || a > array_size)
    {
       //number of elements in array
        cin >> a;
    }
    int i;
    for(i = 0; i < a; i++)
    {
        cin >> array[i];
    }
    return i;
}

int main()
{
     const size_t MAX_ARRAY = 1000;
    int array[MAX_ARRAY];
    size_t number_of_elements = GetArray(array, MAX_ARRAY);
    cout<< Bubblesort(number_of_elements, array); 
}

Although I still got the error "0x7ffe7944a430". What does that mean?

[jlb]

Please post the complete error message.

And note you can't print the result of your Bubblesort() call. You'll need to print each individual element. Also there is no need to return the array from the Bubblesort() function.

[dhayden]

First, I suggest that you indent your code in BubbleSort to match the functional level of the statements.

Do this and you may find that you aren't decrementing size where you should.

Next, I would creat a separate function to print out the array

Do this and then call it in main() after calling BubbleSort().

[GonlyG]

If I have no return, there is an error,"no return for non-void type function".
I'm not sure how to fix the following errors:

 In function 'int GetArray(int*, size_t)':
22:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 In function 'int PrintArray(int*, size_t)':
36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 In function 'int main()':
45:10: error: incompatible types in assignment of 'int*' to 'int [1000]'

my code:

#include <iostream>
#include <algorithm>
using namespace std;
   int* Bubblesort (int size, int array []){
       int swaps=0, passes = 0;
       bool swapped = true;
    do {swapped = false;
            passes++;
            for (int i = 0; i < size-1; i++)
            {if (array[i] > array[i+1])
                { swap(array[i], array[i+1]);
                swaps++;
                swapped = true;
                } 
            }
size--;} while (swapped == true);
           return 0;                       } 

int GetArray (int array[], size_t array_size)
{
    int a = 0;
    while(a < 1 || a > array_size)
    {
       //number of elements in array
        cin >> a;
    }
    int i;
    for(i = 0; i < a; i++)
    {
        cin >> array[i];
    }
    return i;
}

int PrintArray (int array[], size_t array_size){
    for (int i=0; i<array_size; i++){
        cout<<array[i];
    }
return 0;}
int main()
{
     const size_t MAX_ARRAY = 1000;
    int* array[MAX_ARRAY];
    size_t number_of_elements = GetArray(array, MAX_ARRAY);
    array= Bubblesort(number_of_elements, array); 
    cout<<PrintArray(array, number_of_elements);
}

[jlb]

If I have no return, there is an error,"no return for non-void type function".

If you don't need to return anything then use a void return type. In your latest program both Bubblesort() and PrintArray() could be defined as void functions:

void PrintArray(int array[], size_t array_size);

Also you shouldn't be trying to print the return value from PrintArray(), just call the function without the cout.

As for your warnings you should be using a size_t in your loops:

void PrintArray (int array[], size_t array_size)
{
    for (size_t i=0; i < array_size; i++)
   {
        cout << array[i];
   }
}

And please please start using a sane indentation style consistently.
https://en.wikipedia.org/wiki/Indent_style

[GonlyG]

Excellent. The bubblesort function works. Thanks for the help.

#include <iostream>
#include <algorithm>
using namespace std;
   void Bubblesort (int size, int array [])
{   int swaps=0, passes = 0;
       bool swapped = true;
    do {swapped = false;
            passes++;
            for (int i = 0; i < size-1; i++)
            {if (array[i] > array[i+1])
                {swap(array[i], array[i+1]);
                swaps++;
                swapped = true;
                } 
            }
size--;} while (swapped == true);
/*here I added cout<<passes<<" "<<swaps<<" "; which prints out passes, swaps, AND the array! yay! */
} 

int GetArray (int array[], size_t array_size)
{
    int a = 0;
    while(a < 1 || a > array_size)
    {
       //number of elements in array
        cin >> a;
    }
    int i;
    for(i = 0; i < a; i++)
    {
        cin >> array[i];
    }
    return i;
}

void PrintArray (int array[], size_t array_size)
{
    for (int i=0; i<array_size; i++)
    {
        cout<<array[i]<<" ";
    }
}
int main()
{
     const size_t MAX_ARRAY = 1000;
    int array[MAX_ARRAY];
    size_t number_of_elements = GetArray(array, MAX_ARRAY);
    Bubblesort(number_of_elements, array); 
    PrintArray(array, number_of_elements);
}

[GonlyG]

also, this function is SOOOOO much harder in c++ than in python XD

num_input = int(raw_input())
data = map(int, raw_input().split())
swaps, passes = 0, 0
swapped = True
while swapped == True:
    swapped = False
    for i in range(0, len(data) - 1):
        if data[i] > data[i+1]:
            data[i], data[i+1] = data[i+1], data[i]
            swaps += 1
            swapped = True
    passes += 1
print passes, swaps

[jlb]

Perhaps it is, but c++ does have std::sort that will easily sort the elements of your array. And also using a std::vector instead of the array will make things easier as well.

int main()
{
    const size_t MAX_ARRAY = 1000;
    int array[MAX_ARRAY];

    size_t number_of_elements = GetArray(array, MAX_ARRAY);

    std::sort(begin(array), begin(array) + number_of_elements);
    //Bubblesort(number_of_elements, array);

    PrintArray(array, number_of_elements);

    return 0;
}

[GonlyG]

perhaps.