JavaScript Selection Sort

Posted on: 2017-06-28

The selection sort is a very primitive sort that has two loops. They are both imbricated which cause an asymptotic analysis of the upper bound to be O(n^2). The selection sort loops a first time all elements except the last one of the array which allow to evaluate every data. The second loop, is there to find the smallest value after the first loop and swap any smallest value if one found.

The idea is : find the smallest one, put it at the beginning.

function swap(array, left, right) {
  var temp = array[left];
  array[left] = array[right];
  array[right] = temp;
}
function selectionSort(arrayToSort) {
  var length = arrayToSort.length;
  var minIndex = -1;
  for (var i = 0; i < length - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < length; j++) {
      if (arrayToSort[j] < arrayToSort[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      swap(arrayToSort, minIndex, i);
    }
  }
}