병합 정렬
병합 정렬(merge sort)은 분할 정복(divide and conquer) 알고리즘을 사용하여 정렬하는 알고리즘입니다.
병합 정렬은 다음과 같은 단계로 진행됩니다.
입력 배열을 중간 지점으로 나눕니다.
각 부분 배열을 재귀적으로 병합 정렬합니다.
두 부분 배열을 합쳐 정렬된 배열을 생성합니다.
def mSort(ns):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2
leftNums = mSort(ns[:midIdx])
rightNums = mSort(ns[midIdx:len(ns)])
mergeNums = []
leftIdx = 0
rightIdx = 0
while leftIdx < len(leftNums) and rightIdx < len(rightNums):
if leftNums[leftIdx] < rightNums[rightIdx]:
mergeNums.append(leftNums[leftIdx])
leftIdx += 1
else:
mergeNums.append(rightNums[rightIdx])
rightIdx += 1
mergeNums = mergeNums + leftNums[leftIdx:]
mergeNums = mergeNums + rightNums[rightIdx:]
return mergeNums
nums = [8, 1, 4, 3, 2, 5, 10, 6]
print(f'mSort(nums) : {mSort(nums)}')mSort(nums)를 호출합니다.
리스트의 길이가 8로 1보다 크기 때문에, 리스트를 반으로 나눕니다.
왼쪽 부분 리스트 [8, 1, 4, 3]와 오른쪽 부분 리스트 [2, 5, 10, 6]을 각각 정렬하기 위해 mSort 재귀함수로 호출합니다.
위 과정을 반복하여 최종적으로 길이가 1인 부분 리스트로 나눠집니다.
정렬된 부분 리스트를 합치는 과정에서, 작은 값을 선택하여 mergeNums에 추가합니다.
마지막으로 남은 부분 리스트를 mergeNums에 추가합니다.
최종적으로 정렬된 리스트가 반환되고, print(f'mSort(nums) : {mSort(nums)}')에 의해 출력됩니다.
이를 통해 입력 리스트 nums가 병합정렬에 의해 정렬된 결과를 확인할 수 있습니다.
퀵 정렬
퀵 정렬(quick sort)은 분할 정복(divide and conquer) 알고리즘을 사용하여 정렬하는 알고리즘입니다.
퀵 정렬은 다음과 같은 단계로 진행됩니다.
입력 배열에서 피벗(pivot)을 선택합니다.
피벗을 기준으로 배열을 두 부분으로 분할합니다.
각 부분 배열을 재귀적으로 퀵 정렬합니다.
def qsort(ns):
if len(ns) < 2:
return ns
midIdx = len(ns) // 2
midVal = ns[midIdx]
smallNums = []; sameNums = []; bigNums = []
for i in ns:
if i < midVal:
smallNums.append(i)
elif i == midVal:
sameNums.append(i)
else:
bigNums.append(i)
return qsort(smallNums) + sameNums + qsort(bigNums)
nums = [8, 1, 4, 3, 2, 5, 4, 10, 6, 8]
quick = qsort(nums)
print(f'quick : {quick}')qsort(nums)를 호출합니다.
리스트의 길이가 10으로 1보다 크기 때문에, 피벗 값을 선택하고 작은 값, 같은 값, 큰 값으로 나눕니다.
피벗 값: 4 (중앙 값)
작은 값: [1, 3, 2]
같은 값: [4, 4, 8, 8]
큰 값: [5, 10, 6]
작은 값, 같은 값, 큰 값 각각에 대해 qsort 함수를 재귀적으로 호출합니다.
qsort([1, 3, 2]): 길이가 3이므로 더 이상 나눌 수 없어 그대로 반환
qsort([5, 10, 6]): 길이가 3이므로 더 이상 나눌 수 없어 그대로 반환
작은 값 + 같은 값 + 큰 값 순서로 합쳐진 최종 결과를 반환합니다.
[1, 2, 3] + [4, 4, 8, 8] + [5, 6, 10]
최종 결과: [1, 2, 3, 4, 4, 8, 8, 5, 6, 10]
이렇게 퀵소트는 피벗을 기준으로 나누고, 작은 값과 큰 값을 각각 재귀적으로 정렬하여 최종적으로 정렬된 리스트를 얻게 됩니다.
알고리즘 파트 후기
이것으로 알고리즘 파트 강의는 전부 들었으나 아직 개념정리가 덜된거 같아 문제 풀이는 EDA와 같이 해보도록 하겠습니다.
