60. Insertion Sort List

리트코드

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

1. 삽입 정렬 (1936ms)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        #초깃값 변경
        
        cur = parent = ListNode(None)
        while head:
            while cur.next and cur.next.val < head.val:
                cur = cur.next
                
            cur.next, head.next, head = head, cur.next, head.next
           
            cur = parent
        return parent.next

• 입력값 4 -> 2 -> 1 -> 3 연결 리스트이고 head는 루트 노드인 4를 가리킬 때의 삽입 정렬 과정

• 삽입 정렬은 정렬을 해야 할 대상과 끝낸 대상, 두 그룹으로 나눠 진행한다.

  • head는 정렬을 해야 할 대상

  • cur는 정렬을 끝낸 대상으로 정한다.

• 정렬을 해야 할 대상 head를 반복한다.

  • 먼저 cur와 parent는 빈 노드로 정한다.

  • cur에는 정렬을 끝낸 연결 리스트를 추가해줄 것이고, parent는 계속 그 위치에 두어 사실상 루트를 가리키게 한다.

  • cur는 이미 정렬된 상태 이므로, 정렬을 해야 할 대상 head와 비교하면서 더 작다면 계속 cur.next를 이용해 다음으로 이동한다.

  • 이제 정렬이 필요한 위치, 즉 cur에 삽입될 위치를 찾았다면 cur 연결 리스트에 추가한다.

• 찾은 cur위치 다음에 head가 들어가고, head.next에는 cur.next를 연결해 계속 이어지게 한다.

  • 다음번 head는 head.next로 차례를 이어받는다.

  • 이후에는 cur = parent를 통해 다시 처음으로 되돌아가며, 차례대로 다시 비교하게 된다.

  • 그림에서는 cur의 마지막 노드는 2 -> 3 -> 4 형태가 되는데, 이는 입력값에서 유일하게 그 직전 값인 1 보다 head의 값인 3이 더 크기 때문이다.

  • 따라서 cur = cur.next로 작거나 같아질 때까지 계속 전진한다.

  • 이후에 head는 None이 되면서 비교가 끝나게 된다.

2. 삽입 정렬의 비교 조건 개선 (180ms)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, 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
            
            #필요한 경우에만 cur 포인터가 되돌아가도록 처리
            if head and cur.val > head.val:
                cur = parent
        return parent.next

• 풀이 1은 제대로 된 삽입 정렬 풀이가 아니다. 왜냐하면 삽입 정렬은 정답 셋과 정답이 아닌 셋을 비교할 때, 정답 셋의 가장 큰 값부터 왼쪽 방향으로 내려가며 스왑되는 위치를 찾는다.

  • 그러나, 이 문제의 경우 연결 리스트이고 게다가 이중 연결 리스트도 아니기 때문에, 큰 값에서부터 작은 값까지 거꾸로 거슬러 내려가는 게 사실상 불가능하다.

  • 그러다 보니 매번 가장 작은 값부터 차례대로 크기 비교를 하는 매우 비효율적인 연산이 수행된다.

• 그럼 어떻게 이 부분을 개선할 수 있을까?

  cur = parent

  • 다음번 head를 비교할 때 정렬된 노드인 cur도 다시 맨 처음으로 되돌아가라는 명령인데, 만약 다음 번 head 도 cur보다 작은 상태라면 굳이 되돌아가지 않아도 되지 않을까?

  • 돌아가지 않고 그 상태에서 계속 비교를 진행할 수 있다면, 비교 횟수를 획기적으로 줄일 수 있을 것 같다.

  • 거꾸로 비교할 수 없는 대신, 필요할 때만 돌아가는 형태로 개선할 수 있을 것이고, 되돌아가는 경우는 cur가 head보다 클 때만 하면 될 것 같다.

• 이동한 다음번 head가 None일 수도 있기 때문에 존재 여부를 확인하고 cur와 head의 값을 비교해 꼭 필요한 경우에만 되돌아가게 했다.

  • cur.val이 head.val 보다 작다면, 그 다음 반복 때 while 구문이 실행되지 않고 바로 교환이 진행될 것이므로, 불피요한 while 반복은 진행하지 않아도 된다..

• 단 한 줄의 조건문으로 기존 대비 10배 이상 성능을 높일 수 있었다.

  이처럼 약간의 최적화만 거쳐도 성능을 획기적으로 개선할 수 있으며, 얼마든지 알고리즘을 최적화할 수 있다.