선택 정렬 (Selection Sort)
선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보낸다.
전체 연산 횟수는 N + (N - 1) + (N - 2) + ... + 2번 수행된다.
이를 근사치로 계산하면 N(N+1)/2로 표현할 수 있으며, 시간 복잡도는 O(N^2)이다.
선택 정렬은 기본 정렬 라이브러리를 포함해 뒤에서 다룰 알고리즘과 비교했을 때 매우 비효율적이다.
하지만 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 자주 등장하므로, 선택 정렬의 구현 방식에 익숙해질 필요가 있다.
a = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(a)):
min_idx = i
for j in range(i+1, len(a)):
if a[min_idx] > a[j]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]
print(a)삽입 정렬 (Insertion Sort)
삽입 정렬은 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 방식으로 동작한다.
선택 정렬에 비해 구현 난이도가 높지만, 일반적으로 더 효율적으로 동작한다.
삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
최선의 경우 O(N)의 시간 복잡도를 가지며, 최악의 경우 O(N^2)의 시간 복잡도를 가진다.
a = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(a)):
for j in range(i, 0, -1):
if a[j] < a[j-1]:
a[j], a[j-1] = a[j-1], a[j]
else:
break
print(a)퀵 정렬 (Quick Sort)
퀵 정렬은 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방식으로 동작한다.
일반적으로 가장 많이 사용되는 정렬 알고리즘 중 하나이며, 병합 정렬과 함께 대부분의 프로그래밍 언어에서 기본 정렬 알고리즘으로 활용된다.
가장 기본적인 퀵 정렬은 첫 번째 데이터를 피벗(pivot)으로 설정한다.
퀵 정렬의 시간 복잡도는 평균적으로 O(NlogN)이다.
- 최선의 경우: 분할이 일어날 때마다 왼쪽과 오른쪽이 절반씩 나뉘는 경우 → O(NlogN)
- 최악의 경우: 데이터가 이미 정렬되어 있는 경우 → O(N^2) (삽입 정렬과 반대되는 특성)
퀵 정렬을 제공하는 라이브러리는 최악의 경우에도 O(NlogN)을 보장하기 위해 피벗을 설정할 때 추가적인 로직을 포함한다.
a = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(a, start, end):
if start >= end:
return
pivot = start
left = start + 1
right = end
while left <= right:
while left <= end and a[left] <= a[pivot]: left += 1
while right > start and a[right] >= a[pivot]: right -= 1
if left > right:
a[right], a[pivot] = a[pivot], a[right]
else:
a[left], a[right] = a[right], a[left]
quick_sort(a, start, right - 1)
quick_sort(a, right + 1, end)
quick_sort(a, 0, len(a) - 1)
print(a)계수 정렬 (Counting Sort)
계수 정렬은 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠르게 동작하는 정렬 알고리즘이다.
계수 정렬은 데이터의 크기 범위가 제한되어 있고, 정수 형태로 표현할 수 있을 때 사용 가능하다.
- 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 최악의 경우에도 O(N + K)의 시간 복잡도를 보장한다.
- 공간 복잡도 또한 O(N + K)이다.
하지만 계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
예를 들어, 데이터가 0과 999,999로 단 2개만 존재하는 경우 메모리 낭비가 심하다.
동일한 값을 가지는 데이터가 여러 개 등장할 때 매우 효과적으로 사용할 수 있다.
예를 들어, 학생들의 성적을 정렬할 때 적절하다.
a = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
count = [0] * (max(a) + 1)
for i in range(len(a)):
count[a[i]] += 1
for i in range(len(count)):
for _ in range(count[i]):
print(i, end=' ')| 정렬 알고리즘 | 평균 시간 복잡도 | 최악의 시간 복잡도 | 특징 |
|---|---|---|---|
| 선택 정렬 | O(N^2) | O(N^2) | 구현이 간단하지만 비효율적 |
| 삽입 정렬 | O(N^2) | O(N) (거의 정렬된 경우) | 데이터가 정렬되어 있을수록 빠름 |
| 퀵 정렬 | O(NlogN) | O(N^2) (최악의 경우) | 평균적으로 가장 빠른 정렬 중 하나 |
| 계수 정렬 | O(N + K) | O(N + K) | 특정 조건에서 매우 빠름 |
