One line of code I don't understand in the Bubble Sort

[357mag]

I'm making the Bubble Sort program and I think I understand most every line of code except one line. The inner for loop header I don't understand. The code is:

int[] numbers = { 3, 5, 2, 7, 1, 4 };
for (int i = 0; i < numbers.Length - 1; i++)
{
     for (int j = 0; j < numbers.Length - i - 1; j++)
     {
         if (numbers[j] > numbers[j + 1])
         {
             int temp = numbers[j];
             numbers[j] = numbers[j + 1];
             numbers[j + 1] = temp;

I don't understand the numbers.Length - i - 1 part. Maybe it controls the number of times you will have to swap values?

 

[357mag]

Maybe there is a better way to write this. Herb Schildt does it way different.

 

[Skydiver]

It will make a lot more sense if you actually simulate the code using pen and paper. (Alas, another skill that is often not taught in programming classes. Just like very few programming classes teach flowcharting it seems.)

Basically, what is happening is that by the time the first iteration of the outer loop happens, the last element of the array will have the highest value. E.g. The highest value has bubbled up. Hence the name of the sorting algorithm: Bubble Sort.

Since you know that the highest element of the array already has the highest value after the first iteration, there's no point comparing against it anymore an trying to swap into that slot. So the next iteration needs to stop at one less than the length of the array. So conveniently, at the second iteration, i is equal to 1. So numbers.Length - 1 is the last slot, e.g. numbers.Length - 0 - 1, then the second to the last slot is numbers.Length - 2 which is conveniently computed by numbers.Length - 1 - 1.

 

[Skydiver]

You could read and watch the animation in the Wikipedia article:

Bubble sort - Wikipedia

en.m.wikipedia.org

but true learning will kick in if you simulate with pen and paper.

The next best learning is stepping through the code with a debugger, but I still recommend the pen and paper simulation. Call me old school.

 

[Skydiver]

Maybe there is a better way to write this. Herb Schildt does it way different.

In the old Dream.In.Code forum, Herb Schildt's books were the least recommended programming books partly because of poor teaching approaches/techniques, and partly because of errors in his books. But we all cling to some of the books that were the breakthrough books in our learning process.

(I know some people swear by Knuth's data structures book even though there are better books for learning data structures. Knuth has the breadth, but not always the depth. He kind of just skimmed over how and things work, or leaves them as "exercises".)

Anyway, see: bullschildt

 

[357mag]

I found another code snippet that works but it's a little different. Looks like this:

for (int j = 0; j <= numArray.Length - 2; j++)
        {
            for (int i = 0; i <= numArray.Length - 2; i++)

 

[Skydiver]

In general, bubble sort is inefficient. That's an even less efficient way of doing bubble sort because you will be going over parts of the array that are already sorted.

Admittedly, when I was learning how to write code back when I was 9, that is how I wrote my bubble sort in BASIC: with a fixed loop end because I didn't know any better back then about efficiency.

 

[357mag]

Yes, but when you're just a hobbyist like I am, you don't concern yourself with things like that. You just want to understand things on a more basic level. I'm really a guitarist.

 

[Skydiver]

Think of it this way: You have 100 people in a line and you need to arrange them by age from youngest to oldest. You don't have a great memory, so you can't remember people's faces and their ages, so you need to ask everyone their age every time as you try to sort them out. You stand in front of the first person in line and ask them their age. You also ask the person behind them. If the first person is older than the second person, you tell them to swap places. You then move to the stand in front of the second person and ask them their age again, and ask the person third person their age. If the second person is older than the third person you ask them to swap places. You continue moving on down the line until you get to the second to the last person and do the same ask the age and swap places as needed. You then go back to the front of the line and do it all over again.

The code in post #6 will have you do this process through the entire line asking all 100 people. You'll end up asking 99x99x2=19,602 times. It's simple and guarantees you the result that you want at the cost of extra time.

The code in post #1 will have you get to the second to the last person the first time through the line. You'll end up with the oldest person at the end of the line. The next time through the line, you'll just get to the third to the last person in the line. This is because you know that the last person in line is the oldest, and so the current two people you are questioning can't possibly be older than the person at the back of the line. By the end of that questioning and possible swap you'll have the two oldest people at the end of the line. The next time through, you'll just get to the fourth to the last person in the line by induction. You'll need to go back to the start of the line 99 times. You'll end up asking 9,900 times. This is a bit more complex because you need to remember where you last ended, and you had to apply some initial analysis to guarantee that you get the results that you want.

As an extension of the problem, imagine that the people in the line have already arranged themselves by age before you started asking them. With the code in #6, you would still need to ask 19,602 times even if they are already sorted. Likewise with the code in #1, you would still need to ask 9,900 times. Wouldn't it be a good enhancement be to also keep track if ever two people swapped? If you didn't had to swap anybody, then that means that the entire line is already sorted. You could potentially just ask 198 times and be done! This is the version of bubble sort presented in Wikipedia.