Selection Sort

As the loop repeats over a collection, this algorithm finds and “chooses” the index with the lowest value and replaces it with the start index wherever appropriate.

The complexity of Space and Time

Best: O(n^2) time | O(1) space

Average: O(n^2) time | O(1) space

Worst: O(n^2) time | O(1) space

n is the length of the input array.

Input

[8, 5, 1, 9, 5, 6, 2]

Output

[1, 2, 5, 5, 6, 8, 9]

Hint

Split the input array into two subarrays. The first subarray must be sorted at all times, and it should begin with a length of zero, while the second subarray must be unsorted. In an unsorted array, find the smallest (or biggest) element and insert it into the sorted subarray with a swap method. Until the complete array is sorted, repeat these steps.

Pseudo Code

DEFINE FUNCTION selectionSort(array):
    SET currentIdx TO 0
    WHILE currentIdx < len(array) - 1:
        SET smallestIdx TO currentIdx
        FOR i IN range(currentIdx + 1, len(array)):
            IF array[smallestIdx] > array[i]:
                SET smallestIdx TO i
        swap(currentIdx, smallestIdx, array)
        currentIdx += 1
    RETURN array

Typescript Code

function selectionSort(array) {
  let startIdx = 0;
  while (startIdx < array.length - 1) {
    let smallestIdx = startIdx;
    for (let i = startIdx + 1; i < array.length; i++) {
      if (array[smallestIdx] > array[i]) smallestIdx = i;
    }
    swap(startIdx, smallestIdx, array);
    startIdx++;
  }
  return array;
}

function swap(i, j, array) {
  const temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}

mocha.setup("bdd");
describe("Selection Sort", () => {
  it("Test Case #1", function () {
    const input = [8, 5, 1, 9, 5, 6, 2];
    chai.expect(selectionSort(input)).to.deep.equal([1, 2, 5, 5, 6, 8, 9]);
  });

  it("Test Case #2", function () {
    const input = [5, 3, 1, 2, 4];
    chai.expect(selectionSort(input)).to.deep.equal([1, 2, 3, 4, 5]);
  });
});

mocha.run();

Demo

https://codepen.io/evalteam/pen/rNYNgBB