[인프런] 선택 정렬 - JavaScript

선택 정렬 (Selection Sort)

제자리 정렬(In-place sort) 알고리즘

1. 주어진 리스트 중 최솟값을 찾는다
2. 그 최솟값과 맨 앞에 위치한 값을 교체한다
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다
4. 1개의 요소가 남으면 중단한다

n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 정해진다.

Big O

최악(Worst) : 정렬이 하나도 안돼있는 경우	최선(Best) : 이미 정렬이 돼있는 경우	평균(Avg)
O(n2)	O(n2)	O(n2)

장점

• 알고리즘이 단순하다
• (제자리 정렬의 특징을 갖고 있으므로) 주어진 공간 외에 추가적인 메모리를 필요로 하지 않기 때문에 메모리가 제한적인 경우 성능 상의 이점이 있다

단점

• 현재 값이 최솟값이어도 최솟값을 찾기 위한 순회를 진행하기 때문에 불필요한 순회과정이 진행된다
• 최솟값을 찾는 횟수가 정해져있다
• 데이터가 중복된 경우 위치가 바뀔 수 있기 때문에 Unstable한 정렬이다

코드

인프런 '자바스크립트 알고리즘 문제풀이' 섹션7 선택 정렬 강의 참고

function solution(arr) {
  let answer = arr;

  for (let i = 0; i < arr.length - 1; i++) {
    let idx = i;

    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[idx]) {
        idx = j;
      }
    }

    [arr[i], arr[idx]] = [arr[idx], arr[i]];
  }

  return answer;
}

let arr = [13, 5, 11, 7, 23, 15];
console.log(solution(arr)); // [ 5, 7, 11, 13, 15, 23 ]

참고
선택 정렬 - 위키백과
[JS/Sorting] 버블 정렬, 삽입 정렬, 선택 정렬 자바스크립트로 구현하기
자바스크립트로 구현한 선택정렬 알고리즘