Selection Sort in Javascript

selection sort in javascript is of the sorting algorithm in Data structure and Algorithm Sorting by selection traverses the indexes of the array; For each index, the order of selection calls the index minimum and swap. In this post, we will explore users of selection sort and concrete examples of selection sort in debug mode.

How selection sort works

The above gif shows a selection sort in action. When you passed in a list [2,5,3,4,6,1] to selection sort, it returns a sort list [1,2,3,4,5,6].

pass in another list [3,1,2], it returns [1,2,3].

Selection sort has a space complexity of O(1) and time complexity of O(n ^2)

Where selection sort is used

  1. When the array to be sorted is relatively small
  2. When the array is NOT partially sorted
  3. When the array to be sorted is relatively small

Avoid using Selection sort when:

  1. The array is nearly sorted
  2. The array to be sorted has a large number of elements
  3. You want a faster run time and memory is not a concern.

Concrete example with Javascript code

I have a list of [3,1,2], I want this list to be sorted. Let me specify a written selection sort below

var list = [3,1,2]

selectionSort = function(array){
// the lgic goes here...
}

Next, I will loop over the array and declare a min index that will hold the index of my loop.

var list = [3,1,2]

selectionSort = function(array){
 for(var i = 0; i < array.length; i++){
 var min = i;
}
};

Next, will create another loop inside the first loop, which I will use it index to compare the min index. If the array [min] is greater than array[j], I will set the min index to j

var list = [3,1,2]

selectionSort = function(array){
 for(var i = 0; i < array.length; i++){
 var min = i;
   for(var j = i+1; j < array.length; j++){
      if(array[min] >  array[j] ){
        min = j;
      }
    }

}
};

If the second loop is complete, I want to do a swap. I will need a helper function for the swap.

var list = [3,1,2];

var swap = function(array, firstIndex, secondIndex){
    var temp = array[firstIndex];
    array[firstIndex]  = array[secondIndex];
    array[secondIndex] = temp;
};

selectionSort = function(array){
 for(var i = 0; i < array.length; i++){
 var min = i;
   for(var j = i+1; j < array.length; j++){
      if(array[min] >  array[j] ){
        min = j;
      }
    }
    swap(array, i, min);
}
};

Next, we want to return the array at the end of the first loop.

var list = [3,1,2];

var swap = function(array, firstIndex, secondIndex){
    var temp = array[firstIndex];
    array[firstIndex]  = array[secondIndex];
    array[secondIndex] = temp;
};

selectionSort = function(array){
 for(var i = 0; i < array.length; i++){
 var min = i;
   for(var j = i+1; j < array.length; j++){
      if(array[min] >  array[j] ){
        min = j;
      }
    }
    swap(array, i, min);
}
return array;
};

the full code is below.

var list = [3,1,2];

var swap = function(array, firstIndex, secondIndex){
    var temp = array[firstIndex];
    array[firstIndex]  = array[secondIndex];
    array[secondIndex] = temp;
};

selectionSort = function(array){
 for(var i = 0; i < array.length; i++){
 var min = i;
   for(var j = i+1; j < array.length; j++){
      if(array[min] >  array[j] ){
        min = j;
      }
    }
    swap(array, i, min);
}
return array;
};

console.log(list) // result = [1,2,3]

if you are still confused or want to know what is happening under the hood, run the code below in debug mode and step over each line of the process.


//HELPER FUNCTION
var swap = function(array, firstIndex, secondIndex){
    console.log('be swapped ', array)
    var temp = array[firstIndex];
    array[firstIndex]  = array[secondIndex];
    array[secondIndex] = temp;
    console.log('swapped ', array)
};



var selectionSort = function(array){
  for(var i = 0; i < array.length; i++){
      console.log('1st loop = ',i)
    //set min to the current iteration of i
    var min = i;
    for(var j = i+1; j < array.length; j++){
        console.log('2st loop = ',j)
        console.log('MIN ',min)
        console.log(array[min] +' compapare ', array[j] )
      if(array[min] >  array[j] ){
          console.log('change ', min + ' and '+ j);
        min = j;
        console.log('after ', min + ' and '+ j);
      }
    }
    swap(array, i, min);
  }
  return array;
};
var array = [3,1,2]

console.log(selectionSort(array))
If you are looking for more examples on selection sort, I urge you to look into this example.

swagasoft

Fully stack(MEAN) software engineer with over five years of experience participating in the complete product development lifecycle of successfully launched applications. Eager and willing to deliver mission- critical technology solutions.

View all posts by swagasoft →

Leave a Reply

Your email address will not be published. Required fields are marked *