이번 포스팅에서는 정렬 알고리즘 중 가장 유명한 Quick Sort(퀵 정렬), Merge Sort (병합 정렬)을 자료 구조적 관점에서의 설명과 풀이를 동반해서 정리해봤습니다.
이번 포스트의 이해를 돕기위한 알고리즘 문제는 아래 두 사이트의 문제를 기반으로 작성되었습니다.
• 퀵 정렬은 배열의 한 요소를 피벗(pivot)으로 선택한 후, 나머지 요소들을 피벗을 기준으로 작은 값과 큰 값으로 나누어 배열을 재배치합니다.
• 재배치 후, 피벗의 왼쪽에는 피벗보다 작은 값들이, 오른쪽에는 큰 값들이 위치하게 됩니다.
• 재귀적으로 왼쪽과 오른쪽 부분 배열에 대해 동일한 작업을 반복하여 전체 배열을 정렬합니다.
2. 단계별 알고리즘:
• 분할(Partitioning): 피벗을 기준으로 배열을 두 부분으로 나눕니다. 피벗보다 작은 값들은 왼쪽, 큰 값들은 오른쪽에 위치하게 됩니다.
• 정복(Conquer): 분할된 배열에 대해 재귀적으로 퀵 정렬을 수행합니다.
• 결합(Combine): 분할된 배열을 정렬할 필요가 없으며, 재귀 호출이 끝나면 이미 배열은 정렬되어 있습니다.
4. 피벗(pivot) 값 선택:
• 피벗은 배열의 첫 번째 요소, 마지막 요소, 임의의 요소 또는 중간 값으로 선택할 수 있습니다. 피벗 선택 전략에 따라 성능이 달라질 수 있습니다.
• 일반적으로, 무작위 피벗 선택 또는 중간 값 피벗 선택이 최악의 경우를 방지하는데 유리합니다.
평균 시간 복잡도: • 퀵 정렬의 평균 시간 복잡도는 O(n log n)입니다. 데이터가 균등하게 분할되는 경우, 각 분할마다 정렬해야 하는 크기가 절반씩 줄어들 경우에는 해당 성능을 나타냅니다.
최악의 시간 복잡도: • 최악의 경우 시간 복잡도는 O(n^2)입니다. 피벗 선택이 비효율적일 경우, 분할이 극단적으로 비대칭적으로 이루어질 경우에 발생합니다.
✅ [Quick-sort] Python RAW CODE 🔽
import sys
def quick_sort(arr, start, end):
if start < end:
pivot_index = partition(arr, start, end)
quick_sort(arr, start, pivot_index - 1) # 왼쪽 부분 정렬
quick_sort(arr, pivot_index + 1, end) # 오른쪽 부분 정렬
def partition(arr, start, end):
pivot_index = (start + end) // 2
pivot_value = arr[pivot_index]
_swap(arr, start, pivot_index)
left = start + 1
right = end
while left <= right:
while left <= right and arr[left] < pivot_value:
left += 1
while left <= right and arr[right] > pivot_value:
right -= 1
if left <= right:
_swap(arr, left, right)
left += 1
right -= 1
_swap(arr, start, right)
return right
def _swap(arr, first, second):
arr[first], arr[second] = arr[second], arr[first]
if __name__ == "__main__":
inputs = sys.stdin.readline
n = int(inputs())
arr = list(map(int, inputs().split()))
quick_sort(arr, 0, len(arr) - 1) # 퀵 정렬 실행
print(" ".join(map(str, arr))) # 정렬된 결과 출력
✅ [Quick-sort] Pythonic 한 CODE 🔽
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
lesser_arr, equal_arr, greater_arr = [], [], []
for num in arr:
if num < pivot:
lesser_arr.append(num)
elif num > pivot:
greater_arr.append(num)
else:
equal_arr.append(num)
return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)
✅ [Quick-sort] Pythonic 하게 최적화한 CODE 🔽
def quick_sort(arr):
def sort(low, high):
if high <= low:
return
mid = partition(low, high)
sort(low, mid - 1)
sort(mid, high)
def partition(low, high):
pivot = arr[(low + high) // 2]
while low <= high:
while arr[low] < pivot:
low += 1
while arr[high] > pivot:
high -= 1
if low <= high:
arr[low], arr[high] = arr[high], arr[low]
low, high = low + 1, high - 1
return low
return sort(0, len(arr) - 1)
이해를 쉽게 돕기 위해서, BOJ 의 문제의 풀이를 기반으로, 정렬되어 있지 않는 수를 가진 배열로 Quick Sort를 그림으로 설명해보겠습니다.
inputs = sys.stdin.readline
n = int(inputs())
위의 input에 [3,7,8,5,2,1,9,5,4]의 값이 입력된 Array를 기준으로, Pivot의 경우 중앙 값 (len(array)//2)로 지정한 뒤, Pivot 값을 맨 끝 element와 교환합니다.
이때, Pointer 두개를 기준으로 Index를 왼쪽, 오른쪽으로 이동해가며, Pivot 값 보다 작은 경우와 큰 경우의 값을 Swiching 합니다.
while left <= right:
while left <= right and arr[left] < pivot_value:
left += 1
while left <= right and arr[right] > pivot_value:
right -= 1
if left <= right:
_swap(arr, left, right)
left += 1
right -= 1
_swap(arr, start, right)
return right
def _swap(arr, first, second):
arr[first], arr[second] = arr[second], arr[first]
위의 Code의 Pointer 2개를 기준으로 left : pivot 값 보다 큰 값, Right : pivot 값 보다 작은 값을 찾습니다.
해당 조건의 만족하는 경우 _swap 함수를 통해서, 큰 값과 작은 값을 교환합니다. = 작은 값을 왼쪽으로 몰아넣기 위해
이후 Loop을 반복하다가, left index의 pointer의 값이 right 보다 같거나, 커질 경우, while loop을 종료합니다.
pointer 가 교차되었다는 의미는, 이미 작은 값, 큰값에 대한 교환이 완료된 index이기 때문입니다.
• 병합 정렬은 한개의 배열을 두개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한 다음, 정렬된 부분 리스트를 합하여, 전체가 정렬된 리스트를 얻습니다.
• 보통 재귀함수를 사용해, 배열 안의 인자 값이 1개일 때 까지 리스트를 분할하게 되고, 1개 일 경우에 분할을 멈추게 됩니다.
2. 단계별 알고리즘:
• 분할(Divide): 배열, 입력 리스트를 같은 크기의 2개의 부분 리스트로 분할합니다.
• 정복(Conquer): 2개로 분할된 배열의 분할이 멈추면, 부분 리스트 인자의 정렬을 수행합니다. (이때 분할이 멈추는 경우는 리스트 크기가 1일 경우)
• 결합(Combine): 정렬된 부분 리시트를 하나의 리스트로 통합합니다.
평균/최악 시간 복잡도: • 병합 정렬의 평균 및 최악의 시간 복잡도는 동일하게 O(n log n)입니다. 모든 경우에서의 시간 복잡도가 동일하기에, 안정 정렬이라고 불립니다.
✅ [Merge-sort] Python CODE 🔽
def merge_sort(arr:list[int]) -> None:
if len(arr) <= 1: # 배열의 크기가 1이 될 경우 재귀 종료
return
L_ARR = arr[:len(arr)//2] # 왼쪽 배열은 중간 값 이전 값
R_ARR = arr[len(arr)//2:] # 오른쪽 배열은 중간 값 이후 값
merge_sort(L_ARR) # 재귀를 실행시켜 각 인자가 1개씩으로 분할
merge_sort(R_ARR) # 재귀를 실행시켜 각 인자가 1개씩으로 분할
L_index, R_index, merge_index = 0, 0, 0
while L_index < len(L_ARR) and R_index < len(R_ARR):
if L_ARR[L_index] < R_ARR[R_index]:
arr[merge_index] = L_ARR[L_index]
L_index += 1
else:
arr[merge_index] = R_ARR[R_index]
R_index += 1
merge_index += 1
while L_index < len(L_ARR):
arr[merge_index] = L_ARR[L_index]
L_index += 1
merge_index += 1
while R_index < len(R_ARR):
arr[merge_index] = R_ARR[R_index]
R_index += 1
merge_index += 1
if __name__ == "__main__":
input = sys.stdin.readline
N, K = map(int, input().split()) ## N , K 에 해당하는 입력 값 받기
arr = list(map(int, input().split())) # arr 받기
merge_sort(arr) # arr를 merge sort
print(arr[K-1])
이해를 쉽게 돕기 위해서, BOJ 의 문제의 풀이를 기반으로, 정렬되어 있지 않는 수를 가진 배열로 Merge Sort를 그림으로 설명해보겠습니다.
위의 input에 [9,12,20,25,12,14,21]의 값이 입력된 Array를 기준으로, 1(len(array)//2)로 나눈 값 이전, 이후로 Array를 2개로 분할 합니다.
이때, 재귀되면서 분할된 Array의 인자 값의 개수가 1개일 경우, 재귀와, 분할을 종료합니다.
위의 그림으로 설명되면, 9, 12, 20, 25, 12 , 14, 21이 각각 하나의 Array에 속해 있는 상태 입니다.
퀵 정렬과 알고리즘이 동일하나, 퀵 정렬의 경우 배열이 이미 정렬 되어있거나, Pivot 값이 최소 혹은 최대 원소일 경우, O(n^2)의 시간 복잡도를 갖습니다.
따라서 위의 예시와 같은 배열에서 사용하기엔 부적합합니다., 보통은 퀵 정렬의 진화형인 QuickSelect를 사용하거나, Merge Sort를 사용하죠.
✅ Quick-Select Python Code 🔽
import sys
import random
def q_select(arr:list[int], K:int):
if len(arr) == 1:
return arr[0]
pivot = random.choice(arr) # random 함수를 사용해서, 무작위의 pivot 값을 지정 합니다.
left = [x for x in nums if x > pivot]
mid = [x for x in nums if x == pivot]
right = [x for x in nums if x < pivot]
if K <= len(left):
return q_select(left, K)
elif K <= len(left) + len(middle):
return pivot
else:
return q_select(right, k - len(left) - len(middle))
if __name__ == "__main__":
inputs = sys.stdin.readline
n, k = map(int, inputs().split())
arr = list(map(int, inputs().split()))
result = q_select(arr, k)
로직은 퀵정렬과 동일합니다. 다만 효율적으로 배열의 구분 부분을 list comprehension 으로 구현했습니다.
결론적으로 가장 중요한 부분은, K 라는 index의 위치와 array list의 len = element 갯수를 이용해서 targer index를 구하는 로직입니다.
해당 알고리즘을 사용하는 경우는 특정 배열에서 특정 INDEX를 찾아야 할 때 등 모든 배열을 다 확인하는 것이 비효율적인 경우 입니다.
left = [x for x in nums if x > pivot] # element 값이 pivot 보다 작은 경우
mid = [x for x in nums if x == pivot] # element 값이 pivot과 같은 경우는
right = [x for x in nums if x < pivot] # element 값이 pivot 보다 큰 경우
if K <= len(left): # Target k가 index의 경우 arr의 갯수로 확인
return q_select(left, K) # 이 경우 k 보다 left arr의 개수가 작으니 그 안에 target num이 있는 경우
elif K <= len(left) + len(middle): # 이 경우 pivot 값을 더 했을 때 동일하다면 pivot 값이 해당 target num 인 경우
return pivot
else: # 아니면, 더 큰것이기 때문에, target num k의 숫자도 그만큼 감소 시킨 뒤 Recursive
return q_select(right, k - len(left) - len(middle))
먼저 숫자의 피벗 및 분할요소를 피벗보다 작거나, 같거나, 큰 세부분으로 선택합니다. (이분 되서 빠른 재귀 종료가 가능합니다)
다음으로는 각 그룹 (list) 별로 몇개의 원소가 존재하는지 살펴봅니다 (len)
가장 작은 것, 작은것 + 같은것 / 두가지 조건으로 찾아야 하는 인덱스와 비교해보면, 그 길이보다 작으면 왼쪽, 크면 오른족에 해당 인덱스가 존재합니다.
![[Algorithm] Python으로 구현하는 (QuickSort, MergeSort) Algorithm](/static/516076847d6abd57f064d50daeb89c7c/a161f/Python_Algorithm.webp)
![[Develop] Python을 사용한 Azure Chatbot을 생성 및 Teams 연결 과정](/static/3565f14618bf3b71db002582aac29fe5/48bb0/chatbot.webp)
![[DataBase CS] 엔진 수준의 Lock, MVCC, 트랜잭션 격리 수준 (Transaction Isolation Level)](/static/504cfd30be29ceed59baa1c00f05baf3/a161f/transaction1.webp)
![[DataBase CS] 데이터 정규화와 Star Schema, Snow Flake 모델링](/static/2386eea5623aa3d738174a26de2e1cf1/a161f/SnowFlake.webp)
![[LINUX] 효율적인 리눅스 로그 관리: SYSLOGD와 RSYSLOG](/static/8e9b34409d4f90e094c3bb4266230bf0/99344/syslog.webp)
![[BASH] 명령줄 인수와 특수 매개변수 (bash Special Parameters)](/static/72faa2d11e0344f488712711388f9b26/b38eb/argument.webp)
![[LINUX] sed 명령어 사용법 : 변수 사용과 패턴 매칭, 실제 예제 패턴](/static/4e49fa0ae430646dac5926a7e97aade9/a161f/FreeBSD_10_vi_RC_Firewall.webp)