병합 정렬, 삽입 정렬 (Python Algorithm interview 17장)

파이썬 알고리즘 인터뷰 17장을 정리한 내용입니다.

합병 정렬

출처: https://holypython.com/merge-sort-algorithm-python-code/

• 비교 기반 정렬 알고리즘으로 분할 정복 알고리즘 중 하나이다
• 입력된 배열을 같은 길이의 2개 부분으로 분할한다
• 분할된 부분 배열을 정렬하고 결합한다.

#58 리스트 정렬

p.489

• 연결 리스트를 O(nlogn)에 정렬하라

병합 정렬

• 병합 정렬의 분할 정복을 위해서는 중앙을 분할해야 한다
• 연결 리스트는 전체 길이를 알 수 없기 때문에 Runner 기법을 활용해서 중앙을 찾아낸다

# Runner
half, slow, fast = None, head, head
while fast and fast.next:
    half, slow, fast = slow, slow.next, fast.next.next
half.next = None

• slow는 한 칸씩, fast는 두 칸씩 앞으로 이동한다
• fast가 맨 끝에 도달하면 slow는 중앙에 도착한다
• half는 slow의 바로 이전 값으로 한다
• half.next = None 으로 half 위치를 기준으로 연결 리스트 관계를 끊는다.

def sortList(head: ListNode) -> ListNode:

	l1 = sortList(head)
	l2 = sortList(slow)

	return mergeTwolist(l1, l2)

• 재귀 호출을 통해 각 요소들을 단일 원소로 쪼개준다

def mergeTwolist(l1: ListNode, l2: ListNode) -> ListNode:
    if l1 and l2:
        if l1.val > l2.val:
            l1, l2 = l2, l1
        l1.next = mergeTwolist(l1.next, l2)

    return l1 or l2

• mergeTwolist 를 사용하여 각 원소들을 크기를 비교하면서 이어 붙여준다
• return l1 or l2 는 l1 에 값이 있다면 l1 을 반환하고 None 인 경우에는 l2 를 리턴한다

내장 함수를 이용하는 방법

• 파이썬의 기본 라이브러리의 정렬 함수를 사용하면 속도가 가장 빠르다
• C로 구현한 Timesort를 사용하기 때문에 효율적이다
• 면접에서는 병합 정렬을 설명하는 것이 좋다

def sortList_(head: ListNode) -> ListNode:
    p = head
    lst: list = []
    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

• 리스트에 연결 리스트 요소들을 넣고 sort() 를 이용해 정렬해 준다
• p = head 로 연결 리스트를 초기화 한 다음 리스트에 저장된 요소들을 연결 리스트로 이어준다.
• 내장 함수를 이용하는 방법이 효율적이다.

---

삽입 정렬

출처: 위키백과

• 삽입 정렬은 두 번째 자료부터 시작해서 그 앞 자료들과 비교하여 삽입할 위치를 정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘
• 처음 key 값은 두 번째 자료부터 정렬을 시작한다.

#60 삽입 정렬 리스트

p.500

• 연결 리스트를 삽입 정렬로 정렬하라

삽입 정렬

• 정렬을 해야 할 대상과 정렬을 끝낸 대상 두 그룹으로 나눈다
• head 는 정렬을 해야 할 대상이고 cur 은 정렬을 끝낸 대상으로 정한다

cur = parent = listnode(None)
while head:
    while cur.next and cur.next.val < head.val:
        cur = cur.next

• cur 은 정렬을 끝낸 연결 리스트를 추가해 갈것이고 parent 는 루트를 가리키게 한다

cur.next, head.next, head = head, cur.next, head.next
cur = parent # cur이 head보다 클 경우만 실행되면 된다.

삽입 정렬의 비교 조건 개선

def insertionSort_(head: listnode) -> listnode:
    cur = parent = listnode(0)
    while head:
        while cur.next and cur.next.val < head.val:
            cur = cur.next

        cur.next, head.next, head = head, cur.next, head.next
        if head and cur.val > head.val: # 위 코드와 다른 부분
            cur = parent
    return cur.next

• cur이 head보다 클 경우만 실행되면 된다.