[알고리즘] 선택정렬

선택정렬(Selection sort)

• 다음과 같은 순서를 반복하며 정렬하는 알고리즘
  1. 주어진 데이터 중, 최소값을 찾음
     2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
     3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

설명	0	1	2	3	4	-
ex)	5	2	4	3	1
0번 자리부터 끝까지 중 최솟값은 1이므로 0번 자리와 교체	1	2	4	3	5	실행횟수 = 4
1번 자리부터 끝까지 중 최솟값은 2이므로 1번 자리와 교체	1	2	4	3	5	실행횟수 = 3
2번 자리부터 끝까지 중 최솟값은 3이므로 2번 자리와 교체	1	2	3	4	5	실행횟수 = 2
3번 자리부터 끝까지 중 최솟값은 4이므로 3번 자리와 교체	1	2	3	4	5	실행횟수 = 1
끝	1	2	3	4	5	반복횟수 = 4

• 배열의 길이 = 5
• 실행횟수 = 4 -> 3 -> 2 -> 1
• 반복횟수 = 4

일반화

• 배열의 길이 = n
• 실행횟수 = n-1 -> n-2 -> ... -> 2 -> 1
• 반복횟수 = n-1

특징

• 최솟값의 인덱스을 담을 변수를 생성

구현

1. for stand in range(len(data)-1) 로 반복
2. lowest = stand 로 놓고,
3. for num in range(stand, len(data)) stand 이후부터 끝까지 반복
   • 내부 반복문 안에서 data[lowest] > data[num] 이면,
     • lowest = num
4. 최솟값을 찾았으면
   data[num], data[lowest] = data[lowest], data[num]

---

Python

def selection_sort(data):
    for stand in range(len(data)-1):
        lowest = stand
        for num in range(stand+1, len(data)):
            if data[lowest] > data[num]:
                lowest = num
        data[stand], data[lowest] = data[lowest], data[stand]
    return data

Swift

import Foundation

func selectionSort(_ data: [Int]) -> [Int] {
    var data = data
    for stand in 0..<data.count-1 {
        var lowest = stand
        for num in (stand+1)..<data.count {
            if data[lowest] > data[num] {
                lowest = num
            }
        }
        data.swapAt(lowest, stand)
    }
    return data
}

시간복잡도

• 반복문이 2개이므로 $O(n^2)$
  • 실제로 ${n(n-1)\over 2}$