Python으로 다양한 정렬(Sorting) 구현하기
본 포스팅도, Python으로 자료구조 구현하기 시리즈와 같이 기본에 충실하자! 컨셉의 포스팅이다.
Bubble Sort(버블 정렬), Insertion Sort(삽입 정렬), Selection Sort(선택 정렬), Merge Sort(합병 정렬), Quick Sort(퀵 정렬), Heap Sort(힙 정렬)의 6가지 기본 시리즈를 구현하였다.
각각의 Sorting 방식을 간단히 알아보고 구현 코드를 하나씩 알아보자.(원래 나눠서 포스팅을 올릴까하였으나, 그냥 한곳에 몰아놓는게 저도, 여러분들도 보기 편하실 것 같아 모았습니다.)
Bubble Sort(버블 정렬, 거품 정렬) 기초
- 앞에서부터 i번째 인덱스와 i+1번째 인덱스의 원소를 비교하며, 오름차순의 경우 i번째 인덱스의 원소가 i+1번째 인덱스의 원소보다 값이 클 경우, 두 값을 바꿔주는 방식으로 정렬을 진행
- 한번의 Iteration을 다 돌고 나면, 적어도 배열의 맨 끝에는 항상 "최댓값"이 가게 되므로, 배열의 길이가 N일 때, 최대 N번의 Iteration을 돌고나면 확정적으로 정렬이 완료된다.
- N번, N-1번, N-2번, ... 2번, 1번 순으로 연산이 수행되므로 Big-O는 (N^2)이다.
Insertion Sort(삽입 정렬) 기초
- 앞에서부터 스캔하며, i번째 원소가 들어갈 적절한 위치를 찾아서 삽입해주는 방식이라고 하여 삽입 정렬이라는 이름을 가지게 되었다.
- 오름차순의 경우, 왼쪽엔 i번째 원소보다 작은 값, 오른쪽엔 i번째 원소보다 큰 값을 만족하는 위치에 적절히 원소를 삽입하여 정렬을 진행하게 된다.
- 배열 arr가 주어졌을 때, arr[i-1, i-2, ..., 1, 0]의 원소를 탐색하면서 arr[i] 값보다 큰 원소들의 경우 한 칸씩 값을 밀어주고 (arr[j] = arr[j-1]), 최초로 자신보다 작은 값이 나오면 해당 인덱스 옆에 arr[i]를 넣어준다.
(말로 이해가 안간다면, GIF를 참고하고 코드를 보자.)
Selection Sort(선택 정렬) 기초
- 배열에서 가장 작은 값을 찾아서 앞에서부터 채워나가는 방식의 정렬이다.
- Bubble Sort에서는 한번의 Iteration을 돌 때 마다 최대값이 확정되었다면, 본 방식에서는 한번의 Iteration을 돌 때마다 최소값이 확정된다.
- 따라서, 길이가 N인 배열에 대해서 N, N-1, N-2, ..., 1, 0 번의 비교를 수행하게 되고, N^2의 시간 복잡도를 가진다.
Quick Sort(퀵 정렬) 기초
- 하나의 pivot값을 정하고, 이를 기준으로 pivot보다 작은 값을 왼쪽, pivot보다 큰 값을 오른쪽으로 배치한다.
- 그러면 최악의 경우에도 적어도 pivot 만큼은 정렬이 완료된다.
- pivot 보다 작은 값들에 대해 다시 pivot을 설정하여 정렬하고 큰 값에 대해서도 pivot을 설정하여 각각 정렬한다. 이러한 과정을 재귀적으로 반복하여 정렬을 진행한다.
- pivot의 기준값이 계속 이상하게 잡혀서 불균등하게 배열이 나눠지고, 이미 정렬된 부분에 대해 계속 Quick Sorting이 진행될 경우 최악이며, Big-O (N^2)이 되지만, 일반적으로 그럴 일이 거의 없으며, 평균적으로 NlogN의 시간복잡도를 가진다.
- Python의 sort가 퀵 정렬 기반으로 구현되어 있으며, 실제 실행시간이 다른 NlogN정렬방식보다 대부분의 경우에서 빠르다.
Merge Sort(합병 정렬) 기초
- Divide Conquer 방식으로 정렬 문제를 접근한 방식
- 배열을 동일한 비율로 쪼개고 (크기가 1일 때 까지), 이를 합쳐나가면서 정렬을 진행한다.
- 큰 배열을 작은 배열로 쪼개고, 문제를 해결 한후 합치는 방식
- 재귀적으로 구현이 가능
- NlogN의 시간복잡도를 가진다.
Heap Sort(힙 정렬) 기초
- Heap 자료구조를 활용한 정렬 방식이다.
- 최대, 최소 힙을 활용하여 내림차순, 오름차순의 정렬이 가능하다.
- 최소 힙의 Root는 항상 최소값이 되므로, 하나씩 pop해서 배열에 넣으면 자동적으로 정렬이 완료되는 효과
최종 성능 비교
Bubble Sort 구현
def HyunBubble(numbers):
for i in range(len(numbers), 1, -1):
for j in range(i-1):
if numbers[j] > numbers[j+1]:
numbers[j], numbers[j+1] = numbers[j+1], numbers[j]
return numbers
Insertion Sort 구현
def HyunInsertion(numbers):
for i in range(1, len(numbers)):
target = numbers[i]
for j in range(i, 0, -1):
if numbers[j-1] > target:
numbers[j], numbers[j-1] = numbers[j-1], numbers[j]
else:
break
return numbers
Selection Sort 구현
def HyunSelection(numbers):
for i in range(len(numbers)):
mn = 999999999
for j in range(i, len(numbers)):
if numbers[j] < mn:
mn = numbers[j]
mn_idx = j
numbers[i], numbers[mn_idx] = numbers[mn_idx], numbers[i]
return numbers
Quick Sort 구현
Quick Sort의 경우, 사실 in-place sort로 하면서 pivot을 바꾸고 하는 과정이 굉장히 많지만,
그냥 최대한 단순히 Pythonic 하게 구현하면 아래와 같다.
연산량이 조금 더 많아지긴 하겠지만, 그럼에도 불구하고 높은 성능을 가진다.
def HyunQuick(numbers):
if len(numbers) <= 1:
return numbers
pivot = numbers[len(numbers)//2]
left, right, equal = [], [], []
for num in numbers:
if num < pivot:
left.append(num)
elif num > pivot:
right.append(num)
else:
equal.append(num)
return HyunQuick(left) + equal + HyunQuick(right)
Merge Sort 구현
def HyunMerge(left, right):
result = []
i,j = 0,0
while True:
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
if i >= len(left) or j >= len(right):
break
result = result + right[j:] if i==len(left) else result + left[i:]
return result
def HyunMergeSort(numbers):
if len(numbers) <= 1:
return numbers
mid = len(numbers)//2
left = HyunMergeSort(numbers[:mid])
right = HyunMergeSort(numbers[mid:])
return HyunMerge(left, right)
Heap Sort 구현
Heap Sort의 경우, Python에서는 heapq 라이브러리를 통해 아주 쉽게 리스트를 최소힙으로 바꿀 수 있으므로, 오히려 구현 난이도가 쉬운편이다.
import heapq
def HyunHeap(numbers):
result = []
heapq.heapify(numbers)
while numbers:
result.append(heapq.heappop(numbers))
return result
'Development > Python' 카테고리의 다른 글
| [Python] N까지의 소수 구하기 최적화 방법 (0) | 2021.12.18 |
|---|---|
| [Python] 피보나치(Fibonacci) 수열 구하기 (0) | 2021.12.18 |
| [Python / 자료구조] Python으로 Queue 구현하기 (0) | 2021.12.18 |
| [Python / 자료구조] Python으로 Stack 구현하기 (0) | 2021.12.18 |
| [Python / Linux] tcmalloc: large alloc 2219589632 bytes == 0x8fa7a000 @ 0x7fb7e4433680 해결법 (0) | 2021.10.09 |
Hyunsoo Luke HA
석사를 마치고 현재는 Upstage에서 전문연구요원으로 활동중인 AI 개발자의 삽질 일지입니다! 이해한 내용을 정리하는 용도로 만들었으니, 틀린 내용이 있으면 자유롭게 의견 남겨주세요!