선택 정렬(Selection Sort)

코딩테스트 스터디를 하면서, 정리해두면 좋을 자료구조나 알고리즘 등을 정리해두려 한다.

선택정렬이란?

배열을 처음부터 끝까지 탐색하며, 가장 작은 요소를 선택해 앞에 위치한 값과 교체를 하는 과정을 가진 알고리즘으로, 이 과정이 반복되면서 전체 배열이 오름차순으로 정렬된다.

 

특징

- 선택 정렬은 제자리 정렬(in-place sort) 알고리즘으로 추가적인 메모리 공간을 거의 필요로 하지 않아, 메모리가 매우 제한적인 환경에서 유용하고 한다. 

- 선택 정렬은 입력 데이터가 어떤 상태든 상관없이 항상 동일한 시간복잡도(O(n^2))를 가진다. 따라서, 데이터가 이미 부분적으로 정렬되어 있는 경우나 정렬 방향(오름차순, 내림차순)에 관계없이 항상 동일한 성능을 보여준다.

- 선택 정렬은 정렬 과정에서 데이터 이동(swap)이 n번 이루어진다. 따라서 데이터 이동 비용이 크게 부담되는 경우, 선택 정렬이 좋은 선택일 수 있다.

* 위와 같은 상황에서는 유용하지만, 크기가 큰 리스트에 대해서는 효율이 좋지 않아, 실제 앱에서는 잘 사용되지 않고, 다른 정렬 알고리즘(퀵 정렬, 병합 정렬 등)을 사용한다고 한다.

 

예제

[4, 2, 7, 1, 3]이라는 배열에 선택 정렬을 적용하는 과정이다.

1단계: i = 0일 때, 첫 번째 요소를 가장 작은 요소로 가정하고 나머지 배열을 탐색한다.

[4, 2, 7, 1, 3] : 현재 가장 작은 수는 4, 그 위치는 0이다.
[4, 2, 7, 1, 3] : 2는 4보다 작으므로 가장 작은 수는 2, 그 위치는 1이다.
[4, 2, 7, 1, 3] : 7은 2보다 크므로 변경하지 않는다.
[4, 2, 7, 1, 3] : 1은 2보다 작으므로 가장 작은 수는 1, 그 위치는 3이다.
[4, 2, 7, 1, 3] : 3은 1보다 크므로 변경하지 않는다.
가장 작은 수 1과 i번째 위치에 있는 4를 교환한다.
결과: [1, 2, 7, 4, 3]

2단계: i = 1일 때, 두 번째 요소를 가장 작은 요소로 가정하고 나머지 배열을 탐색한다.

[1, 2, 7, 4, 3] : 현재 가장 작은 수는 2, 그 위치는 1이다.
[1, 2, 7, 4, 3] : 7은 2보다 크므로 변경하지 않는다.
[1, 2, 7, 4, 3] : 4는 2보다 크므로 변경하지 않는다.
[1, 2, 7, 4, 3] : 3는 2보다 크므로 변경하지 않는다.
가장 작은 수 2가 이미 i번째 위치에 있으므로 교환하지 않다.
결과: [1, 2, 7, 4, 3]

3단계: i = 2일 때, 세 번째 요소를 가장 작은 요소로 가정하고 나머지 배열을 탐색한다.

[1, 2, 7, 4, 3] : 현재 가장 작은 수는 7, 그 위치는 2이다.
[1, 2, 7, 4, 3] : 4는 7보다 작으므로 가장 작은 수는 4, 그 위치는 3이다.
[1, 2, 7, 4, 3] : 3는 4보다 작으므로 가장 작은 수는 3, 그 위치는 4이다.
가장 작은 수 3과 i번째 위치에 있는 7을 교환한다.
결과: [1, 2, 3, 4, 7]

4단계: i = 3일 때, 네 번째 요소를 가장 작은 요소로 가정하고 나머지 배열을 탐색한다.

[1, 2, 3, 4, 7] : 현재 가장 작은 수는 4, 그 위치는 3이다.
[1, 2, 3, 4, 7] : 7은 4보다 크므로 변경하지 않는다.
가장 작은 수 4가 이미 i번째 위치에 있으므로 교환하지 않는다.
결과: [1, 2, 3, 4, 7]

5단계: i = 4일 때, 이미 마지막 요소이므로, 더 이상 비교할 필요가 없다.

최종 결과: [1, 2, 3, 4, 7]

설명

function selectionSort(array) { 

  for(let i = 0; i < array.length - 1; i++) { // 배열의 첫번째 요소부터 시작해서 마지막에서 두 번째 요소까지 반복한다. (마지막 요소는 자동적으로 정렬되기 때문에 확인할 필요가 없다)
    let lowestNumberIndex = i; // 가장 작은 수를 가리키는 인덱스를 초기화합니다. 첫 반복에서는 첫번째 요소로 설정된다.

    for(let j = i + 1; j < array.length; j++) { // 선택한 요소의 다음 요소부터 배열의 마지막 요소까지 반복한다. 이는 'i'번째 요소가 가장 작은 수인지 확인하기 위한 반복문이다.
      if(array[j] < array[lowestNumberIndex]) { // 'j'번째 요소가 현재까지 찾은 가장 작은 수보다 작으면,
        lowestNumberIndex = j; // 가장 작은 수를 가리키는 인덱스를 'j'로 업데이트한다.
      }
    }

    if(lowestNumberIndex != i) { // 'i'번째 요소가 가장 작은 수가 아니라면, 즉 가장 작은 수의 위치가 'i'가 아니라면
      let temp = array[i]; // 'i'번째 요소를 임시 변수에 저장한다.
      array[i] = array[lowestNumberIndex]; // 가장 작은 수를 'i'번째 위치로 이동한다.
      array[lowestNumberIndex] = temp; // 'i'번째 요소를 가장 작은 수가 있던 위치로 이동한다. 이로써 'i'번째 요소와 가장 작은 수가 바뀌었다.
    }
  }

  return array; // 정렬이 완료된 배열을 반환한다.
}