미루고 미루던 Merge Sort와 Quick Sort 개념을 정리하고 공부해보겠습니다.
1. Quick Sort
평균 Time complexity : O(nlogn)
최악의Time complexity : O(n^2)
특정 요소를 기준으로 크고 작은 그룹을 단계적으로 재배치/분할하여 정렬하는 알고리즘
(요소 pivot 선택기준은 가장 왼쪽/오른쪽/랜덤/중간 등 다양한 값으로 선택가능)
2. Merge Sort
평균 Time complexity : O(nlogn)
최악의Time complexity : O(nlogn)
비교 기반의 정렬 알고리즘 동일한 길이의 조각으로 조각이 한개가 될 때까지 나누고
다시 쪼개진 조각들을 짝지어 작은 숫자, 큰 숫자 순으로 정렬해가면서 결국 하나의 정렬로 합치는 알고리즘
3. Quick Sort / Merge Sort 차이점
두 가지 방법 모두 Divide and Conquer(분할정복) 알고리즘이라는 공통점이 있지만
Merge Sort 는 부분그룹을 동일한 길이를 기반으로 선정하고 , 그룹을 마지막 단계에 합치면서 정렬을 수행하지만
Quick Sort 는 그룹의 사이즈보다 비교 요소 대비 크고 작음을 기준으로 분할하고 그룹을 쪼개면서 정렬을 수행한다는 차이점이 있습니다.
따라서, Mergesort는 순차적인 접근에 용이한 linked list에 효율적으로 사용될 수 있고, Quicksort는 가끔 코딩 문제에 제약조건으로 추가적으로 메모리를 사용하지 않아야 한다는 제약조건이 있을 때 in-place 정렬을 위해서 사용되기에 좋습니다
4. Quick Sort / Merge Sort 파이썬 코드
(Geeks for Geeks 의 코드를 활용했습니다)
1) Quick Sort
def partition(array, low, high):
pivot = array[high] #가장 오른쪽값을 집어줍니다
i = low - 1
for j in range(low, high):
if array[j] <= pivot:
i = i + 1
(array[i], array[j]) = (array[j], array[i])
(array[i + 1], array[high]) = (array[high], array[i + 1])
return i + 1
def quickSort(array, low, high):
if low < high:
pi = partition(array, low, high)
quickSort(array, low, pi - 1)
quickSort(array, pi + 1, high)
2) Merge Sort
def mergeSort(arr):
if len(arr) > 1:
mid = len(arr)//2
mergeSort(arr[:mid])
mergeSort(arr[mid:])
i = j = k =0
while i < len(arr[:mid]) and j <len(arr[mid:]):
if arr[:mid][i] < arr[mid:][j]:
arr[k] = arr[:mid][i]
i += 1
else:
arr[k] = arr[mid:][j]
j += 1
k += 1
#좌우 비교 리스트의 길이가 다를 경우, 남은 값을 통해 정렬
while i < len(arr[:mid]):
arr[k] = arr[:mid][i]
i += 1
k += 1
while j < len(arr[mid:]):
arr[k] = arr[mid:][j]
j += 1
k += 1
Source:
https://www.programiz.com/dsa/merge-sort
https://www.geeksforgeeks.org/python-program-for-quicksort/
https://www.interviewkickstart.com/learn/quicksort-vs-merge-sort
'Data Structure & Algorithm' 카테고리의 다른 글
나만 알고 싶은 코딩테스트 템플릿/ 인터뷰 준비 사이트 (0) | 2023.04.13 |
---|---|
Monotonic Stack 개념 정리 (Push하고 Pop하고) (0) | 2022.12.01 |
필수 리눅스 (Linux) 명령어 정리 (0) | 2022.11.02 |
Greedy 탐욕 알고리즘 정리 (0) | 2022.10.17 |
Dynamic Programming _ Memoization 설명 및 적용 #2(숫자형) (0) | 2022.10.09 |
댓글