Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why do we use `length-i-1` in the inner loop of bubble sort algorithm

Using javascript, It's programmed to sort the elements in an array by asc order. I tried my best to understand why the inner loop uses length-i-1, but couldn't. Can anyone please help me understand why do we use it?

function bubbleSort(arr) {

    for(let i=0; i<= arr.length; i++) {
        for(let j=0; j< arr.length-i-1; j++) {
            if(arr[j] > arr[j+1]) {
                let lesser = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = lesser;
            }
        }
    }

    return arr;
}
like image 209
Prem Avatar asked Dec 17 '22 22:12

Prem


1 Answers

Like Daniel said in his comment, it is because those items have already been sorted (eg. the largest element that ends up at the highest index in the first iteration)

Watch the gif below, notice how the 8 ends up on the far right, and then gets surrounded by the black box, signifying that it will not need to be moved anymore, and therefor doesn't need to be checked anymore (it is greater than length-i-1).

Bubble Sort in action

Not checking these already 'locked in' elements helps to increase the algorithm speed.

Gif is from: Bubble Sort on Wikipedia

like image 177
tehp Avatar answered Dec 20 '22 12:12

tehp