자바스크립트 정렬 알고리즘 3 : Selection Sort

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function selectionSort(array) {
  const length = array.length;
  for (let i = 0; i < length; i++) {
    let minIdx = i;
    let temp = array[i];
    for (let k = i+1; k < length; k++) {
      if (array[minIdx] > array[k]) {
        minIdx = k;
      }
    }
    array[i] = array[minIdx];
    array[minIdx] = temp;
  }
  return array;
}

selectionSort(numbers);

Bubble Sort와 마찬가지로, nested for loop의 형태를 띄기 때문에 시간 복잡도는 O(n^2)가 된다.

 

☞ Selection Sort의 로직