ROBOT.LK

Posted: **Wed Nov 09, 2011 9:46 am**

Can anyone help me to understand Bubble sort in Java. Here is the code from Java a Beginner's Guide book.

I understand some. But I mostly don't understand how this code works. (I mean how this is sorting). I used Google to find out more info about Bubble sort and have an understanding how it works.
What I mostly don't understand is the code below this comment.

Code: Select all

// This is the Bubble sort.

I would really happy if some one can explain me this code line by line.

Code: Select all

/*
Project 5-1
Demonstrate the Bubble sort.
*/

class Bubble {
public static void main(String args[]) {

	int nums[] = { 99, -10, 100123, 18, -978,
					5623, 463, -9, 287, 49 };
	int a, b, t;
	int size;
	size = 10; // number of elements to sort
	
// display original array
	System.out.print("Original array is:");
	for(int i=0; i < size; i++)
		System.out.print(" " + nums[i]);
		System.out.println();
		
// This is the Bubble sort.
	for(a=1; a < size; a++)
	for(b=size-1; b >= a; b–-) {
		if(nums[b-1] > nums[b]) { // if out of order
			// exchange elements
			t = nums[b-1];
			nums[b-1] = nums[b];
			nums[b] = t;
			}
		}
// display sorted array
	System.out.print("Sorted array is:");
	for(int i=0; i < size; i++)
		System.out.print(" " + nums[i]);
		System.out.println();
	}
}

Thank you very much.

Posted: **Thu Nov 10, 2011 8:10 am**

Nipuna man,
if you can't understand the code by just reviewing , then take the pencil and paper and
do a dry run.

do you know how to do a dry run?

Posted: **Thu Nov 10, 2011 12:20 pm**

No man.
Thanks for the advice but I don't know how to Dry Run.

Posted: **Fri Nov 11, 2011 10:54 am**

Hi Nipuna,

The whole logic is here. I have added a parenthesis to the first 'for' loop for better understanding.

Code: Select all

for(a=1; a < size; a++){
	for(b=size-1; b >= a; b–-) {
		if(nums[b-1] > nums[b]) { // if out of order
			// exchange elements
			t = nums[b-1];
			nums[b-1] = nums[b];
			nums[b] = t;
		}
	}
}

Okay... The first 'for' loop runs from 1 to (size - 1). That is, say you have 10 elements. The loop runs from 1 to 9. That is 1 less the total number of elements.

Now consider the second 'for' loop. It runs from (size - 1) to 'a' (the value given by first 'for' loop). For example, say the first 'for' loop runs 5 times, then the values of 'a' is 5. Then the second 'for' loop runs from 9 to 5 (5 times). Botice that second 'for' loop runs in decreasing order where as the first one on increasing.

Okay... Now let's see what is happening. As Sandun stated, we will have to write the values on a piece of paper for each iteration.
I'll run the first one. I'll assume there are 10 elements so 'size' = 10.

First 'for' loop runs from 1 to 9:
a = 1
Second 'for' loop runs from 9 to 1:

b = 9
if (nums[8] > nums[9]) { <- here we check the last element with one before the last element
// last element is lower than one before the last one -> we need to swap element 8 with 9
t = nums[8];
nums[8] = nums[9];
nums[9] = t;
}

b = 8
if (nums[7] > nums[8]) {
// 8th element is lower than7th one -> we need to swap element 7 with 8
t = nums[7];
nums[7] = nums[8];
nums[8] = t;
}
...........

...........

...........

b = 1
if (nums[0] > nums[1]) {
// second element is lower than first one -> swap them
t = nums[0];
nums[0] = nums[1];
nums[1] = t;
}

First iteration of 1st loop done. Now 'a' become 2
a = 2
b goes from 9 to 2

On the 3rd iteration
a = 3
b goes from 9 to 3

......

......

......

On the last iteration of first loop,
a = 9
b goes from 9 to 9 (So will run only 1 time to check 8th element with 9th one)

So the simple logic here is to get the lowest element to top on the first run second loop.
On the second run of second loop, it takes the 2nd highest element to 2nd position of the array.
.....
.....
Likewise on the last run it adjusts the last two elements on the array by taking the lowest one to top.

So the lowest element comes up just as a bubble in water.

Hope you have a better idea now.

Posted: **Fri Nov 11, 2011 5:38 pm**

I'll slowly read your reply Neo then try to understand

Thanks

ROBOT.LK

Help me to understand Bubble sort in Java. Anyone???

Help me to understand Bubble sort in Java. Anyone???

Re: Help me to understand Bubble sort in Java. Anyone???

Re: Help me to understand Bubble sort in Java. Anyone???

Re: Help me to understand Bubble sort in Java. Anyone???

Re: Help me to understand Bubble sort in Java. Anyone???