TIL 83 | 정렬(3) - JS로 Selection Sort 구현

Gom·2021년 6월 3일

Selection Sort

Algorithm

목록 보기

40/48

Selection Sort

개념

배열 안에서 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬

선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

과정

숫자들 중에서 가장 작은 값을 찾는다.
가장 작은 값은 가장 앞에 있어야 하므로 현재 리스트의 첫 번째 값과 자리를 교환한다.
정렬된 가장 앞 자리를 제외하고 두 번째 숫자부터 시작해서 1,2번을 반복한다.

시간복잡도

Big-O : O(n^2)

Big-Ω : Ω(n^2)

(n-1)*(n-2) = n^2-3n+2
바깥 루프에서는 숫자들을 처음부터 순서대로 방문하고, 안쪽 루프에서는 가장 작은 값을 찾아야하므로 두 번의 루프를 돈다.

장단점

장점

버블 정렬과 마찬가지로 알고리즘이 단순하다.
메모리 절약 O(1)
정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간 불필요
(in-place sorting 제자리정렬)

단점

시간복잡도 비효율적

특징

Unstable

중복 데이터가 있는 경우 기존 중복 데이터 순서가 바뀔 수 있다.

코드

function selectionSort (array) {
  for(let i=0; i<array.length; i++){
    let minIdx = i;
    for(let j=i+1; j<array.length; j++){
      if(array[minIdx]>array[j]){
        minIdx = j;
      }
    }
    if(minIdx !== i){
      let swap = array[minIdx];
      array[minIdx] = array[i];
      array[i] = swap;
      
    }
    console.log(`${i}회전 : ${array}`)
  }
  return array;
}
console.log(selectionSort([5,7,3,4,1,6,2]));