1
$\begingroup$

I analized the bubble sort algorithm and I cannot see why they "implemented this way". I wrote down the results as the two loops performed their works and, with my small testing arrays, the outer loop condition to stop was always too much (the array was sorted when "i" was like 2, when the loop conditon to stop was 5.

this.bubbleSort = function(){
     var length = array.length; 

      for (var i=0; i<length; i++){ //this loop seems too much

         for (var j=0; j<length-1; j++ ){ 

            if (array[j] > array[j+1]){ 

               swap(array, j, j+1);
               }
             }
           }
        };

Is there a possibility that the outer loop will have to reach its limit? I mean the "i - 1 < length" will be necessary to sort. Is the array length on the outer loop really a precise choice or just a good choice, because it gives a clue of how many inner loop iterations will be needed with some leftover if necessary?

For me it means that the algorithm could be written, somehow, like this

var length = array.length; 

  for (var i=0; i< 10; i++){ //I used 10 instead of the array length

     for (var j=0; j<length-1; j++ ){ 

        if (array[j] > array[j+1]){ 

           swap(array, j, j+1);
           }
         }
       }
    };
$\endgroup$
  • $\begingroup$ If no swap is done in the inner loop, the outer loop can stop. (That's how I was taught bubble sort many years ago, too.) In fact, you can optimise further by using the index of the first swap as the start index of the next iteration. No matter what optimisations you find, bubblesort is quadratic and just about any other non-pathological sort algorithm is better. $\endgroup$ – rici May 16 '18 at 7:30
1
$\begingroup$

Let's assume that the input has is a reversed array like a = 5 4 3 2 1. every iteration of the outer loop all the 5 - 1 - i smallest elements will be shifted one cell to the right(i is zero in the first iteration) and the 5 - i th element will be moved to the 5 - i th cell. as one can see it takes 4 iteration to sort this.

at every iteration of the outer loop, the n - i th element will be moved to the n - i th cell so it will take at most n - 1 iteration and the worst case (descending array) will always take that many iteration ( the last element will be sorted by itself).

$\endgroup$
  • $\begingroup$ No, with an array with length 5 like this it only takes 4 outers loops. $\endgroup$ – Diego Alves May 15 '18 at 19:09
  • $\begingroup$ hmm right i messed up $\endgroup$ – Sobhan Mohammadpour May 15 '18 at 19:56
  • $\begingroup$ ok so i fixed the number and the reasoning $\endgroup$ – Sobhan Mohammadpour May 15 '18 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.