Thread: bubble sort

    #1
  1. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2002
    Posts
    421
    Rep Power
    12

    bubble sort


    I am getting into simple algorithms. I am starting with the bubble sort which was suggested by a friend. He ended up giving me the code to look at. Here is the code and the questions I have:

    #include <iostream.h>

    int main() {

    int array[] = {22, 23, 21, 20};
    int n = 4;
    for ( int i = 0; i < n-1; i++ ) { <--- Why n-1?
    for ( int j = 1; j < n-i; j++ ) { <--- n-i now?
    if ( array[j-1] > array[j] ) {
    int temp;
    temp = array[j-1]; <----Why did he make a temp array?
    array[j-1] = array[j];
    array[j] = temp;
    }

    }
    }

    for (int x = 0; x < 4; x++) {
    cout << array[x] << "\n";

    }

    cout << "\nThanks for using the bubble sort program!\n\n";
    return 0;

    }

    I do understand that after one cycle the highest number is at the end, so the n-1 tells the program it doesn't need to check the last number...but I think im missing something. Thanks in advance guys.

    -andy
    Last edited by andy3109; February 12th, 2003 at 03:36 PM.
    hmmm...
  2. #2
  3. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,643
    Rep Power
    4247
    Code:
    if ( array[j-1] > array[j] ) { 
    int temp; 
    temp = array[j-1]; <----Why did he make a temp array?
    array[j-1] = array[j];
    array[j] = temp;
    }
    He's not making a temp array. All he's doing is declaring a temp variable and using it to swap the values of two array elements. Let's say you have two variables a and b and want to swap the values. This is how you would do it:
    Assign the value of 'a' to a temp variable, say 'c'
    Assign the value of 'b' to 'a'
    Assign the value of 'c' to 'b'

    As for what the rest of it does, I'd suggest you study how the bubble sort algorithm works. Start with this article http://www.devarticles.com/art/1/76/2
    Note that the code that the author presents in that article is a bubble sort, but is less optimal than your friend's code (because it performs longer loops than is actually necessary). However, the concept of the bubble sort is explained pretty decently there. Hope this helps!
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Feb 2001
    Posts
    1,481
    Rep Power
    15
    andy,

    The temporary variable is required to swap values. You can't do this:

    int a=5
    int b=10;

    a=b;
    b=a;

    Do you see why? If you set a equal to b, then a equals 10(the 5 is overwritten), then if you set b equal to a, b will equal 10, which was it's original value. Somehow you have to save the value for a or else you will lose it. That's where the temporary variable comes into play.

    I admit those index values are not easy to follow, so a good programmer would explain them with comments. Otherwise, you need to read up on the algorithm used and go through the loop by hand recording values for all the variables to see what's happening. Generally speaking though, the outer loop(i loop) is going to be peformed 3 times(n-1=3) which means the code is going to traverse the array three times doing swaps, but each time through the array you don't have to perform as many swaps(n-i gets smaller).
    Last edited by 7stud; February 12th, 2003 at 04:36 PM.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Feb 2001
    Posts
    1,481
    Rep Power
    15
    That was a great link for explaining how the bubble sort works.

    I gathered from the article that since the largest value is moved to the end of the array the first time through the array, subsequent examinations don't need to look at the last element, and the next time through the array, the second largest number is second from the end, so the last two elements don't need to be examined subsequently, and so forth, hence the (n-i) in the inner loop of the code andy posted.
    Last edited by 7stud; February 12th, 2003 at 04:52 PM.
  8. #5
  9. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,643
    Rep Power
    4247
    Originally posted by 7stud
    I gathered from the article that since the largest value is moved to the end of the array the first time through the array, subsequent examinations don't need to look at the last element, and the next time through the array, the second largest number is second from the end, so the last two elements don't need to be examined subsequently, and so forth, hence the (n-i) in the inner loop of the code andy posted.
    Yep, that's exactly the optimization I was talking about. :)

IMN logo majestic logo threadwatch logo seochat tools logo