Bubble sort

[Violet_82]

Hi there,
I am trying to get my head around the bubble sort but I don't seem to get it.
Now I have a program written by somebody which performs a bubble sort and I am trying to understand it but no much success. Here is the code:

#include <iostream> //This is my teacher's and it works fine.
 #include <math.h>
 using namespace std;
 
 const int MAX = 10;
 void main()
 {
 	int i;
 	int Data[MAX]; //1D array to hold data
 	for (i=0; i<MAX; i++)
 	{
 		Data[i]=rand() % 101;
 		cout <<" " << Data[i] << "\n";
 	}
 
 
 //sort the data array using the bubble sort
 for (i=0; i < MAX; i++)
 for (i=1; i < MAX; ++i)
 	for (int j = MAX - 1; j >=i; --j)
 		if (Data[j-1] > Data[j])
 		{
 			int tmp = Data[j-1];
 			Data[j-1] = Data[j];
 			Data[j] = tmp;
 		}
 		for (i=0; i < MAX; i++)
 			cout << Data[i] << "--";
}

I am trying to replicate this on my program which I 've just started:

#include <iostream>
using namespace std;
const int MAX = 5;
int main ()
{
int Data[MAX] = {51,62,31,27,90};
...

but obviously I don't want to copy it, I want to understand it first and then apply it to mine.
I also had a look at wikipedia http://en.wikipedia.org/wiki/Bubble_sort where there is some pseudocode, which helped me a little bit but there are things like flag variables that I haven't covered as yet, so I am not sure how to use them...help please!
thanks

[Fbody]

A flag is nothing more than a variable that tells the program when an event has occurred or a condition has been met. There really isn't anything special about them.

Have a look at this for more info:
http://www.sorting-algorithms.com/bubble-sort

[syd919]

bubble sort works by comparing one element int the data to every other element, take for example the data in this array int array={3,2,6,5};, if you wanted to sort the data in ascending order using bubble sort you would compare 3 to 2 first and the push 2 to the front, so after the first pass your array would look like this ; int array={2,3,6,5}; ,you would continue this process until the data is sorted.

[Violet_82]

I think that what confuses me are the loops actually. Now, I had a look at the pseudocode on that website, but why do we need to use 2 variables n and j and not only one instead?
My understanding is that the pseudocode is telling me this:
do a for loop so that

for (n=0; i<MAX; ++i)
bool swap =false;
for (int j=0; j<i+1; ++j)
{
if a[j]<a[j-1]
{
a[j]=a[j-1];
}
}
swapped = true;
if (swapped=false) 
break;

But i think I don't understand the fuction of the loops...

[syd919]

bubble sort works by comparing one element in the data to every other element, take for example the data in this array

int array[]={3,2,6,5};

, if you wanted to sort the data in ascending order using bubble sort you would compare 3 to 2 first and the push 2 to the front, so after the first pass your array would look like this ;

int array[]={2,3,6,5};

,you would continue this process until the data is sorted.

[Violet_82]

that's fine, I understand the process, but what I don't understand is how to translate that into code and what functions the loops have in the process of ordering the numbers.

[Violet_82]

SO does it look like something like:

#include <iostream>
using namespace std;
const int MAX = 5;
void main ()
{
int i;
int Data[MAX] = {51,62,31,27,90};
for (i=0; i<MAX; i++)
bool swapped = false;
for (int j=0;j<i+1; ++j)
{
	if a[j]<a[j-1
	{
		a[j]=a[j-1];
	}
	swapped=true;

if (swapped=false) 
break;
}

}

[VernonDozier]

Your swap is incorrect. Swapping is done like this:

// Suppose x = 4 and y = 6 and x and y are to be swapped
int temp = x;
x = y;
y = temp;

At the end of the swap, x will equal 6 and y will equal 4. The variable temp is needed as a temporary variable (hence the name "temp"). Bubble Sort (and other sorts) use swapping a lot.

Line 16 needs to be INSIDE of an if statement. Bubble Sort stops when you go through ALL of the numbers and don't need to swap anything. Thus you have something like this:

bool swap = false;
do
{
     // code
    if (/* some condition */
    {
        // swap two numbers as explained above.
        // swap = true;
    }
    // code
}
while (swap);

[EDIT]
Thank God for 30 minute editing.

Correct pseudocode is above. Anyone who saw this post earlier would have been well justified to ding me.

[Fbody]

that's fine, I understand the process, but what I don't understand is how to translate that into code and what functions the loops have in the process of ordering the numbers.

You use 2 loops with 2 different indexes to mark your progress in the sorting algorithm.

The first/outer loop is roughly based on the number of elements to be sorted and keeps track of how many times you have traversed the data set. You must stop this loop at element (size-2) to prevent overrunning the boundaries of your data set. The current value of this loop's index determines the starting point of the inner loop. This allows you to reduce the range of the sort on each successive pass, effectively speeding it up as you progress farther through the set.

The second/inner loop does the actual comparisons and required swaps. The range of this loop is based on the current value of the index controlling the outer loop. Each time the loop starts, it performs one less iteration. This loop starts at (outerLoopIndex +1) and ends at (dataSetSize-1).

[Violet_82]

Thanks guys.
I have tried it in a slightly different way (using some of the code that I posted at the beginning, just to test it and then I will try with VernonDozier's code.)
But one thing at a time.

Now, here's what I came up with but I would like, if there is anybody patient enough, to go through it almost line by line:

#include <iostream>
using namespace std;
const int MAX = 10; //I use a constant to define the dimension of the array

int main()
{
	int i; //this will be one of the indexes of my array
	int j; //this will be then the second index of my array
	int Data[MAX] = {6,34,87,12,43,11,65,99,50,10};
	for (i=0;i<MAX;i++) /*This is just the loop used to print all the values of my array isn't it?*/
		{
		cout <<Data[i]<<" - ";
		}
	for (i=0; i<MAX; i++)/*sort starts. What's the purpose of this loop? I tried to remove it from the code and the program doesn't work but I don't quite understand what it does */
	for (j=MAX-1;j>=i;--j)/*Why do we need a second loop with a second index and why is it --j and not j--?*/
		if (Data[j-1]>Data[j]) //These lines
			{ //are 
			int temp = Data[j-1]; //all
			Data[j-1] = Data[j]; //clear, it is
			Data[j] = temp; //probably the only thing I really
			} //understood in this program!
	for (i=0;i<MAX;i++) /*This loop is just for printing the values 
of the array after the swap has happened*/
		cout <<" "<<Data[i];




	return 0;
}

One of the main things that has bugged me about array is this: what does it exactly mean when I say something like

Data[i]

? "i" is the index isn't it? But does it have a specific value or does it represent all the elements in the array?
Sorry but arrays really confuse me...I hope I will be able to understand them properly soon!
thanks

[VernonDozier]

We don't normally give out full programs, but I think it's fine here. It's just a bubble sort and you've shown effort. Here is an implementation of the Bubble Sort. You can see the program and you can see the different iterations and you can see how it works under three different variations:

#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;

void Display (int array[], int size)
{
    for (int i = 0; i < size; i++)
        cout << array[i] << '\t';

    cout << endl;
}


int main ()
{
    const int SIZE  = 10;
    srand (time (0));
    int array[SIZE];

    cout << "1. Forwards\n";
    cout << "2. Backwards\n";
    cout << "3. Random\n";
    cout << "Enter 1 - 3 : ";
    int option;
    cin >> option;

    switch (option)
    {
         case 1:
                for (int i = 0; i < SIZE; i++)
                    array[i] = i;
                break;
         case 2:
                for (int i = 0; i < SIZE; i++)
                    array[i] = SIZE - i;
                break;
         case 3:
                for (int i = 0; i < SIZE; i++)
                    array[i] = rand () % SIZE;
                break;
    }

    cout << "Pre-sort          : ";
    Display (array, SIZE);

    bool atLeastOneSwap = true;  // initialize to true so that we enter the for loop.
    for (int i = 0; i < SIZE - 1 && atLeastOneSwap; i++)
    {
        atLeastOneSwap = false;
        for (int j = SIZE - 1; j > i; j--)
        {
            if (array[j-1] > array[j])
            {
                int temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                atLeastOneSwap = true;
            }
        }

        cout << "After iteration " << i << " : "; 
        Display (array, SIZE);
    }

    cout << "sorted            : ";
    Display (array, SIZE);

    return 0;
}

[VernonDozier]

One of the main things that has bugged me about array is this: what does it exactly mean when I say something like

Data[i]

? "i" is the index isn't it? But does it have a specific value or does it represent all the elements in the array?
Sorry but arrays really confuse me...I hope I will be able to understand them properly soon!
thanks

Data[i] means different things depending on how it is used:

int Data[10];  // declaration : 10 is the size,here, not an index.  Declare and set aside storage for 10 integers.
Data[5] = 7; // assignment : 5 is the index here.  Legal indexes are 0 through 9.  Make the fifth element (remember that indexes start at 0, not 1) of the Data array equal to 7.
cout << Data[5]; // access : display the value of the fifth element of the Data array to the screen.

If there is a type (i.e. int) in front of Data, the number in the brackets is the size of the array. If not, it is the index.

int Data[10]; // 10 is the size.
Data[5] = 7; // 5 is the index.
cout << Data[5]; // 5 is the index

[Violet_82]

Thank you VernonDozier, I can ensure you that I always try hard myself before asking anything on the forum, the reason being that I want to learn how to program.
Thanks for posting the code, I had a look at it and I don't think I could have done on my own though, because there are still lots of things I don't know, like your directives

#include <ctime>
#include <cmath>

(never seen them before) and like boolean variables just to name some of them.

Thanks also for the clarification on the array, it's better now :)

[Sky Diploma]

interesting question.

Array: An array is kinda like a collection of variables of the same data type. Each variable that is pointed out by an index value.

Creation of an array:

Consider the following code:

int arr[10];

Here we declare/define an array of '10' integer elements. of which all can be accessed by the variable name "arr".

This is the basics of array declarations.

Now lets see on how to access elements of an array.

We first looked at how '' with the size in them created an array.
The same operator can be used to access variables.

The basic, but important point to remember is .
For any array of 'n' elements.
The range of its elements . starts from '0' and ends at 'n-1'

For example.. in our array of 10 elements. we have individual variables like,

arr[0],arr[1],arr[2]...arr[9]

So if i wish to access the 5th element of the array "arr" i can do it by :

arr[4] = 100;

Its simply to mean.. that while accessing elements of the array, the indexing of the elements starts from '0'.. and the last element is actually accessed by using "last-1" in the square braces.
------------------------------------------------------------
That is the basics of arrays . Hope this post helped you
------------------------------------------------------------------------
EDIT
I am sorry.... I didn't check the total threads properly.. but started to answer upon it.

[jonsca]

Thank you VernonDozier, I can ensure you that I always try hard myself before asking anything on the forum, the reason being that I want to learn how to program.
Thanks for posting the code, I had a look at it and I don't think I could have done on my own though, because there are still lots of things I don't know, like your directives

#include <ctime>
#include <cmath>

(never seen them before) and like boolean variables just to name some of them.

Thanks also for the clarification on the array, it's better now :)

ctime is the version of the C header time.h meant to be used in C++ code
cmath is that of math.h
(there is cstdlib for stdlib.h, etc., etc.)

[Violet_82]

thanks guys :)