<aside> 👉🏿 가장 원시적인 방법으로 매번 가장 작은 것을 선택하는 알고리즘이다.
데이터가 있을 때 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고,
그다음 작은 데이터를 두번째 데이터와 바꿔주는 과정을 반복한다.
선택 정렬의 시간 복잡도는 O(N**2)이다. 따라서 버블 정렬만큼 비 효율적이다.
</aside>
[4, 6, 2, 9, 1] # 정렬되지 않은 배열
1단계 : [4, 6, 2, 9, 1]
4와 6과 2와 9와 1을 차례차례 비교합니다.
그 중 가장 작은 1과 맨 앞 자리인 4를 교체합니다!
[1, 6, 2, 9, 4] 이렇게요!
자, 그러면 이제 가장 작은 숫자인 1이 맨 앞으로 왔습니다.
가장 작은 걸 가장 맨 앞으로 옮기기로 했으니까요!
그러면, 맨 앞자리를 제외하고 다시 한 번 반복하면 됩니다.
2단계 : [1, 6, 2, 9, 4]
6과 2와 9와 4를 차례차례 비교합니다.
그 중 가장 작은 2와 두번째 앞 자리인 6을 교체합니다!
[1, 2, 6, 9, 4] 이렇게요!
3단계 : [1, 2, 6, 9, 4]
6과 9와 4를 차례차례 비교합니다.
그 중 가장 작은 4와 세번째 앞 자리인 6을 교체합니다!
[1, 2, 4, 9, 6] 이렇게요!
4단계 : [1, 2, 4, 9, 6]
9와 6을 비교합니다!
그 중 가장 작은 6과 네번째 앞 자리인 9을 교체합니다!
[1, 2, 4, 6, 9] 이렇게요!
자, 모두 정렬이 되었습니다! 어떠신가요? 감이 좀 오시나요?
버블 정렬보다 훨씬 더 적은 비교를 하는 것 같지만,
실제로는 각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 사용해야 합니다!
def selection_sort(list):
iters = len(list) - 1
# 리스트의 길이만큼 반복
for iter in range(iters):
# 최소값은 시작값으로 지정
minimum = iter
# 시작값 다음부터 리스트의 길이까지 반복
for cur in range(iter + 1, len(list)):
# 현재값이 최소값보다 작을 경우 최소값을 현재값으로 지정
if list[cur] < list[minimum]:
minimum = cur
# 최소값이 바뀌었을 경우
if minimum != iter:
# 스와프
list[minimum], list[iter] = list[iter], list[minimum]