Thread: Bubble sort confusion

  1. #1
    Registered User
    Join Date
    Jul 2010
    Posts
    2

    Bubble sort confusion

    I am working through Herbert Schildt's beginners C++ and I can't get my head around an element of the bubble sort. In the fragment:

    Code:
    // 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;
    				}
    			}
    The two for statements seem to indicate that "a" will count up and continue until it reaches constant "size" while "b" will count down through the array until it's value is equal to "a". Given that "a" is counting up and that "b" is counting down, it seems to me that the two will meet in the middle.

    I can't get my head around how, with this, any of the array below that point will be sorted.

    I would appreciate it if someone would be able to explain it in simple terms.

    Thanks!

  2. #2
    Registered User
    Join Date
    Feb 2009
    Posts
    329
    Quote Originally Posted by Cpt_Tangerine View Post
    I am working through Herbert Schildt's beginners C++ and I can't get my head around an element of the bubble sort. In the fragment:

    Code:
    // 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;
    				}
    			}
    The two for statements seem to indicate that "a" will count up and continue until it reaches constant "size" while "b" will count down through the array until it's value is equal to "a". Given that "a" is counting up and that "b" is counting down, it seems to me that the two will meet in the middle.

    I can't get my head around how, with this, any of the array below that point will be sorted.

    I would appreciate it if someone would be able to explain it in simple terms.

    Thanks!
    For each single iteration of the outer loop, the inner loop will run completely. So when a = 1, the inner loop will run from b=size-1 down to 1. Then when thats complete, the outer loop will increment a to 2 and then the inner loop will run from b=size-1 down to 2, etc. it doesnt work by the outer loop and inner loop taking individual turns.

  3. #3
    Registered User
    Join Date
    Jul 2010
    Posts
    2
    Fantastic!

    Thanks for that. I was somewhat confused by the fact that there are no brackets from the 1st for to the 2nd and I was thinking because of that that each time the block below the 2nd for completed that it would go back to the very beginning.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 05-13-2009, 03:25 PM
  2. help with debug (bubble sort algorithm)
    By lbraglia in forum C Programming
    Replies: 5
    Last Post: 10-19-2007, 05:24 PM
  3. Bubble Sort... which type?
    By gflores in forum C++ Programming
    Replies: 8
    Last Post: 08-15-2004, 04:48 AM
  4. Bubble Sort, Qucik Sort
    By insomniak in forum C Programming
    Replies: 2
    Last Post: 03-15-2003, 04:54 PM
  5. optimizing bubble sort
    By Sargnagel in forum C Programming
    Replies: 14
    Last Post: 01-23-2003, 06:27 AM