Recursive Selection Sort

recusive-selection-sort.js

// Implement Selection Sort
// The algorithm divides the input list into two parts:
// - a sorted sublist of items which is built up from left to right at the front (left) of the list
// - a sublist of the remaining unsorted items that occupy the rest of the list.
// Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.
// The algorithm proceeds by:
// - finding the smallest element in the unsorted sublist
// - exchanging (swapping) it with the leftmost unsorted element
// - moving the sublist boundaries one element to the right.
// Read more: https://en.wikipedia.org/wiki/Selection_sort

// Note: you can assume the inputs are always positive integers (3, 7, 34)
function findMinimumIndex(
  list: number[],
  currentIndex = 0,
  minIndex = 0
): number {
  if (list[minIndex] > list[currentIndex]) {
    minIndex = currentIndex;
  }
  if (currentIndex < list.length - 1) {
    return findMinimumIndex(list, currentIndex + 1, minIndex);
  } else {
    return minIndex;
  }
}

function selectionSort(inputList: number[], startIndex = 0): number[] {
  if (inputList.length == 0) return [];

  // find minimum
  const minimumIndex = findMinimumIndex(inputList, startIndex, startIndex);

  if (inputList[minimumIndex] < inputList[startIndex]) {
    // swap
    const tempStorage = inputList[startIndex];
    inputList[startIndex] = inputList[minimumIndex];
    inputList[minimumIndex] = tempStorage;
  }

  // recursion finished
  if (startIndex > inputList.length - 1) return inputList;

  // call on the rest
  return selectionSort(inputList, startIndex + 1);
}

export default selectionSort;