[JS] 선택정렬 구현 / 시간 복잡도

JavaScript 알고리즘 & 자료구조 마스터클래스

 

이 알고리즘은 배열에서 가장 작은 값을 두 개씩 비교하며 찾아서 그 값을 배열의 맨 앞으로 이동시킴으로써 정렬합니다.

1. 배열의 첫 번째 원소를 최소값으로 기억한다.
2. 배열의 나머지 원소들을 순서대로 탐색하며 최소값이라고 지정한 첫번째 원소보다 더 작은 값을 찾습니다.
3. 더 작은 값을 찾으면 그 값을 최소값으로 기억한다.
4. 배열의 마지막까지 돌면 기억해둔 최소값인 원소를 배열의 첫 번째 원소와 교체
5. 배열의 두 번째 원소를 최소값으로 지정한다.
6. 앞선 과정을 반복한다.

아래는 선택정렬을 구현한 코드입니다

function selectionSort(arr){
  for(let i = 0; i < arr.length; i++){
    let min = i
    for(let j = i+1; j < arr.length; j++){
      if(arr[j] < arr[min]){
        min = j
      }
    }
    if(min !== i){
      [arr[i], arr[min]] = [arr[min], arr[i]]
    }
  }
  return arr
}

 

시간 복잡도는 for문을 n만큼 두번 도는 것으로 O(n^2)이다.

 

동작 방식은 아래 사이트에서 보면 쉽게 이해할 수 있다.

https://visualgo.net/en/sorting

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo