[알고리즘] 정렬
이것이 취업을 위한 코딩 테스트다. with 파이썬책을 참고하여 정리한 내용입니다.
정렬 알고리즘별 시간 복잡도
| 종류 | 평균 | 최악 | 최선 |
|---|---|---|---|
| 선택 정렬(Selection Sort) | $O(N^2)$ | $O(N^2)$ | $O(N^2)$ |
| 삽입 정렬(Insertion Sort) | $O(N^2)$ | $O(N^2)$ | $O(N)$ (데이터가 거의 정렬 되어 있으면) |
| 퀵 정렬(Quick Sort) | $O(NlogN)$ | $O(N^2)$ | $O(NlogN)$ |
| 계수 정렬(Count Sort) | $O(N+K)$ | $O(N+K)$ | $O(N+K)$ |
코딩 테스트에서 정렬 알고리즘이 사용되는 경우 3가지 유형
- 정렬 라이브러리로 풀 수 있는 문제 : 단순히 정렬 기법을 알고 있는지 물어보는 문제로 기본 정렬 라이브러리의 사용 방법을 숙지하고 있으면 어렵지 않게 풀 수 있다.
- 정렬 알고리즘의 원리에 대해서 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야 문제를 풀 수 있다.
- 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으로는 풀 수 없으며 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 거쳐야 풀 수 있다.
정렬 알고리즘
정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 어떤식으로든 정렬해서 사용하는 경우가 많기 때문에 프로그램 작성할 때 가장 많이 사용되는 알고리즘 중 하나이다. 면접에서도 많이 출제된다. 많은 정렬 알고리즘 중 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 알아보자.
선택 정렬(Selection Sort)
데이터가 무작위로 있을 때 '가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면 어떨까?' 이 방법은 가장 원시적인 방법으로 매번 ‘가장 작은 것을 선택’한다는 의미에서 선택 정렬(Selection Sort) 알고리즘이라고 한다.
선택 정렬의 시간 복잡도
선택 정렬은 N - 1 번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 구현 방식에 따라 사소한 오차는 있을 수 있지만, 연산 횟수는 $N + (N-1) + (N-2) + \cdots + 2$로 볼 수 있다. 따라서 근사치로 $N * (N+1) / 2$번의 연산을 수행한다고 가정하면 $N^2 + N / 2$로 표현할 수 있고, 빅오 표기법으로 $O(N^2)$이라고 표현할 수 있다. 소스코드에서 2중 반복문을 사용했으므로 $O(N^2)$이라고 이해할 수 있다. 알고리즘 수행 시간은 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려진다. 선택 정렬은 파이썬에 내장된 기본 정렬 라이브러리와 뒤에서 다룰 알고리즘과 비교했을 때 매우 비효율적이지만, 특정 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 잦으므로 선택 정렬 소스코드 형태에 익숙해질 필요는 있다.
소스코드
1
2
3
4
5
6
7
8
9
10
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
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] # swap
print(array)
1
2
# 출력
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
삽입 정렬(Insertion Sort)
'데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하면 어떨까?' 삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만 실행 시간 측면에서 더 효율적이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 ‘데이터가 거의 정렬 되어 있을 때’ 훨씬 효과적이다.
삽입 정렬은 특정한 데이터를 적절한 위치에 ‘삽입’한다는 의미에서 삽입 정렬(Insertion Sort)이라고 부른다. 그리고 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터에 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다. 삽입정렬은 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하기 때문에 두 번째 데이터부터 시작한다.
삽입 정렬의 시간 복잡도
삽입 정렬의 시간 복잡도는 선택 정렬과 마찬가지로 2중 반복문이 사용되었으므로 $O(N^2)$인데, 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다. 최선의 경우 $O(N)$의 시간 복잡도를 가진다. 퀵 정렬 알고리즘과 비교했을 때, 보통은 삽입 정렬이 비효율적이나 정렬이 거의 되어 있는 상황에서는 퀵 정렬 알고리즘보다 더 강력하다.
소스 코드
1
2
3
4
5
6
7
8
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
array[j], array[j - 1] = array[j - 1], array[j]
else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
break
퀵 정렬(Quick Sort)
'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?' 퀵 정렬(Quick Sort)은 위의 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 퀵 정렬과 비교할 만큼 빠른 알고리즘으로 ‘병합 정렬’ 알고리즘이 있다. 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬에는 피벗(Pivot)이 사용된다. 작은 숫자와 큰 숫자를 교환하기 위한 기준을 피벗이라고 한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분하는데, 책에서는 가장 대표적인 호어 분할(Hoare Partition) 방식을 기준으로 설명한다고 한다.
- 리스트에서 첫 번째 데이터를 피벗으로 정한다.
- 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
- 큰 데이터와 작은 데이터의 위치를 서로 교환한다.
- 왼쪽에서 찾는 값과 오른쪽에서 찾는 값의 위치가 서로 엇갈린 경우, 작은 데이터와 피벗의 위치를 서로 변경하여 분할을 수행한다.
- 피벗이 이동된 위치를 기준으로 왼쪽의 데이터는 모두 피벗보다 작고, 우측의 데이터는 모두 피벗보다 크다.
- 피벗을 기준으로 좌측, 우측의 데이터를 다시
1~4번의 과정으로 정렬한다.
해당 과정은 재귀 함수로 작성할 때 구현이 매우 간결해진다. 종료 조건은 리스트 데이터의 개수가 1개일 경우이다.
퀵 정렬의 시간 복잡도
퀵 정렬의 평균 시간 복잡도는 $O(NlogN)$이다. 최악의 경우엔 $O(N^2)$이다. 리스트의 가장 왼쪽 데이터를 피벗으로 삼을 때, ‘이미 데이터가 정렬되어 있는 경우’에는 매우 느리게 동작한다.
소스 코드
1) 널리 사용되고 있는 가장 직관적인 형태의 퀵 정렬 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
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: # 엇갈렸다면 작은 데이터와 피벗을 교체
array[right], array[pivot] = array[pivot], array[right]
else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left], array[right] = array[right], array[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right - 1)
quick_sort(array, right + 1, end)
quick_sort(array, 0, len(array)-1)
2) 파이썬의 장점을 살려 짧게 작성한 소스코드. 피벗과 데이터를 비교하는 연산 횟수가 증가하므로 시간 면에서는 조금 비효율적이지만, 더 직관적이고 기억하기 쉽다는 장점이 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
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))
계수 정렬(Count Sort)
계수 정렬(Count Sort) 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 모든 데이터가 양의 정수일 때, 데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 $O(N+K)$를 보장한다. 계수 정렬은 ‘데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때’만 사용할 수 있다. 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
이러한 특징을 가지는 이유는 ‘모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언’해야 하기 때문이다. 리스트의 인덱스가 모든 범위를 포함할 수 있도록 크기를 설정하고, 모든 데이터가 0이 되도록 초기화한다. 그다음 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.
계수 정렬의 시간 복잡도
모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, $O(N + K)$의 시간 복잡도를 가진다. 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있다. 사실상 현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)과 더불어 가장 빠르다고 볼 수 있다.
기수 정렬은 코딩 테스트에는 거의 출제되지 않는다고 한다.
계수 정렬의 공간 복잡도
떄에 따라서 심각한 비효율성을 초래할 수 있다. 예를 들어 데이터가 0과 999,999 2개만 존재한다고 했을 때, 리스트의 크기가 100만 개가 되도록 선언해야 한다. 따라서 항상 사용할 수 있는 알고리즘은 아니며, 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다. 예를 들어 성적의 경우 100점을 맞는 학생이 여러명일 수 있으므로 계수 정렬이 적합하다. 반면에 데이터의 특성을 파악하기 어렵다면 퀵 정렬을 이용하는 것이 유리하다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
1
2
# 출력
0 1 1 2 2 3 4 5 5 6 7 8 9 9
파이썬의 정렬 라이브러리
파이썬은 기본 정렬 라이브러인 sorted() 함수를 제공한다. sorted()는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 $O(NlogN)$을 보장한다는 특징이 있다.
정렬 라이브러리의 시간 복잡도
항상 최악의 경우에도 $O(NlogN)$을 보장한다. 이미 잘 작성된 함수이므로 우리가 직접 퀵 정렬을 구현할 때 보다 더욱더 효과적이다. 파이썬은 정확히는 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있다고 한다. 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.
실습 코드
1
2
3
4
5
6
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
result = sorted(array) # 정렬 된 리스트를 반환
array.sort() # 해당 리스트를 정렬
array = [('바나나', 2), ('사과', 5), ('당근', 3)]
result = sorted(array, key=lambda x: x[1]) # key 값을 줄 수 있음