정렬 알고리즘(Sorting Algorithm)
어떤 정렬을 쓰냐에 따라 프로그램의 효율성이 좌지우지될 수 있다.
정렬은 면접 단골 질문이기도 하다.
버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬, 병합 정렬, 힙 정렬 정도까지는 알고 있으면 좋다.
버블 정렬(Bubble Sort)
왼쪽부터 자기 오른쪽 요소와 비교해 본인이 더 크면 swap 한 번의 순회마다 큰(오른쪽) 자리의 요소가 정해진다.
코드
def bubble_sort(array):
for i in range(0, len(array)):
for j in range(1, len(array)-i):
if array[j-1] > array[j]:
array[j-1], array[j] = array[j], array[j-1]시간 복잡도
작다고 멈추고 이런 게 없기 때문에 최선의 경우, 최악의 경우 모두 동일하게 O(N^2)
선택 정렬(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)
2번째 데이터부터 시작하여, 자기 왼쪽의 데이터를 확인해 더 크다면 swap, 자신보다 작다면 멈춤으로써 왼쪽부터 정렬을 완성해가는 방식 한 번의 순회마다 왼쪽의 정렬된 데이터 수가 1개씩 늘어난다.
삽입 정렬은 움직일 데이터를 기준으로 내 왼쪽 애들의 순서는 모두 정렬된 상태라는 전제(실제로 그러하다)로 동작한다.
코드
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)파이썬에 특화된 코드
어쨌든 피벗을 정하고 피벗보다 왼쪽에는 작은 데이터, 오른쪽에는 큰 데이터가 오게 만든 뒤 재귀로 각 배열에 대해 동일한 알고리즘을 적용한다면 퀵소트는 돌아간다.
아래는 이러한 점에서 착안한 파이썬에 특화된 코드이다.
위와 달리 배열 자체를 정렬하는 것이 아니라 정렬한 배열을 반환한다.
def quick_sort(array):
if len(array) <= 1: # 두 개부터 재귀에 들어가므로
return array
pivot = array[0]
tail = array[1:] # 이 문장이 반드시 유효해지는 것 (1개 이하면 에러 발생)
left = [i for i in tail if i < pivot]
right = [i for i in tail if i >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)시간 복잡도
최선의 경우
항상 피벗이 정중앙에 위치하게 될 때
즉, 항상 정중앙을 기준으로 배열을 쪼개 재귀에 들어가는 경우
이 때 시간 복잡도는
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에 대하여,
배열 돌면서 각 요소별로 count 증가 O(N)
0부터 최대값 K까지 돌면서 순서대로 새 배열에 삽입 O(K)
두 개를 각각 독립적으로 수행하므로 O(N + K)
공간 복잡도
0과 999,999 단 두 개의 데이터에 대한 정렬을 수행한다면 매우 비효율적인 알고리즘이 될 것이다.
그러나 데이터의 크기가 작고 중복된 데이터가 많은 경우에는 효율적인 알고리즘이다.
따라서, 보통 중복 데이터가 있고 이들의 개수를 세야 하는 경우 해당 알고리즘을 사용한다.
자주 등장하는 유형
리스트 자료가 주어지며 각 값이 우선도의 의미를 갖는 경우
우선도의 의미를 갖는 경우정렬을 통해 우선순위를 기점으로 데이터를 처리해야 하는 문제에 해당한다.
리스트 내부의 리스트 or 튜플 (여러 개의 정렬 조건)
시간 복잡도를 잘 고려해야 한다. 내가 반복문 중첩을 해도 될지 아닐지 등을 잘 생각할 것
정렬 조건 간의 우선순위가 있는 경우 역순으로 적용한다. (즉, 우선도가 낮은 정렬 조건을 먼저 적용)
이유: 먼저 적용하는 조건에서 같은 우선도를 갖는 애들에 다음 조건을 적용하는 것이므로 먼저 적용할 조건을 나중에 적용하면 앞에서 정렬된 (같은 우선도를 가질) 애들의 순서에는 영향을 미치지 않는다.
Last updated