30. 기본 정렬 알고리듬의 수행 시간 비교

앞서 만들었던 3가지 정렬과 파이썬의 기본 정렬을 비교해 보겠습니다. 

 

파이썬 내장 정렬 함수

비교 전에 파이썬의 내장 정렬 함수에 대해 살짝만 알아봅시다.... 

어짜피 한 번은 다루고 넘어가야 하기 때문에...

 

파이썬의 내장 정렬은 array.sort()와 array = sorted(array)가 있습니다.

 

array.sort()는 내부적으로 정렬합니다.
array = sorted(array)는 새로운 리스트를 만들어 줍니다.  

 

함수형으로 프로그래밍할 때는 sorted가 필요합니다.

 

공식 문서에는 새로운 리스트를 만드는 sorted 보다 sort가 더 효율적이라고 했는데,
테스트 결과는 그와 달라서 혼란스럽습니다. 데이터 셋이 작아서 그런가?

 

파이썬의 공식 문서도 한글화 되어 읽을만합니다.
https://docs.python.org/ko/3/howto/sorting.html

 

파이썬의 내장 정렬은 tim sort이며 Tim Peter라는 분이 2002년 파이썬을 위해 C로 만들었고, merge sort를 최적화한 것으로 알려져 있습니다. 자바, 스위프트 등에서도 기본 정렬로 사용되고 있습니다. 

('난 잘 모르지만 글은 남겨야 겠다.'의 완곡한 표현... 알려져 있다..)
https://d2.naver.com/helloworld/0315536
https://orchistro.tistory.com/175

 

각종 정렬 비교표 

한눈에 들어오니 좋습니다. (출처 : ko.wikipedia.org ko.wikipedia.org) 

이름	최선	평균	최악	메모리	안정
bubble	O(n)	O(n**2)	O(n**2)	O(1)	O
selection	O(n**2)	O(n**2)	O(n**2)	O(1)	X
insertion	O(n)	O(n**2)	O(n**2)	O(1)	O
heap	O(n)	O(n log(n))	O(n log(n))	O(1)	X
merge	O(n log(n))	O(n log(n))	O(n log(n))	O(n)	O
quick	O(n log(n))	O(n log(n))	O(n**2)	O(log(n))	X

 

 

수행 시간 비교를 위해 클로저를 사용했습니다. 

__doc__는 독스트링(함수 시작 부분에서 함수를 설명하는 문자열)을 가져옵니다. 

import timeit
from random import randint


class Array:
    def __init__(self, nums):
        self.data = [randint(1, nums) for _ in range(nums)]

    def clear(self):
        self.data.clear()

    def show_all(self):
        print(self.data)

    def python_sort(self):
        """파이썬 내장 정렬1"""

        array = self.data[:]
        array.sort()
        # print(array)

    def python2_sort(self):
        """파이썬 내장 정렬2"""

        array = self.data[:]
        _ = sorted(array)
        # print(array)

    def fool_sort(self):
        """무식 정렬"""

        array = self.data[:]
        for outer in range(len(array)):
            for inner in range(len(array)):
                if outer != inner and array[outer] < array[inner]:
                    array[outer], array[inner] = array[inner], array[outer]
                # print(outer, inner, array)

    def bubble_sort(self):
        """버블 정렬"""

        array = self.data[:]  # 원본 복사
        for outer in range(len(array), 1,  -1):  # -1은 역순, (주의) 2에서 끝납니다.
            for inner in range(0, outer-1):
                if array[inner] > array[inner+1]:
                    array[inner], array[inner+1] = array[inner+1], array[inner]
                    # print(outer, inner, array)

    def selection_sort(self):
        """선택 정렬"""

        array = self.data[:]
        length = len(array)
        for outer in range(0, length-1):
            min = outer
            for inner in range(outer+1, length):
                if array[min] > array[inner]:
                    min = inner
            if min != outer:
                array[outer], array[min] = array[min], array[outer]
                # print(outer, min, array)

    def insertion_sort(self):
        """삽입 정렬"""

        array = self.data[:]
        for i in range(1, len(array)):
            key = array[i]
            j = i
            while j > 0 and array[j - 1] > key:
                array[j] = array[j - 1]
                j -= 1
            array[j] = key
            #print(i, j, array)


def runtime(f):
    start = timeit.default_timer()
    f
    end = timeit.default_timer()
    print(f'{end - start:0.10f}')


a = Array(5000)
# a.show_all()
print(a.python_sort.__doc__)
runtime(a.python_sort())
print(a.python2_sort.__doc__)
runtime(a.python2_sort())
print(a.fool_sort.__doc__)
runtime(a.fool_sort())
print(a.bubble_sort.__doc__)
runtime(a.bubble_sort())
print(a.selection_sort.__doc__)
runtime(a.selection_sort())
print(a.insertion_sort.__doc__)
runtime(a.insertion_sort())

파이썬 내장 정렬1
0.0000027000
파이썬 내장 정렬2
0.0000007000
무식 정렬
0.0000009000
버블 정렬
0.0000007000
선택 정렬
0.0000008000
삽입 정렬
0.0000007000

 

정확한 결과를 알기 위해서는 여러 번 반복해야 합니다.
(힙 정렬도 끼워 넣었습니다. )

import timeit
from heapq import heapify, heappop
from random import randint


class Array:
    def __init__(self, nums):
        self.data = [randint(1, nums) for _ in range(nums)]

    def python_sort(self):
        """파이썬 내장 정렬1"""
        array = self.data[:]
        array.sort()
        # print(array)

    def python_sort2(self):
        """파이썬 내장 정렬2"""
        array = self.data[:]
        _ = sorted(array)
        # print(array)

    def heap_sort(self):
        """힙 정렬"""
        array = self.data[:]
        heapify(array)
        _ = [heappop(array) for _ in range(len(array))]
        # print(temp)

    def fool_sort(self):
        """무식 정렬"""
        array = self.data[:]
        for outer in range(len(array)):
            for inner in range(len(array)):
                if outer != inner and array[outer] < array[inner]:
                    array[outer], array[inner] = array[inner], array[outer]
                # print(outer, inner, array)

    def bubble_sort(self):
        """버블 정렬"""
        array = self.data[:]  # 원본 복사
        for outer in range(len(array), 1, -1):  # -1은 역순, (주의) 2에서 끝납니다.
            for inner in range(0, outer - 1):
                if array[inner] > array[inner + 1]:
                    array[inner], array[inner + 1] = array[inner + 1], array[inner]
                    # print(outer, inner, array)

    def selection_sort(self):
        """선택 정렬"""
        array = self.data[:]
        length = len(array)
        for outer in range(0, length - 1):
            min_val = outer
            for inner in range(outer + 1, length):
                if array[min_val] > array[inner]:
                    min_val = inner
            if min_val != outer:
                array[outer], array[min_val] = array[min_val], array[outer]
                # print(outer, min, array)

    def insertion_sort(self):
        """삽입 정렬"""
        array = self.data[:]
        for i in range(1, len(array)):
            key = array[i]
            j = i
            while j > 0 and array[j - 1] > key:
                array[j] = array[j - 1]
                j -= 1
            array[j] = key
            # print(i, j, array)


def runtime(f):
    start = timeit.default_timer()
    f
    end = timeit.default_timer()
    # print(end - start)
    return end - start


times = {}
for _ in range(50):
    a = Array(500)
    times['built_in_1'] = times.get('built_in_1', 0) + runtime(a.python_sort())
    times['built_in_2'] = times.get('built_in_2', 0) + runtime(a.python_sort2())
    times['heap'] = times.get('heap', 0) + runtime(a.heap_sort())
    times['fool'] = times.get('fool', 0) + runtime(a.fool_sort())
    times['bubble'] = times.get('bubble', 0) + runtime(a.bubble_sort())
    times['selection'] = times.get('selection', 0) + runtime(a.selection_sort())
    times['insertion'] = times.get('insertion', 0) + runtime(a.insertion_sort())
# print(times)
for key in times:
    print(f"{key:<10}: {times[key]:0.8f}")

built_in_1: 0.00001500
built_in_2: 0.00001000
heap      : 0.00001200
fool      : 0.00003120
bubble    : 0.00002930
selection : 0.00002280
insertion : 0.00002480