CODEWITHSUNDEEP
java
Lifter
Lifter

Reputation: 77

Outer loop in Bubble Sort Algorithm

I've been searching on google, and couldn't find a a similar question or explanation.

Assume the following code:

int out, in;
for(out=nElems-1; out>1; out--)
    for(in=0; in<out; in++) {
        if( a[in] > a[in+1] )
            swap(in, in+1);
    }

Why does the outer loop stops when after the outer value reaches 1? Isn't it supposed to have 2 elements left? The 0 and 1 places? What makes us so sure that they are already sorted?

I understand how the Algorithm work, and realise there would be a better solution with a flag that stops if no iteration are done, but I'm really interested in understanding the above code.

Upvotes: 2

Views: 653

Answers (2)

3yakuya
3yakuya

Reputation: 2672

When out reaches 2, the inner loop goes from 0 to 1. It makes sure the two elements at [0] and [1] are in the correct order - this is the time to stop bubble sorting. However, the code you presented above will then compare [1] and [2] - resulting in a potential swap leading to unsorted array (as [0] and [1] should be compared again, after [1] and [2] are compared). For this code to work, the outer loop should go downto 1 inclusive, so for (out = nElems - 1; out > 0; out--).

What you need to see here is the fact, that in bubble sort the inner loop is doing the actual job of sorting (by swapping the elements). The outer loop is just setting the limit beyond which all elements are already sorted.

Upvotes: 1

Kyborek
Kyborek

Reputation: 1511

So, i am afraid the book code doesn't work, let's prove it by example:

Array ={3,2,1};//nvm the syntax, i assume pseudocode because we don't even know what is swap()
nElems=3;
For: out=2;
 For:in=0
  check 0 and 1
  Array={2,3,1}
 in=1
  check 1 and 2
  Array={2,1,3}
 in=2, break;
out=1, break;

You can see the flow ended with array {2,1,3} which is not sorted. So even books may have errors, or maybe if you read few pages ahead you might find out it was intentional. Correct bubble sort would have condition out>=1 or out>0

EDIT: with array consisting of 2 elements, the algorithm will do nothing, even simplier proof

Array ={2,1};
nElems=2;
For: out=1, break;//out = nElems-1, 1>1 is false

Upvotes: 4

Related Questions