시간 복잡도

• 알고리즘의 효율을 실행되는 시간으로 측정

Big - O

Bubble sort (버블정렬)

• 최대 O(n^2) 시간복잡도
• 이웃한 두 값을 비교하여 정렬
• 최댓값을 맨 오른쪽으로 이동

li = [] #정렬되지 않은 랜덤 숫자가 들어간 리스트 객체

for i in reversed(range(len(li))):
    for j in range(i):
        if li[j] > li[j+1]:
            li[j], li[j+1] = li[j+1], li[j] # Swap

Selection sort (선택정렬)

• 최대 O(n^2) 시간복잡도
• 주어진 정렬에서 최대값을 찾고 맨 오른쪽 값과 교체 (버블정렬과 비슷하지만 이웃한 두 값 정렬 X)

li = []

for i in reversed(range(len(li))):
    max_position = 0
    for j in range(1, i + 1):
        if li[j] > li[max_position]:
            max_n = j
    li[max_position], li[i] = li[i], li[max_position]

Insertion sort (삽입정렬)

• 최대 O(n^2) 시간복잡도이지만 버블이나 선택에 비해 빠름
• 값을 배열 사이에 끼워넣는 과정 반복

li = []

for i in range(1, len(li)):
    num = li[i]
    j = i
    while j > 0 and li[j-1] > num:
        li[j] = x[j-1]
        j -= 1
    li[j] = num

Shell sort (쉘 정렬)

• 간격에 따라 시간복잡도가 천차만별
• 주어진 간격만큼 벌어진 서브배열을 만들어 삽입정렬 수행

def gapInsertionSort(x, start, gap): # 삽입정렬
    for target in range(start+gap, len(x), gap): # 정한 간격만큼 삽입정렬 수행
        val = x[target]
        i = target # 인덱스
        while i > start:
            if x[i-gap] > val: # 타켓 값보다 크다면
                x[i] = x[i-gap] # 해당 인덱스에 값 할당
            else:
                break
            i -= gap
        x[i] = val # 해당값 삽입

def shellSort(x):
    gap = len(x) // 2 # 리스트의 중간값 (간격)
    while gap > 0:
        for start in range(gap):
            gapInsertionSort(x, start, gap)
        gap = gap // 2 # 간격을 줄여감

Merge sort (병합 정렬)

• 폰 노이만이 개발했으며, 두 부분으로 쪼개는 것을 반복한 뒤 작은 값부터 병합
• 쪼갤 때 O(log n); 이진탐색, 데이터 병합 O(n) -> 언제나 O(n log n)

def mergeSort(x):
    if len(x) > 1: # 배열의 길이가 1일 때까지 쪼갬
        mid = len(x)//2
        lx, rx = x[:mid], x[mid:] # 중간값 기준으로 왼, 오 나눔
        mergeSort(lx) # 재귀함수 사용하여 또 쪼갬
        mergeSort(rx) 

        li, ri, i = 0, 0, 0 # 정렬을 위한 변수 선언
        while li < len(lx) and ri < len(rx):
            if lx[li] < rx[ri]: # 오른쪽 리스트의 값이 클 경우
                x[i] = lx[li]
                li += 1
            else:
                x[i] = rx[ri] # 왼쪽 리스트의 값이 클 경우
                ri += 1
            i += 1
        x[i:] = lx[li:] if li != len(lx) else rx[ri:]
        # 왼쪽 리스트의 길이가 서브 리스트의 값과 !=라면 왼쪽 서브리스트 값 덮어쓰기
        # 그렇지 않다면 오른쪽 서브 리스트 할당

참고 : https://ratsgo.github.io/data%20structure&algorithm/2017/10/19/sort/