[Elementary Sorting Algotithms] Selection sort

Smiliar to bubble sort, but instead of first placing large values into sorted position, it places small values into sorted position.

 

처음것과 그 다음 배열을 차례대로 비교해서 최소의 수를 '맨 마지막에' 앞으로 옮김, 그 후 반복

[5, 3, 4, 1, 2]

[5, 3, 4, 1, 2]

[5, 3, 4, 1, 2]

[5, 3, 4, 1, 2]

[1, 3, 4, 5, 2]

 

Pseudocode

• store the first element as the smallest value you've seen so far
• compare this item to the next item in the array until you find a smaller number
• if a smaller number is found, designate that smaller number to be the new 'minimum' and continue until the end of the array
• if the minimum is not the value(index) you initially began with, swap the two values 
  • we don't save the value, but we save the index of the value, so that we can swap (we wanna know where it is)
• repeat this with the next element until the array is sorted
  • we're not looking at the whole array. Then the minimum will be always the first one. We will shrink the scope

implementation

function selectionSort(array) {
  for (let i = 0; i < array.length; i++) {
    let lowest = i;
    for (let j = i + 1; j < array.length; j++) {
      // console.log(i, j);
      if (array[j] < array[lowest]) {
        lowest = j;
      }
      //swap
      if (i != lowest) {
        // console.log(array)
        // console.log(i, lowest);
        let temp = array[i];
        array[i] = array[lowest];
        array[lowest] = temp;
        // console.log(array)
      }
    }
    return arr;
  }

  selectionSort([0, 2, 34, 22, 10, 19, 17]);

  //ES6 version

  function selectionSort(array) {
    const swap = (arr, idx1, idx2) =>
      ([array[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]);

    for (let i = 0; i < array.length; i++) {
      let lowest = i;
      for (let j = i + 1; j < array.length; j++) {
        // console.log(i, j);
        if (array[j] < array[lowest]) {
          lowest = j;
        }
      }
    }
    if (i != lowest) {
      swap(array, i, lowest);
    }
    return array;
  }
}

selectionSort([0, 2, 34, 22, 10, 19, 17]);

 

Big O complexity

O(n^2)

배열이 늘어날수록 n이 늘어남

*bubble sort 은 계속 swap했다면, selection sort는 한번 반복할때마다 맨 끝에서 swap하면