선택 정렬(selection sort)

참고: 누구나 자료 구조와 알고리즘 2장,

모두를 위한 컴퓨터 과학(하버드 데이비드말란 교수님) 강의

 

1.1. 선택 정렬

정렬을 위한 알고리즘 중 선택 정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 선택해놓은 다음, 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.
선택 정렬은 버블 정렬처럼 쌍을 이뤄 앞/뒤 순서를 교환하지 않는다. 매번 가장 작은 값을 선택해놓는 것이 목표다.
즉, 반복할 때마다 가장 작은 수를 선택하는 것이다.

버블 정렬은 인접한 두 원소를 비교할 때마다 교환이 발생하지만, 선택 정렬은 교환 횟수를 최소화한다.

 

1.2. 선택 정렬 구현

1부터 N개의 원소가 있다고 하자. (인덱스 번호로는 0번째부터 N-1번째에 원소가 있는 것)

for i in range(len(n)-1)

1) [i=0]번째 원소부터 마지막 [i=N-1]번째까지 모든 원소 값을 비교해 가장 작은 원소를 선택해놓는다. -> N-1번 비교
2) 가장 작은 원소를 찾으면 [i=0]번째 원소와 교환한다. -> 1번 교환
3) 가장 작은 원소는 [i=0]번째로 정렬된다.

4) 정렬된 [i=0]번째 원소를 제외하고, [i=1]번째 ~ [i=N-1]번째의 원소까지 다시 모든 수를 비교한다. -> N-2번 비교
5) 가장 작은 원소를 찾으면 [i=1]번째 원소와 교환한다. -> 1번 교환
6) 가장 작은 원소는 [i=1]번째로 정렬된다.

---

선택 정렬

 

1.3. 선택 정렬의 효율성

최악의 시나리오: O(N²)

• 비교: (N-1) + (N-2) + ... + 1 = N(N-1)/2번
• 교환(swap): 1 + 1 + 1 + ... = N-1번

최선의 시나리오: Ω(N²)

• 비교: (N-1) + (N-2) + ... + 1 = N(N-1)/2번
• 교환(swap): 0번

ex. 1234567 로 이미 정렬되어 있는 최선의 상황을 보자.
우리는 1이 가장 작은 원소임을 직관적으로 알 수 있지만, 프로그램은 배열 속 숫자를 전부 열어봐야 알 수 있다.
따라서 최선의 시나리오에서도 비교 횟수는 최악의 시나리오와 같다.

 

1.4. 선택 정렬의 장점

• 버블 정렬에 비해 교환 횟수는 적기 때문에 많은 교환이 일어나야 하는 배열에서 비교적 효율적이다.
• 버블 정렬과 마찬가지로 배열 안에서 교환하는 제자리 정렬 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

---

참고: NAVER Connect Foundation 모두를 위한 컴퓨터 과학 강의 자료

선택 정렬은 버블 정렬과는 다르게 몇 번의 교환을 해주었는지 횟수를 셀 필요가 없다. (비교마다 1번의 교환만 발생)
원래 배열의 순서와 상관없이 선택 정렬로 정렬되는 배열은 총 n-1번의 교환이 필요하다. n-1번의 교환은 확실히 버블 정렬의 교환 횟수보다는 적지만, N-1번의 교환이 일어나기 위해서는 정렬되지 않은 모든 수와 비교가 이루어져야 하므로 N(N-1)/2번 비교가 이루어진다.
선택 정렬은 최선의 경우에도 최악의 경우에서 수행하는 횟수만큼 비교를 해주어야 한다.