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

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

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

출처 : 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

삽입 정렬에서 효율을 높여볼 생각을 못해봤다

단일 연결리스트에서 활용해볼 수 있는 재밌는 방법인 것 같다

from http://pythaac.tistory.com/145 by ccl(A) rewrite - 2021-08-07 03:26:46