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

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!

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).

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.

Yep, that's exactly the optimization I was talking about.