항해99, 4주차 리스트 정렬

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. 총평

퀵소트, 머지소트 구현 및 이해