이 방법은 가장 원시적인 방법으로 매번 ‘가장 작은 것을 선택’하는 알고리즘이다. 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째.. 그 다음 세 번째, 네 번째 이렇게 차례대로 데이터와 바꾸는 과정을 반복한다. 바꾸는 과정을 스와프(swap)라고 한다.
선택 정렬의 시간 복잡도
선택 정렬은 N - 1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 연산 횟수는 N + (N - 1) + (N - 2) + … + 2로 볼 수 있으며 근사치로 N X (N + 1) / 2번의 연산을 수행한다고 가정하자. 이는 (N2 + N) / 2로 표현할 수 있는데, 빅오 표기법으로 간단히 O(N2)이라고 표현할 수 있다. 직관적으로 이해하자면, 소스코드로 구현하면 2중 반복문이 사용되었기 때문이라고 이해할 수 있다.
[선택 정렬을 코드로 직접 구현]
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i range(len(array)):
min_index = i # 가장 작은 원소의 인덱스
for j in range(i + 1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i] # 스와프
print(array)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[파이썬 3.7의 라이브러리와 비교]
파이썬에 내장된 기본 정렬 라이브러리는 내부적으로 C 언어 기반이며, 다양한 최적화 테크닉이 포함되어 더욱 빠르게 동작한다. |데이터의 개수(N)|선택 정렬|퀵 정렬|파이썬 정렬 라이브러리| |—————|———|——-|——————–| |N=100 |0.0123초 |0.00156초|0.00000753초 | |N=1,000 |0.354초 |0.00343초|0.0000365초 | |N=10,000 |15.475초 |0.0312초 |0.000248초 |
ref
이것이 취업을 위한 코딩 테스트다 with 파이썬
나동빈 유튜브 강의