[파이썬 알고리즘 인터뷰][정렬] 삽입 정렬 리스트

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

단일 연결리스트의 삽입정렬 구현

 

책에서 구현된 코드

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

 

기억해야할 기법

• return parent.next
  
  • 의미 없는 빈 노드를 생성하고 next부터 데이터를 채우면 양끝삽입 처리가 쉬워짐
• 삽입 정렬 개선
  • 마지막으로 삽입한 위치에서 다음 비교할 값이 더 크면 처음부터 비교할 필요가 없음

 

내가 구현한 코드

# 연결리스트로 구현
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
    	# head의 값으로 연결리스트 첫번째 노드 생성
        root = ListNode(head.val)
        # 입력된 연결리스트의 값으로 새로운 노드 생성
        while head.next:
            head = head.next
            nw_node = ListNode(head.val)
            # 새로운 노드가 가장 작은 노드일 경우, 첫번째 노드로 설정
            if nw_node.val < root.val:
                nw_node.next, root = root, nw_node
            else:
            	# 더 큰 값의 노드 or 리스트의 마지막에 도달할 때까지 next 후 삽입
                crnt = root
                while crnt.next and crnt.next.val < nw_node.val:
                    crnt = crnt.next
                crnt.next, nw_node.next = nw_node, crnt.next

        return root

# 배열로 구현
class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        arr = [head.val]
        crnt = head
        # 연결리스트 순차탐색
        while crnt.next:
            crnt = crnt.next
            val = crnt.val
            # arr 배열에 삽입 정렬
            i = 0
            while i < len(arr):
                if val < arr[i]:
                    break
                i += 1
            arr.insert(i, val)
        # 연결리스트에 값 업데이트
        crnt = head
        for val in arr:
            crnt.val = val
            crnt = crnt.next

        return head

• 삽입 정렬에서 효율을 높여볼 생각을 못해봤다
• 단일 연결리스트에서 활용해볼 수 있는 재밌는 방법인 것 같다