0

I'm writing a bubble sort program for fun but what i don't understand is the line j<len-i does in this code?

i can just remove -i from the above line it will also work,

var arr=[3,5,4,7,8,9,30,0,-1];
function bubble_Sort(arr){

var len = arr.length,
    i, j, stop;

for (i=0; i < len; i++){
    for (j=0; j<len-i;  j++){
        if (arr[j] > arr[j+1]){
            var temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;

        }
    }
}

return arr;
}
console.log(bubble_Sort(arr));


//with -i in second for loop
var arr=[3,5,4,7,8,9,30,0,-1];
function bubble_Sort(arr){

    var len = arr.length,
        i, j, stop;

    for (i=0; i < len; i++){
        for (j=0; j<len-i;  j++){
            if (arr[j] > arr[j+1]){
                var temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
                
            }
        }
    }

    return arr;
}
console.log(bubble_Sort(arr));

Without -i in second loop

Improve this question
7
  • Where you removed i? Commented Mar 12, 2019 at 6:53
  • 1
    U can remove i from j<len-i Commented Mar 12, 2019 at 6:54
  • If you will keep -i then iteration will be low because you have already sorted the elements. If you remove then it will do unwanted operation with sorted elements. You should keep -i Commented Mar 12, 2019 at 6:57
  • Suppose your array have 5 elements then first time you will sort one element. So now You have to do operation for 4 elements, then 3 then 2 then 1 Commented Mar 12, 2019 at 6:58
  • -i stops unwanted loop iterations thats it :) Commented Mar 12, 2019 at 6:59

4 Answers 4

Reset to default
2

You can see why that work, if you log the arr for every "i" loop.

var arr=[3,5,4,7,8,9,30,0,-1];
function bubble_Sort(arr){

var len = arr.length,
    i, j, stop;

for (i=0; i < len; i++){
    for (j=0; j<len-i;  j++){
        if (arr[j] > arr[j+1]){
            var temp=arr[j];
            arr[j]=arr[j+1];
            arr[j+1]=temp;

        }
    }
    console.log(arr)
}

return arr;
}
console.log(bubble_Sort(arr));

(9) [3, 4, 5, 7, 8, 9, 0, -1, 30]

(9) [3, 4, 5, 7, 8, 0, -1, 9, 30]

(9) [3, 4, 5, 7, 0, -1, 8, 9, 30]

(9) [3, 4, 5, 0, -1, 7, 8, 9, 30]

(9) [3, 4, 0, -1, 5, 7, 8, 9, 30]

(9) [3, 0, -1, 4, 5, 7, 8, 9, 30]

(9) [0, -1, 3, 4, 5, 7, 8, 9, 30]

(9) [-1, 0, 3, 4, 5, 7, 8, 9, 30]

(9) [-1, 0, 3, 4, 5, 7, 8, 9, 30]

(9) [-1, 0, 3, 4, 5, 7, 8, 9, 30]

every i loop, it moves the ith large number to bottom, so the last i number is stable.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I don't get it.
@NewBie_WannaBe it will show 10 iterations of the outer loop, but ur inner loop will stop running once sorted.
when i use -i i get ten console.log lines(iterations) and same goes for when i remove -i too
ah, it just display the whole arr, actually, the bubbles of the loop is 10, 9, 8, 7...1
1

Consider the array (to be sorted in increasing order):

[4, 3, 2, 1]

After running your inner loop with i = 0 you will get:

[3, 2, 1, 4]

Now, i=1...

Repeating the process again, at your next iteration when i=1 you will get:

[2, 1, 3, 4]

Now, i=2

Again, repeating the loop again at i=2 you get:

[1, 2, 3, 4]

Now i=3

Notice how the bold numbers are already in sorted order.

Here we have a loop invariant for the outer loop (ie a statement which holds true for each iteration of the outer loop), which is that the last i items of the array is in sorted order. Or, another way to look at it is that all items in the array from [0, ... length-i) are not sorted, and thus items from index length-i and onwards are in sorted order.

In other words, when you look at your array, you can see that after each iteration of the outer loop, the array all items from length-i, ..., length are in sorted order, and thus there is no need to re-sort/re-check them.

So, providing the len-i prevents you from rechecking the items already in sorted order, as you know they won't need to change.

Improve this answer

Comments

1

This is because every time the last element gets sorted. After every iteration, you will find that the last element is in the correct place (for 0th iteration - the last element is in correct position, for 1st iteration - last 2 elements are in correct position and so on). So every time we loop through len - i elements.

Improve this answer

Comments

1

The minus i is whats going to account for the fact that after you do a full iteration through your array the first time, the right most element will be in the correct location. So you don’t have to try to re-sort that again in the future. This is why yoy have the minus i on there.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.