preface

Reading “learning JavaScript data structure and algorithm (3rd edition)” have a feeling that I hope every time learning algorithm can output a blog, income column, check their own learning situation ~ article has a mistake welcome various big god correction, don’t spray, if you want to spray, trouble light, thank you ~

start

Selection sort algorithm is a kind of address comparison sort algorithm. He solved the problem of too many bubble exchanges

When you compare adjacent elements in bubble sort, you swap them O(N^2) times

In selection sort, you’re only looking for the minimum and you’re only swapping with the original address O(N) times.

Train of thought

Such as an array,4,3,2,1 [5]

  • As can be seen from the figure above, the general idea of selection sort is to find the minimum value in the data structure through a loop and swap it with the first place.
  • Then the second round finds the second smallest value and swaps it with the second, and so on.
  • The outer loop only has to go through n minus 1 times, because the last time, of course, there’s one element left, and I don’t have to do anything with it, so the outer loop just has to usearray.length - 1

implementation

function selectSort(array) {
  var sum = 0.// Count the number of loops
    minIndex = 0; // Minimum index
  for (var i = 0; i < array.length - 1; i++) {
    minIndex = i;
    for (let j = i; j < array.length; j++) {
      sum += 1
      if (array[minIndex] > array[j]) {
        minIndex = j
      }
    }
    if(i ! = minIndex) [array[minIndex], array[i]] = [array[i], array[minIndex]]; }console.log('sum: ', sum); / / 14
  return array;
}
var arr = [5.4.3.2.1];
console.info(selectSort(arr));
Copy the code

To optimize the

JavaScript code above is taken from the learning data structure and algorithm (3rd edition) “, it will be altogether cycle sum = 14 times, inner loop here j = I, there is a process of themselves and their comparison, there is no need to compare this layer, the comparison of each time should be and the current position of the next comparison, the optimized circulation 10 times

function selectSort(array) {
  var sum = 0.// Count the number of loops
    minIndex = 0; // Minimum index
  for (var i = 0; i < array.length - 1; i++) {
    minIndex = i;
    for (let j = i + 1; j < array.length; j++) { // TODO optimization changes j= I to j= I +1
      sum += 1
      if (array[minIndex] > array[j]) minIndex = j
    }
    if(i ! = minIndex) [array[minIndex], array[i]] = [array[i], array[minIndex]]; }console.log('sum: ', sum); / / 10
  return array;
}
var arr = [5.4.3.2.1];
console.info(selectSort(arr)); // [1, 2, 3, 4, 5]
Copy the code

Time complexity

Selection sorting is also an O(n ^ 2) algorithm. Like bubble sort, it contains two nested loops, which leads to quadratic complexity. For the analysis of complexity, see # Front-end Algorithm Learning – Algorithm complexity

other

# Front-end algorithm learning – Algorithm complexity # Front-end must algorithm (I) : bubble sort

The last

Dregs a, welcome all great god many correction, not praise, just supervision correction