Github

선택 정렬(Selection Sort)

1. 선택 정렬이란?

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

선택 정렬은 버블 정렬과 비슷하지만 (오름차순 기준) 작은 값을 먼저 정렬을 하는것에 차이가 있다. 아래의 예시를 살펴보자.

1-1. 선택 정렬의 간단한 예시

배열 [5, 3, 4, 1, 2]이 있다. 이를 선택 정렬을 통해 오름차순으로 바꾸어 보자.

  1. 첫번재 정렬: 첫번째 값이 정해진다.

    • [5, 3, 4, 1, 2]: 5와 3을 비교 -> 가장 작은 값은 3

    • [5, 3, 4, 1, 2]: 5와 4을 비교 -> 가장 작은 값은 3

    • [5, 3, 4, 1, 2]: 5와 1을 비교 -> 가장 작은 값은 1

    • [5, 3, 4, 1, 2]: 5와 2을 비교 -> 가장 작은 값은 1

    • [1, 3, 4, 5, 2]: 지금까지 비교한 값들 중 가장 작은 값이 1을 첫번째에 정렬

  2. 두번째 정렬: 두번째 값이 정해진다.

    • [1, 3, 4, 5, 2]: 3와 4을 비교 -> 가장 작은 값은 3

    • [1, 3, 4, 5, 2]: 3와 5을 비교 -> 가장 작은 값은 3

    • [1, 3, 4, 5, 2]: 3와 2을 비교 -> 가장 작은 값은 2

    • [1, 2, 4, 5, 3]: 지금까지 비교한 값들 중 가장 작은 값이 2을 두번째에 정렬

  3. 세번째 정렬: 세번째 값이 정해진다.

    • [1, 2, 4, 5, 3]: 4와 5을 비교 -> 가장 작은 값은 4

    • [1, 2, 4, 5, 3]: 4와 3을 비교 -> 가장 작은 값은 3

    • [1, 2, 3, 5, 4]: 지금까지 비교한 값들 중 가장 작은 값이 3을 세번째에 정렬

  4. 네번째 정렬: 네번째 값이 정해진다.

    • [1, 2, 3, 5, 4]: 5와 4을 비교 -> 가장 작은 값은 4

    • [1, 2, 3, 4, 5]: 지금까지 비교한 값들 중 가장 작은 값이 4을 네번째에 정렬

  5. 다섯번 정렬: 더이상 비교할 값이 없으므로 종료

2. 선택 정렬 의사 코드

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

위는 숫자를 요소로 가지는 배열의 오름차순으로 선택 정렬하는 의사 코드이다. 첫번째 for... 문에서 가장 먼저 하는 것은 가장 작은 값을 가진 인덱스를 lowest에 할당하는 것이다. 첫 시작이므로 항상 i가 먼저 할당된다.

두번째 for... 문에서는 i 이후의 값들을 비교하며 값이 더 작을 경우 lowest 값을 최신화한다. 두번째 for... 문이 끝나고 나서 만약 lowest값이 바뀌었다면 그것와 i의 위치를 바꾼다.

3. 선택 정렬의 시간 복잡도

선택 정렬은 O(n^2)의 시간 복잡도를 가지기 때문에 버블 정렬과 마찬가지로 효율적이지 않다. 모든 요소를 배열 속 다른 요소와 모두 비교해야 하기에 배열의 길이가 길어 질 수록 걸리는 시간은 제곱으로 길어진다.

버블 정렬과 비교하여 선택 정렬이 나은 점은 스왑을 덜 적게 한다는 것이다.

4. Conclusion

버블 정렬에 이어서 선택 정렬을 정리하였다. 오름 차순 기준으로 가장 작은 값을 먼저 정렬할 것인가(선택 정렬)와 가장 큰 값을 먼저 정렬할 것인가(버블 정렬)의 차이일 뿐 둘다 시간 복잡도는 상상도 하기 싫은 O(n^2)을 가지고 있다. 때문에 실제로는 많이 사용하지 않을 듯 하다. 아무래도 O(n^2)는 너무 오래 걸리기 때문에 시도를 하기에도 부담스럽다.

참고

Udemy - JavaScript 알고리즘 & 자료구조 마스터클래스 / 섹션 12: 선택 정렬

📅 2023-01-27

Previous버블 정렬(Bubble Sort)Next삽입 정렬(Insertion Sort)

Last updated