This is the 15th day of my participation in Gwen Challenge

What is selection sort

We’ve already seen the simplest sort algorithm, bubble sort, but one of the biggest problems with bubble sort is that it swaps elements too many times.

Consider this scenario:

In PE class, students are asked to line up in order of height, from short to tall.

So let’s say you have these five students, and the first student is the tallest, and he has to sort to the end, and if you use bubble sort, the first student gets to the last place, and you switch four times, and that’s just the first round of bubble sort.

Suppose we switch to the selection sort example, where we find the shortest student in each round and send him directly to the front of the queue, so that the sorting can be done in a very small number of switches.

The biggest advantage of selective sort is that it saves the exchange of redundant elements. It is a sort of address-comparison algorithm.

The general idea of selection sort is to find the smallest value in the data structure and place it first, then find the second-smallest value and place it second, and so on.

Graphic algorithm

  • Suppose we have a set of numbers and we want to sort them.

  • Linearly search all numbers to find the smallest number in the set.

  • Swap the minimum found to the top of the number to be sorted. (At this point, the first item of the sequence has been sorted, and the number not to be sorted should be ignored in the future)

  • Repeat the same operation, this time we find the minimum of the number to be sorted — the number 2.

  • Swap the minimum value found, the number 2, to the top of the number to be sorted. (The number 1 is already sorted, so it will be ignored, and the number 2 will be ignored as well.)

  • Repeat the same operation, this time we find the smallest number among the numbers to be sorted — the number 3.

  • Swap the smallest value found, the number 3, to the top of the number to be sorted. (The numbers 1 and 2 are sorted so they are ignored, and the number 3 needs to be ignored as well.)

  • Repeat the same operation until all numbers are sorted.

Code implementation

// A constant object for comparison (to keep code elegant)
export const Compare = {
  LESS_THAN: -1.// If the first element is less than the second, it returns -1
  BIGGER_THAN: 1.If the first element is greater than the second, it returns 1
  EQUALS: 0 // If the element has the same reference, it returns 0
};
// Compare the methods used
export function defaultCompare(a, b) {
  // If the element has the same reference, it returns 0
  if (a === b) {
    return Compare.EQUALS;
  }
  // If the first element is less than the second, it returns -1, otherwise it returns 1
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
/** * swap function *@param {*} Array passes in the array to swap (in this case the heap) *@param {*} A passes in the node a * to be swapped@param {*} B passes in the node b */ to be swapped
export function swap(array, a, b) {
  // ES5
  /* const temp = array[a]; // To swap two values in an array, we need an auxiliary variable to copy the first element to swap array[a] = array[b]; // Then assign the second element to the position of the first element array[b] = temp; * / // Finally, the copied value of the first element is overwritten to the position of the second element
  / / ES6 writing (poorly) https://bugzilla.mozilla.org/show_bug.cgi?id=1177319
  [array[a], array[b]] = [array[b], array[a]];
}
/** * Select sort * The algorithm that repeats the smallest value in the data to be sorted and swaps it with the leftmost number in the sequence is selective sort. *@param {array} Array Array to be sorted *@param {function} CompareFn // Compare with defaultCompare * by default@returns {array} Returns the sorted array */
 export const selectionSort = (array, compareFn = defaultCompare) = > {
   const { length } = array; // Declare a variable named length to store the length of the array
   // Declare a variable to store the location of the smallest element
  let indexMin;
  for (let i = 0; i < length - 1; i++) { // Loop through the array and control the number of iterations in the array
    indexMin = i; // The first value of the initial iteration is the minimum value of the array
    // console.log('index ' + array[i]);
    for (let j = i; j < length; j++) { // Loop from the current value of I to the end of the array
      if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) { // We compare whether the value of position j is smaller than the current minimum value
        // console.log('new index min ' + array[j]);
        indexMin = j; // If so, change the minimum to the new minimum}}if(i ! == indexMin) {// If the minimum is different from the original minimum (I stores the original minimum, indexMin stores the new minimum)
      // console.log('swap ' + array[i] + ' with ' + array[indexMin]);
      swap(array, i, indexMin); // The value is swapped}}// Returns the sorted array
  return array;
};
Copy the code