Today I learned
2022/01/31
회고록
1/31
항해 99, 알고리즘 3주차
교재 : 파이썬 알고리즘 인터뷰 / 이것이 코딩테스트다(동빈좌)
병합/퀵정렬(Sort)
1. 이론
퀵정렬
퀵 정렬(quick sort) 알고리즘의 구체적인 개념
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
퀵 정렬은 다음의 단계들로 이루어진다.
분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
병합정렬
합병 정렬(merge sort) 알고리즘의 구체적인 개념
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
합병 정렬은 다음의 단계들로 이루어진다.
분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
합병 정렬의 과정
추가적인 리스트가 필요하다.
각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.
2. 문제
문제 설명
Given the head of a linked list, return the list after sorting it in ascending order.
Example 1:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
https://leetcode.com/problems/sort-list/
3. MySol
- 3가지 방식의 Solution이 있다.
먼저 퀵소트 방식
class ListNode:
def __init__(self, val=None, next=None):
self.val = val
self.next = next
def partition(head, tail):
# if head.next is None:
# return head
pivot = tail.val
iNode = ListNode()
iNode.next = head
cur = head
while cur is not tail:
if cur.val <= pivot:
iNode = iNode.next
iNode.val, cur.val = cur.val, iNode.val
cur = cur.next
iNode.next.val, tail.val = tail.val, iNode.next.val
return iNode
def nodeQuickSort(head, tail, lv):
# if head is None or head.next is None or head is tail:
# return head
prevPivot = partition(head, tail)
if prevPivot.val is None:
return head
if head is prevPivot:
return head
nodeQuickSort(head, prevPivot, lv+1)
if prevPivot.next.next is tail or prevPivot.next is tail:
return head
nodeQuickSort(prevPivot.next.next, tail, lv+1)
return head
if __name__ == '__main__':
dummy = [4, 2, 1, 5, 3]
for i in reversed(range(len(dummy))):
if i + 1 != len(dummy):
node = ListNode(dummy[i], node)
else:
node = ListNode(dummy[i], None)
head = node
# 꼬리노드 구하기
tail = head
while tail.next is not None:
tail = tail.next
result = nodeQuickSort(head, tail, 0)
while True:
if result.next is not None:
print(f'{result.val}->', end="")
result = result.next
else:
print(f'{result.val}', end="")
break
머지소트방식
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeNode(l1, l2):
#l1이 더 크면 swap 다시 말해, 앞의 노드가 더 크면
if l1 and l2:
if l1.val > l2.val:
l1, l2 = l2, l1
#l1, l2가 연속된 단일노드가 아닌 경우
l1.next = mergeNode(l1.next, l2)
#l1 = Null, l2 = node 일 경우 l2 반환
#l1 = node, l2 = node 일 경우 l1 반환
#l1 = node, l2 = Null 일 경우 l1 반환
return l1 or l2
def mergeSort(head):
#head가 None이거나 head.next가 None인 경우 return head - 다시 말해 정렬할 것이 없다.
if not (head and head.next):
return head
#mid node를 구한다
#런너 기법 활용, slow는 한칸씩 나아가고, fast는 두칸씩 나아가서, fast가 tail에 도달할 때까지
slow = head
fast = head
mid = None
# head가 tail을 넘어서기 전 까지 while 반복
while fast and fast.next:
mid = slow
slow = slow.next
fast = fast.next.next
mid.next = None
l1 = mergeSort(head)
l2 = mergeSort(slow)
result = mergeNode(l1, l2)
return result
if __name__ == '__main__':
dummy = [4, 2, 1, 3]
for i in reversed(range(len(dummy))):
if i + 1 != len(dummy):
node = ListNode(dummy[i], node)
else:
node = ListNode(i, None)
head = node
for _ in range(len(dummy)-1):
node = node.next
result = mergeSort(head)
print(f'result: {result}')
노드 -> 리스트 -> 노드 변환 방식
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def nodeToList(head):
p = head
lst = []
#값만 리스트로 변경
while p:
lst.append(p.val)
p = p.next
#정렬
lst.sort()
p = head
#노드에 정렬된 리스트 값 삽입
for i in range(len(lst)):
p.val = lst[i]
p = p.next
return head
#끗
if __name__ == '__main__':
dummy = [4, 2, 1, 3]
for i in reversed(range(len(dummy))):
if i + 1 != len(dummy):
node = ListNode(dummy[i], node)
else:
node = ListNode(i, None)
head = node
for _ in range(len(dummy)-1):
node = node.next
result = nodeToList(head)
print(f'result: {result}')
4. 배운 점
- 노드를 이용하여 퀵소트 및 머지소트를 구현하며 각 정렬에 대한 이해도를 높였다.
- 퀵정렬은 해당 노드들을 정렬시, 최악시 O(n^2) 효율의 안정성이 좋지 못하여 좋은 알고리즘이 못된다.
- 병합정렬이 차라리 안정적 O(nlogn)이다.
- 하지만, 실제로 이런 문제가 만약 코테에 나온다면 무조건 값만 추출한 리스트로 변환하여 정렬 후 다시 집어넣는 방법을 사용하는게 낫다.
5. 총평
퀵소트, 머지소트 구현 및 이해
