Learn Selection Sort


const swap = (arr, xp, yp) => {
  let temp = arr[xp];
  arr[xp] = arr[yp];
  arr[yp] = temp;
};

export const selectionSort = (arr = []) => {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    let minIndex = i;
    // let minString = arr[i];
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        // minString = arr[j];
        minIndex = j;
      }
    }
    // Swapping the minimum element
    // found with the first element.
    if (minIndex !== i) {
      swap(arr, minIndex, i);
    }
  }
  return arr;
};

export const selectionSortString = (arr = []) => {
  const n = arr.length;
  for (let i = 0; i < n; i++) {
    let minIndex = i;
    let minString = arr[i];
    for (let j = i + 1; j < n; j++) {
      if (arr[j].localeCompare(minString) === -1) {
        minString = arr[j];
        minIndex = j;
      }
    }
    // Swapping the minimum element
    // found with the first element.
    if (minIndex !== i) {
      swap(arr, minIndex, i);
    }
  }
  return arr;
};


export const selectionSortStable = (arr = []) => {
  const n = arr.length;
  // O(n)
  for (let i = 0; i < n; i++) {
    let minIndex = i;
    // O(n)
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // My way
    // Splicing minimum element
    // found with the first element.
    if (minIndex !== i) {
      
      let temp = arr[minIndex];
      arr.splice(i, 0, temp);
      arr.splice(minIndex + 1, 1);
      console.log('add: ', arr);
      console.log('remove: ', arr);
    }
    /**
     * gfg way https://www.geeksforgeeks.org/stable-selection-sort/
     * // Move minimum element at current i.
      let key = a[min];
      while (min > i)
      {
          a[min] = a[min - 1];
          min--;
      }
          
      a[i] = key;
     */
  }
  // Time complexity O(n) + O(n) = O(n^2);
  return arr;
};

Complexity Analysis of Selection Sort:

Time Complexity: O(N²) as there are two nested loops:

One loop to select an element of Array one by one = O(N)
Another loop to compare that element with every other Array element = O(N)
Therefore overall complexity = O(N)*O(N) = O(N*N) = O(N²)

Auxillary Space: O(1) as the only extra memory used is for temp variable while swapping two values in array. The good thing about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.

Selection String Sort

Try it out
Results:

Selection Number Sort

Try it out
Results:

Back to Learn