매번 처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞의 데이터와 바꾸는 것을 반복
시간 복잡도
N개의 데이터를 정렬한다고 할 때, N개 중 최솟값 앞으로 보내기, N-1개 중 최솟값 앞으로 보내기, ..., 2개 중 최솟값 앞으로 보내기 수행
= N + (N - 1) + (N - 2) + ... + 2 = (N - 1)(N + 2) / 2 = (N2 + N - 2) / 2
O(N2)
주어진 데이터가 얼마나 정렬되어 있는지 상관없이, 무조건 모든 원소를 비교하여 최솟값을 찾는 작업을 반복적으로 수행해야 함
공간 복잡도
array = [3, 8, 6, 0, 1, 7, 9, 4, 5, 2]
for i in range(len(array) - 1):
min_idx = i
for j in range(i+1, len(array)):
if array[j] < array[min_idx]:
min_idx = j
array[i], array[min_idx] = array[min_idx], array[i]
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
처리되지 않은 데이터를 하나씩 확인하며 적절한 위치에 삽입
처리를 마친 앞부분의 데이터들은 무조건 정렬되어 있는 상태
시간 복잡도
O(N2)
BUT 선택 정렬과 다른 점은, 주어진 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작
최선의 경우, 즉 모든 데이터가 이미 정렬되어 있는 상태라면, O(N)의 시간 복잡도를 가짐. B/C inner loop이 항상 break를 만나 바로 끝날 것이기 때문에 사실상 outer loop만 있는 것과 동일하기 때문.
공간 복잡도
array = [3, 8, 6, 0, 1, 7, 9, 4, 5, 2]
for i in range(1, len(array)): # 2번째 원소부터 시작하면 됨
for j in range(i, 0, -1):
if array[j - 1] > array[j]:
array[j], array[j - 1] = array[j - 1], array[j]
else:
break
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
기준 데이터(Pivot)를 설정(e.g., 첫 번째 데이터)하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
현재 데이터의 정렬 상태와 상관없이 일반적으로 가장 많이 사용되는 정렬 알고리즘
피벗을 기준으로 데이터 분할 (Divide or Partition) -> 재귀적으로 반복
시간 복잡도
평균적으로, O(NlogN)
최악의 경우, O(N2)
공간 복잡도
일반적인 형태의 퀵 정렬 소스코드
array = [3, 8, 6, 0, 1, 7, 9, 4, 5, 2]
def quick_sort(start, end): # start와 end는 idx 기준
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start
left = start + 1
right = end
while left <= right:
while left <= end and array[left] <= array[pivot]:
left += 1
while right > start and array[right] >= array[pivot]:
right -= 1
if left > right: # left와 right이 엇갈렸다면, 피벗과 작은 데이터(이 경우엔 right) 교체
array[pivot], array[right] = array[right], array[pivot]
else:
array[left], array[right] = array[right], array[left]
quick_sort(start, right - 1)
quick_sort(right + 1, end)
quick_sort(0, len(array) - 1)
print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
더 직관적 BUT 시간이 좀 더 걸리는 소스코드
array = [3, 8, 6, 0, 1, 7, 9, 4, 5, 2]
def quick_sort(array):
if len(array) <= 1:
return array
pivot = array[0]
tail = array[1:]
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(array)) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
각각의 데이터가 몇 번씩 등장하는지를 카운트하는 방식
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능하지만 매우 빠르게 동작하는 정렬 알고리즘
시간 복잡도 & 공간 복잡도
O(N + K) (N = 데이터의 개수, K = 데이터 중 최댓값)
동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적
BUT 데이터 = [0, 999999]와 같이 주어질 때는 매우 비효율적
array = [3, 0, 2, 8, 6, 5, 0, 1, 7, 9, 4, 9, 0, 5, 2]
count = [0] * (max(array) + 1)
for i in array:
count[i] += 1
for i in range(len(count)):
for j in range(count[i]):
print(i, end = ' ') # 0 0 0 1 2 2 3 4 5 5 6 7 8 9 9
정렬 라이브러리는 최악의 경우에도 항상 시간 복잡도 O(NlogN)을 보장한다. 따라서, 문제에서 특정 정렬 알고리즘 사용을 요구한 게 아니라면 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 제한되어 있으며 빠른 동작이 필요할 땐 계수 정렬을 사용하면 된다.
array = [(3, 1, 2), (1, 2, 4), (1, 3, 2), (5, 2, 1), (3, 1, 1)]
first_array = sorted(array)
print(first_array) # [(1, 2, 4), (1, 3, 2), (3, 1, 1), (3, 1, 2), (5, 2, 1)]
second_array = sorted(array, reverse = True)
print(second_array) # [(5, 2, 1), (3, 1, 2), (3, 1, 1), (1, 3, 2), (1, 2, 4)]
[참고]