삽입 정렬 (Insertion Sort) 알고리즘 (with Python3)

삽입 정렬

삽입 정렬(Insertion Sort)은 첫번째 원소부터 하나하나 차례대로 비교해가면서, 자신보다 큰 값이 나타나면 그 큰 값 앞에 놓는 방식이다.

 

예를들어, [2, 4, 5, 1, 3] 이 있을때,

• 비교 대상 2 / 정렬 후 [2, 4, 5, 1, 3]
• 비교 대상 4 / 정렬 후 [2, 4, 5, 1, 3]
• 비교 대상 5 / 정렬 후 [2, 4, 5, 1, 3]
• 비교 대상 1 / 정렬 후 [1, 2, 4, 5, 3]
• 비교 대상 3 / 정렬 후 [1, 2, 3, 4, 5]

코딩

일반적인 삽입 정렬

unittest 기반으로 작성되었다. test_insertion_sort() 를 참고한다.

# -*- coding: utf-8 -*-

import unittest


class Exam09(unittest.TestCase):

    @classmethod
    def setUp(cls):
        pass

    def test_insertion_sort(self):
        data = [2, 4, 5, 1, 3]
        n = len(data)

        for i in range(1, n):
            key = data[i]

            j = i - 1
            while j >= 0 and data[j] > key:
                data[j + 1] = data[j]  # 오른쪽으로 밀어준다. (공간 확보)
                j -= 1
            data[j + 1] = key
            # print(key, data)
        self.assertEqual([1, 2, 3, 4, 5], data)


if __name__ == "__main__":
    unittest.main()

 

파이썬을 활용한 삽입 정렬

unittest 기반으로 작성되었다. test_insertion_sort_with_python() 를 참고한다.

# -*- coding: utf-8 -*-

import unittest


class Exam09(unittest.TestCase):

    @classmethod
    def setUp(cls):
        pass

    def test_insertion_sort_with_python(self):
        data = [2, 4, 5, 1, 3]
        sorted_data = list()
        while data:
            value = data.pop(0)

            n = len(sorted_data)  # value 보다 큰 원소가 없는 경우 맨 뒤로 배치 (default)
            insert_idx = n

            # value 보다 큰 원소를 찾는다.
            for i in range(n):
                if value < sorted_data[i]:
                    insert_idx = i
                    break

            sorted_data.insert(insert_idx, value)
            # print(value, sorted_data)

        self.assertEqual([1, 2, 3, 4, 5], sorted_data)


if __name__ == "__main__":
    unittest.main()

삽입 정렬의 시간복잡도는 O(N^2)으로 상당히 오래걸린다.

 

다른 방법의 정렬 알고리즘은 아래를 참고한다.

• 2020/03/21 - [Algorithm] - 선택 정렬 (Selection Sort) 알고리즘 (with Python3)
• 2020/03/25 - [Algorithm] - 병합 정렬 (Merge Sort) 알고리즘 (with Python3)
• 2020/03/25 - [Algorithm] - 퀵 정렬 (Quick Sort) 알고리즘 (with Python3)
• 2020/03/25 - [Algorithm] - 버블 정렬 (Bubble Sort) 알고리즘 (with Python3)

Reference

• https://thebook.io/006935/part03/ch09/03/