[자료구조] 삽입 정렬(Insertion Sort)

목차

정렬 종류
비교 기반 정렬(Comparison Based Sorts) 
- Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort
비비교 기반 정렬(Non-comparison Based Sorts)
- Counting Sort, Radix Sort, Bucket Sort

삽입 정렬(Insertion Sort)

개념

• 리스트의 시작부터 하나책마다 왼쪽에 있는 책들과 비교해서 자기보다 작은 책이 나올 때까지 번갈아가며 껴줍니다. 
  • 정렬되지 않은 책장이 있을 때 앞에서부터 왼쪽에 있는 책들과 비교를 하면서 자기 크기에 맞는 곳에 넣어주는 것입니다.
  • 즉, 2 3 5 6 7 4가 있을 때 4는 자기보다 작은 값인 3 뒤로 삽입되게 됩니다. -> 2 3 4 5 6 7
• 시간복잡도는 O(N^2)으로 비효율적인 정렬 알고리즘입니다. 
• 공간복잡도는 해당 배열에 그대로 swap 하며 진행하면 되기 때문에 O(1)입니다.
• 
• 이 과정에서 앞에 부분은 정렬되어 있으므로 이분탐색을 이용하면 탐색과정이 O(logN)만에 됩니다. 따라서 전체 시간복잡도를 O(NlogN)로 만들 수 있다고 생각할 수 있습니다. 하지만 해당 인덱스 위치를 찾더라도 해당 인덱스 부분에 값을 삽입하는 과정은 결론적으로 O(N)의 시간복잡도가 추가로 걸리게 됩니다. (중간에 값을 삽입하는 배열의 경우 시간복잡도는 O(N)) 따라서 결국 기존 삽입 정렬의 시간복잡도는 O(N^2)과 동일해집니다.

링크드리스트에서의 삽입 정렬

• 링크드 리스트에서는 swap 과정이 필요 없고, 단순하게 해당 위치를 찾게 되면 해당위치에 삽입을 해주면 됩니다. (O(1)) 단, 해당 위치까지의 이동이 O(N)이 걸리므로 총 시간복잡도는 O(N^2)으로 동일합니다.

코드

• Insertion Sort

  • def insertion_sort(arr):
        for i in range(1, len(arr)):
            curr_idx = i
    
            while curr_idx > 0 and arr[curr_idx - 1] > arr[curr_idx]:
                arr[curr_idx], arr[curr_idx - 1] = arr[curr_idx - 1], arr[curr_idx]
                curr_idx -= 1
    
    
    arr = [7, 3, 2, 5, 6, 10, 9, 8, 1]
    insertion_sort(arr)
    print(arr)

• Linked List Insertion Sort

  • # 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: Optional[ListNode]) -> Optional[ListNode]:
            dummy = ListNode() # 새로운 배열의 시작노드
            curr = head
    
            while curr:
                prev = dummy
    
                # 현재 노드가 들어갈 위치 찾기
                while prev.next and prev.next.val <=curr.val:
                    prev = prev.next
    
                next = curr.next
                
                # 현재 노드를 해당 prev 다음노드에 삽입시켜줍니다.
                curr.next = prev.next # 현재 다음노드 
                prev.next = curr # 
    
                curr = next
            
            return dummy.next

출처

• https://leetcode.com/explore/learn/card/sorting/694/comparison-based-sorts/4435/
• https://leetcode.com/explore/learn/card/sorting/694/comparison-based-sorts/4485/