해당 글은 '이것이 코딩테스트다 with 파이썬' (나동빈 지음) 책 내용을 정리한 것입니다.
정렬 알고리즘 개요
정렬(Sorting)이란 테이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
1. 선택 정렬
가장 작은 데이터를 선택해서 스왑(swap)을 통해 맨 앞부터 정렬하는 방법
1. 다음과 같은 배열이 있다고 가정하자
| 7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
|---|
2. 초기 단계에서는 전체 데이터 중 가장 작은 걸 선택에서 맨 앞에 '7'과 바꾼다.
| 7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| O | O |
3. 가장 작은 '0'은 올바른 위치에 정렬되었기 때문에 이를 제외한 숫자 중 가장 작은 것을 선택해 5와 바꾼다.
| 0 | 5 | 9 | 7 | 3 | 1 | 6 | 2 | 4 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| ✅ | O | O |
4. 위 과정을 반복하면 최종적으로 배열이 정렬된다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|
코드
def selection_sort():
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]
return array시간 복잡도
선택 정렬의 시간 복잡도를 구해보면 다음과 같다.
- 기본적으로 N-1 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야한다.
- 위 코드로 구현했을 때 연산 횟수
- N + (N - 1) + (N - 2) + ••• + 2 ≈ N(N+1)/2
- 빅오 표기법으로 간단히 O(N²) 로 표기할 수 있다.
2. 삽입 정렬
데이터를 하나씩 확인하여 적절한 위치에 삽입하는 방법
- 직관적으로 이해하기 쉽고 선택 정렬에 비해 구현은 어렵지만 실행 시간 측면에서 효율적이다.
- 필요할 때만 위치를 바꾸기 때문에 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.
⬆️는 들어갈 수 있는 위치를 의미한다.
1. 다음과 같은 배열이 있다고 가정하자
| 7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
|---|
2. 두번째부터 시작해서 '5'는 '7'보다 작기 때문에 '7' 앞인 첫번째 위치에 삽입한다.
| 7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ⬆️ | ⬆️ | O |
3. '7'은 올바른 위치에 있기 때문에 그대로 둔다. (다음 과정인 '9' 또한 변화가 없다.)
| 5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ⬆️ | ⬆️ | O | ⬆️ |
4. '0'은 '5', '7', '9' 중에 가장 작기 때문에 '5'앞인 첫번째 위치에 삽입된다.
| 5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ⬆️ | ⬆️ | ⬆️ | ⬆️ | O | ⬆️ |
5. '3'은 '0', '5', '7', '9' 중에 '0'보다 크고 '5'보다 작기 때문에 두번째 위치에 삽입된다.
| 0 | 5 | 7 | 9 | 3 | 1 | 6 | 2 | 4 | 8 | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ⬆️ | ⬆️ | ⬆️ | ⬆️ | ⬆️ | O | ⬆️ |
6. 위 과정을 반복하면 최종적으로 배열이 정렬된다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|
코드
def insertion_sort():
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
return array시간 복잡도
삽입 정렬의 시간복잡도는 O(N²)이다.(선택 정렬과 마찬가지로 반복문이 두번 수행된다.)
하지만 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작하고 최선의 경우 O(N)의 시간 복잡도를 가진다.
3. 퀵 정렬
퀵 정렬은 가장 많이 사용되는 알고리즘 중 하나이다.
- 기분 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다.
동작과정을 통해 설명하면 다음과 같다.
1. 다음과 같은 배열이 있다고 가정하자
| 5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
|---|
2. '5'을 p(pivot)로 설정하고 왼쪽에서부터 p보다 큰 데이터를 선택하고 오른쪽에서부터 p보다 작은 데이터를 선택한다. 이후 선택된 '7', '4'의 위치를 바꾼다.
| 5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| p | l | r |
- 위치 변환
| 5 | 4 | 9 | 0 | 3 | 1 | 6 | 2 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| p | l | r |
3. 다시 왼쪽(이때 바뀐 위치가 시작 기준이 된다.)에서부터 p보다 큰 데이터를 선택하고 오른쪽에서부터 p보다 작은 데이터를 선택한다. 이후 선택된 '9', '2'의 위치를 바꾼다.
| 5 | 4 | 9 | 0 | 3 | 1 | 6 | 2 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| p | l | r |
- 위치 변환
| 5 | 4 | 2 | 0 | 3 | 1 | 6 | 9 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| p | l | r |
4. 다시 과정을 반복하면 다음과 같이 r과 l의 위치가 엇갈린 상황이 발생한다. 그럼 p와 r의 위치를 바꿔준다. 이는 p가 전체 배열에서 있어야 할 위치가 되며 더 이상 위치의 변화를 주지 않는다.
| 5 | 4 | 2 | 0 | 3 | 1 | 6 | 9 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| p | r | l |
- 위치 변환
| 1 | 4 | 2 | 0 | 3 | 5 | 6 | 9 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| ✅ |
5. 과정 4에서 '5'를 기준으로 왼쪽과 오른쪽 부분으로 나누어 위와 같은 과정을 반복해서 수행한다.
코드
version 1
def quick_sort(array, start, end):
if start >= end:
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)위 코드는 퀵 정렬을 직관적으로 이해하기 쉽게 작성한 코드이다.
version 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)위 코드는 파이썬의 장점을 살려 리스트 컴프리헨션을 사용해 코드를 짧게 작성한 코드이다.
리스트 컴프리헨션이란?
직관적으로 리스트를 생성하는 방법으로 조건문을 사용하여 조건에 만족하는 값으로만 리스트를 생성할 수 있다.
코드에서 사용한 것을 보면 다음과 같다.
1. 배열을 pivot과 나머지를 나눠서 선언한다.
pivot = array[0]
tail = array[1:]2. tail(나머지)에서 리스트 컴프리헨션을 사용해 left와 right을 나눈다.
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]디버그로 실행하여 결과를 확인하면 다음과 같다.
pivot '7'를 기준으로 작은 배열의 값을 left, 큰 배열의 값은 right로 리스트가 생성된 것을 볼 수 있다.
3. 이후 나눈 부분 가운데 pivot을 넣고 나머지 정렬과정을 수행한다.
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
시간 복잡도
- 퀵 정렬의 평균적인 시간복잡도는 O(NlogN)이다.
- 이전 정렬에 비해 매우 빠른 편인데 이와 같은 시간복잡도를 가지는 이유는 다음과 같다.
- N이 8이라면 분할은 총 3번 이루어진다.
- 8 -> 4, 4
- 4 -> 2, 2
- 2 -> 1, 1
- 여기서 log의 밑은 2이며 8은 2의 3제곱이기 때문에 최종적으로 O(NlogN)의 시간 복잡도를 가지게 된다.
- 추가적으로 N이 1000일 때 logN은 약 10 정도되기 때문에 N에 비해서 logN은 매우 작은 수임을 알 수 있다.
4. 계수 정렬
계수 정렬은 특정 조건이 부합할때만 사용할 수 있는 방법이다.
- 데이터의 크기 범위가 제한더되어 정수 형태로 표현할 수 있을 때만 사용가능
- 일반적으로 데이터의 크기차이가 1,000,000을 넘지 않을 때 효과적
동작과정을 통해 설명하면 다음과 같다.
1. 다음과 같은 배열이 있다고 가정하자
| 7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 9 | 1 | 4 | 8 | 0 | 5 | 2 |
|---|
2. 데이터의 범주 크기에 맞는 배열을 선언한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
3. 데이터를 하나씩 확인해 몇번 등장하는지 카운트한다.
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
.. (과정 반복) ..
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 2 | 2 | 2 | 1 | 1 | 2 | 1 | 1 | 1 | 2 |
4. 횟수를 카운트한 배열의 출력을 반복한다.
0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
코드
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
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 = ' ')시간 복잡도
모든 데이터가 양의 정수인 상황에서 데이터 개수 N, 최대값의 크기를 K라 할 때, 계수 정렬의 시간 복잡도는 O(N+K)로 매우 빠른편이다.
하지만, 공간 복잡도 또한 O(N+K)이기 때문에 만약, 데이터가 '0', '999,999' 두개만 존재할 때도 1,000,000개의 리스트를 선언해야하는 비효율적인 상황이 발생할 수 있다.
[파이썬의 정렬 라이브러리]
sort(), sorted()등의 함수는 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다.
