CS50 2019 강의를 듣고 내용을 정리한 시리즈 글입니다.
학습목표
선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있습니다.
핵심 단어
- 선택 정렬
강의 내용
1. 선택 정렬
선택정렬은 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.
선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.
1~8의 숫자가 임의로 나열되어 있는 리스트로 선택 정렬을 실행해보자
전: 6 3 8 5 2 7 4 1
후: 1 3 8 5 2 7 4 6
리스트 중 가장 작은 값 1을 찾은 후 첫 번째 인덱스인 6과 교환했다.
작업을 반복해보자
1 2 8 5 3 7 4 6
1 2 3 5 8 7 4 6
1 2 3 4 8 7 5 6
1 2 3 4 5 7 8 6
1 2 3 4 5 6 8 7
1 2 3 4 5 6 7 8선택 정렬을 python으로 나타내면 아래와 같다.
def selection_sort(array):
for i in range(len(array)-1):
min_num = i
for j in range(i + 1, len(array)):
if array[min_num] > array[j]:
min_num = j
array[i], array[min_num] = array[min_num], array[i]
return array선택 정렬 또한 버블 정렬과 마찬가지로 중첩 루프를 돌아야하기 때문에 시간은 O(n^2)과 Ω(n^2)이 된다.
생각해보기
선택정렬을 좀 더 효율적으로 어떻게 바꿀 수 있을까요?
최소값과 최대값을 동시에 비교하는 이중 선택 정렬이 좀 더 효율적이라고 볼 수 있지만 시간복잡도는 선택정렬과 동일하다.
