[파이썬 | 알고리즘 문제해결전략] O(n^2) 정렬 알고리즘

import sys
import random
import copy
import time
read = sys.stdin.readline
 
def logging_time(original_fn):
    def wrapper_fn(*args, **kwargs):
        start_time = time.time()
        result = original_fn(*args, **kwargs)
        end_time = time.time()
        print("WorkingTime[{}]: {} sec".format(original_fn.__name__, end_time-start_time))
        return result
    return wrapper_fn
 
 
def randomArr(size):
    ret = list(range(1, size+1))
    random.shuffle(ret)
    return ret
 
@logging_time
def bubbleSort(arr):
    N = len(arr)
 
    for i in range(N-1, -1, -1):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
 
    return arr
 
@logging_time            
def selectionSort(arr):
    N = len(arr)
 
    for i in range(N):
        minidx = i
        for j in range(i, N):
            if arr[minidx] > arr[j]:
                minidx = j
        arr[i], arr[minidx] = arr[minidx], arr[i]
 
    return arr
 
@logging_time
def insertionSort(arr):
    N = len(arr)
 
    for i in range(N):
        j = i
        while arr[j] > arr[j-1] and j > 0:
            arr[j], arr[j-1] = arr[j-1], arr[j]
            j -= 1 
    return arr
 
if __name__ == '__main__':
    arr = randomArr(10000)
    bubbleSort(copy.deepcopy(arr))
    selectionSort(copy.deepcopy(arr))
    insertionSort(copy.deepcopy(arr))

 

책에 따르면 삽입정렬이 선택정렬보다 일반적인 경우에 더 빠르다.

 

왜냐하면 이미 정렬이 된 경우에는 삽입정렬의 경우 while문이 실행되지 않아서 O(n)의 경우로 실행되기 때문이다.

 

그런데 그냥 랜덤 배열을 생성해서 정렬을 돌려보니 선택이 2배가량 빠른데 이유를 잘 모르겠다.

 

 

### insertionSort를 책에 나온 방식이 아닌 알고리즘 수업시간에 배웠던 방법으로 하니까 시간이 단축되었다.

 

insertionSort는 swap이 아닌 대입의 형태로 하는게 시간 향상에 도움이 된다.

@logging_time
def insertionSort(arr):
    N = len(arr)
 
    for i in range(1, N):
        temp = arr[i]
        idx = 0
        for j in range(i-1, -1, -1):
            if arr[j] >= temp:
                arr[j+1] = arr[j]
            else:
                idx = j+1
                break
        arr[idx] = temp
    return arr