선택 정렬

목표: 배열을 낮은 순서에서 높은 순서로(또는 높은 순서에서 낮은 순서로) 정렬한다.

숫자 배열이 주어지면 이를 올바른 순서로 배치해야 한다. 선택 정렬 알고리즘은 배열을 두 부분으로 나눈다: 배열의 시작 부분은 정렬된 상태이고, 나머지 부분은 아직 정렬되지 않은 숫자들로 구성된다.

[ ...정렬된 숫자... | ...정렬되지 않은 숫자... ]

이 방식은 삽입 정렬과 비슷하지만, 새로운 숫자를 정렬된 부분에 추가하는 방식에서 차이가 있다.

선택 정렬은 다음과 같이 동작한다:

배열에서 가장 작은 숫자를 찾는다. 인덱스 0부터 시작해 배열의 모든 숫자를 순회하며 가장 작은 숫자를 추적한다.
가장 작은 숫자를 인덱스 0의 숫자와 교환한다. 이제 정렬된 부분은 인덱스 0에 위치한 숫자 하나로 구성된다.
인덱스 1로 이동한다.
나머지 배열에서 가장 작은 숫자를 찾는다. 이번에는 인덱스 1부터 탐색을 시작한다. 다시 배열의 끝까지 순회하며 가장 작은 숫자를 추적한다.
가장 작은 숫자를 인덱스 1의 숫자와 교환한다. 이제 정렬된 부분은 두 개의 숫자로 구성되며, 인덱스 0부터 인덱스 1까지 확장된다.
인덱스 2로 이동한다.
나머지 배열에서 가장 작은 숫자를 찾는다. 이번에는 인덱스 2부터 시작해 탐색하고, 가장 작은 숫자를 인덱스 2의 숫자와 교환한다. 이제 배열은 인덱스 0부터 인덱스 2까지 정렬되며, 이 범위에는 배열에서 가장 작은 세 개의 숫자가 포함된다.
이 과정을 더 이상 정렬할 숫자가 없을 때까지 반복한다.

이 알고리즘을 "선택" 정렬이라고 부르는 이유는 각 단계에서 나머지 배열을 탐색해 다음으로 가장 작은 숫자를 선택하기 때문이다.

예제

정렬할 숫자가 [5, 8, 3, 4, 6]라고 가정한다. 배열에서 정렬된 부분의 끝을 나타내는 | 기호를 사용해 표시한다.

처음에는 정렬된 부분이 비어 있다:

[| 5, 8, 3, 4, 6 ]

이제 배열에서 가장 작은 숫자를 찾는다. | 기호부터 시작해 왼쪽에서 오른쪽으로 배열을 스캔한다. 숫자 3을 찾는다.

이 숫자를 정렬된 위치에 넣기 위해 | 바로 다음에 있는 숫자 5와 교환한다:

[ 3 | 8, 5, 4, 6 ]
  *      *

이제 정렬된 부분은 [3]이고 나머지는 [8, 5, 4, 6]이다.

다시 | 기호부터 시작해 가장 작은 숫자를 찾는다. 4를 찾고 8과 교환한다:

[ 3, 4 | 5, 8, 6 ]
     *      *

매 단계마다 | 기호가 오른쪽으로 한 칸씩 이동한다. 다시 나머지 배열을 살펴보고 가장 작은 숫자 5를 찾는다. 5를 자기 자신과 교환할 필요는 없으므로 그냥 진행한다:

[ 3, 4, 5 | 8, 6 ]
        *

이 과정은 배열이 완전히 정렬될 때까지 반복된다. | 기호 왼쪽에 있는 모든 요소는 항상 정렬된 상태이며 배열에서 가장 작은 숫자들로 구성된다. 최종적으로 다음과 같은 결과를 얻는다:

[ 3, 4, 5, 6, 8 |]

선택 정렬은 추가 메모리를 사용하지 않고 동일한 배열 내에서 모든 작업이 이루어지므로 제자리 정렬이다. 또한 동일한 요소들이 서로 상대적인 위치를 바꾸지 않도록 안정 정렬로 구현할 수도 있다(아래 버전은 안정 정렬이 아님).

코드 구현

다음은 Swift로 구현한 선택 정렬(selection sort) 코드이다:

func selectionSort(_ array: [Int]) -> [Int] {
  guard array.count > 1 else { return array }  // 1

  var a = array                    // 2

  for x in 0 ..< a.count - 1 {     // 3

    var lowest = x
    for y in x + 1 ..< a.count {   // 4
      if a[y] < a[lowest] {
        lowest = y
      }
    }

    if x != lowest {               // 5
      a.swapAt(x, lowest)
    }
  }
  return a
}

이 코드를 플레이그라운드에 넣고 다음과 같이 테스트한다:

let list = [ 10, -1, 3, 9, 2, 27, 8, 5, 1, 3, 0, 26 ]
selectionSort(list)

코드가 동작하는 과정을 단계별로 설명한다:

배열이 비어 있거나 단일 요소만 포함하면 정렬할 필요가 없다.
배열의 복사본을 만든다. Swift에서는 array 파라미터의 내용을 직접 수정할 수 없기 때문에 이 과정이 필요하다. Swift의 sort() 함수와 마찬가지로 selectionSort() 함수도 원본 배열의 정렬된 복사본을 반환한다.
이 함수에는 두 개의 루프가 있다. 외부 루프는 배열의 각 요소를 순차적으로 확인하며, 이는 | 표시를 앞으로 이동시키는 역할을 한다.
내부 루프는 배열의 나머지 부분에서 가장 작은 값을 찾는다.
가장 작은 값을 현재 배열 인덱스와 교환한다. Swift에서는 요소를 자기 자신과 교환할 수 없기 때문에 if 검사가 필요하다.

요약하자면, 선택 정렬은 배열의 각 요소를 나머지 배열에서 가장 작은 값과 교환한다. 결과적으로 배열은 왼쪽에서 오른쪽으로 정렬된다. (오른쪽에서 왼쪽으로 정렬하는 것도 가능하며, 이 경우 항상 배열에서 가장 큰 값을 찾는다. 이를 시도해 보자!)

참고: 외부 루프는 인덱스 a.count - 2에서 끝난다. 마지막 요소는 더 이상 작은 요소가 남아 있지 않기 때문에 자동으로 올바른 위치에 있다.

SelectionSort.swift 소스 파일에는 제네릭을 사용한 이 함수의 버전이 포함되어 있다. 이를 통해 문자열이나 다른 데이터 타입도 정렬할 수 있다.

성능

선택 정렬은 이해하기 쉽지만 **O(n^2)**의 시간 복잡도로 인해 느리게 동작한다. 삽입 정렬보다는 성능이 떨어지지만 버블 정렬보다는 나은 편이다. 배열의 나머지 부분에서 가장 작은 요소를 찾는 과정이 느리며, 특히 내부 반복문이 반복적으로 실행되기 때문에 더욱 그렇다.

힙 정렬은 선택 정렬과 동일한 원리를 사용하지만, 배열의 나머지 부분에서 최소값을 찾는 빠른 방법을 제공한다. 힙 정렬의 성능은 **O(n log n)**이다.

함께 보기

위키피디아의 선택 정렬

Swift Algorithm Club을 위해 Matthijs Hollemans가 작성함