정렬 알고리즘(Sorting Algorithm)
- 데이터를 일정한 순서대로 열거하는 알고리즘
- 어떤 정렬을 쓰냐에 따라 프로그램의 효율성이 좌지우지될 수 있다.
- 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬, 병합 정렬, 힙 정렬 정도까지는 알고 있으면 좋다.
선택 정렬(Selection Sort)
순회하며 제일 작은 데이터를 맨 앞으로 옮김으로써 왼쪽부터 정렬을 완성해가는 방식
코드
def selection_sort(array):
for i in 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]
array = [7, 3, 1, 5, 9]
selection_sort(array)
print(array) # [1, 3, 5, 7, 9]시간 복잡도
다음과 같은 이유로 O(N^2)이다.
- (N-1) + (N-2) + ... + 2 = N(N+1)/2 라서
- 반복문이 두 번 중첩되었으므로
따라서 알고리즘 문제 풀이에 사용하기에는 조금 느리다.
삽입 정렬(Insertion Sort)
왼쪽의 데이터를 하나씩 확인하며 왼쪽으로 움직이다가(swap) 자신보다 작은 데이터 앞에서 멈춤으로써 왼쪽부터 정렬을 완성해가는 방식
삽입 정렬은 내 왼쪽 애들은 모두 정렬된 상태라는 전제로 동작한다.
코드
def insertion_sort(array):
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] >= array[j - 1]:
break
array[j], array[j - 1] = array[j - 1], array[j]
array = [7, 3, 1, 5, 9]
insertion_sort(array)
print(array) # [1, 3, 5, 7, 9]시간복잡도
선택 정렬과 마찬가지로 O(N^2)이다.
그러나 최선의 시간복잡도는 O(N)이기 때문에 거의 정렬된 상태의 자료에서 효율적이다.
퀵 정렬(Quick Sort)
기준 데이터(피벗)를 설정하고 기준 데이터를 기점으로 왼쪽에는 보다 작은 데이터가, 오른쪽에는 보다 큰 데이터가 오게 하는 방식
코드
- 첫 번째 원소를 피벗으로 잡고 왼쪽에서부터 피벗보다 큰 데이터를, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
- 찾은 후 두 데이터가 엇갈리지 않았다면 swap, 엇갈렸다면 작은 데이터와 피벗의 위치를 바꾼다.
- 2번까지 수행하고나면 피벗을 기준으로 왼쪽은 보다 작은 데이터가, 오른쪽은 보다 큰 데이터가 존재하게 된다.
def quick_sort(array, start, end):
if start >= end:
return
pivot = start
left, right = start + 1, end
while True:
while left <= end:
if array[pivot] < array[left]:
break
left += 1
while right > start:
if array[pivot] >= array[right]:
break
right -= 1
if left >= right:
break
array[left], array[right] = array[right], array[left]
array[pivot], array[right] = array[right], array[pivot]
quick_sort(array, start, right - 1)
quick_sort(array, right + 1, end)
array = [6, 4, 1, 3, 5, 0]
quick_sort(array, 0, len(array) - 1)
print(array)시간 복잡도
최선의 경우
- 항상 피벗이 정중앙에 위치하게 될 때
- 즉, 항상 정중앙을 기준으로 배열을 쪼개 재귀에 들어가는 경우
- 이 때 시간 복잡도는
O(NlogN)이다.
최악의 경우
- 배열이 한 쪽으로 치우쳐 쪼개져 데이터의 개수만큼 쪼개지는 경우
- 이 때 시간 복잡도는
O(N^2)이다.
따라서 위와 같이 피벗을 선정하는 경우 퀵 정렬은 오히려 정렬된 데이터에서 느리고, 무작위 데이터에서 빨라진다.
이를 보완하기 위해 별도의 피벗 선정 알고리즘을 이용하기도 한다.
계수 정렬
모든 데이터를 담을 수 있는 리스트를 선언해 등장 횟수를 세는 방식
지금까지 본 선택, 삽입, 퀵 정렬은 비교 기반의 정렬 알고리즘이다.
계수 정렬은 데이터를 카운트할 뿐이기 때문에 비교 기반의 정렬 알고리즘이 아니다.
코드
def counting_sort(array):
new_array = []
count = [0] * (max(array) + 1)
for i in array:
count[i] += 1
for i in range(len(count)):
for j in range(count[i]):
new_array.append(i)
return new_array시간 복잡도
데이터의 개수 N과 최대값의 크기 K에 대하여 O(N + K)
공간 복잡도
0과 999,999 단 두 개의 데이터에 대한 정렬을 수행한다면 매우 비효율적인 알고리즘이 될 것이다.
따라서 데이터의 크기가 작고 중복된 데이터가 많은 경우 효율적인 알고리즘이다.