[알고리즘]정렬 알고리즘 및 시간 복잡도 정리

이번에 준비하면서 정렬 알고리즘 관련을 보았는데, 잊어먹은게 많아서 따로 정리를 해본다.

일단 정렬 알고리즘이라면 보통 이렇게 알고있다

1. 버블 정렬 알고리즘 (Bubble Sort)

2. 선택 정렬 알고리즘 (Selection Sort)

3. 삽입 정렬 알고리즘 (Insertion Sort)

4. 합병 정렬 알고리즘 (Merge Sort)

5. 퀵 정렬 알고리즘 (Quick Sort)

다음은 각 알고리즘을 내 방식대로 설명하며, 코딩은 파이썬으로 해보았다.

1. 버블 정렬 알고리즘

액체가 끓때 거품이 올라가는거처럼 표현한 알고리즘이다

시간 복잡도는 O(n^2)

파이썬 코드:

def bubblesort(alist):
    for loop_count in range(len(alist)-1, 0, -1):
        for idx in range(loop_count):
            if alist[idx] > alist[idx+1]:
                tmp = alist[idx]
                alist[idx] = alist[idx+1]
                alist[idx+1] = tmp
 
    return alist

2. 선택 정렬 알고리즘

시간 복잡도는 O(n^2)

파이썬 코드:

def selectionSort(alist):
    for offset in range(0, len(alist)-1):
        offset_minvalue = 0
        for num in range(offset+1, len(alist)):
            if alist[num] < alist[offset_minvalue]:
                offset_minvalue = num
        tmp = alist[offset_minvalue]
        alist[offset_minvalue] = alist[offset]
        alist[offset] = tmp
    return alist

3. 삽입 정렬 알고리즘

내가 이해한 바로는 기존의 배열을 두고, 첫번째 인자값을 다른 배열로 넣고

이후 각 배열 값과 대소관계를 비교하면서 삽입하는 것.

시간 복잡도: O(n)==> 이미 정렬된 경우 혹은 O(n^2)

파이썬 코드:

def insertionsort(alist):
    for index in range(1, len(alist)):
        currentvalue = alist[index]
        position = index
 
        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]
            position = position - 1
 
        alist[position] = currentvalue
    return alist

4. 합병 정렬 알고리즘

기존 배열을 중간 중간으로 나누면서 이분법으로 정렬하는 것

시간 복잡도: O(nlogn)

파이썬 코드:

def mergesort(alist):
    if len(alist) <= 1:
        return alist
 
    mid = len(alist)
    leftlist = alist[:mid]
    rightlist = alist[mid:]
    # return leftlist, rightlist
    L = mergesort(leftlist)
    # R = mergesort(rightlist)
 
    # i = j = 0
    # result = []
 
    # while i < len(L) and j < len(R):
    #     if L[i] < R[j]:
    #         result.append(L[i])
    #         i += 1
    #     else:
    #         result.append(R[j])
    #         j += 1
 
    # result += L[i:]
    # result += R[j:]
    # return result

5. 퀵 정렬 알고리즘

피봇(pivot)을 기준으로 좌우로 배열 값 비교하면서 정렬

시간 복잡도 : O(nlogn)

파이썬 코드:

def qsort(alist, s, e):
    pivot = alist[s]
    bs = s, be = e;
    while s<e:
        while pivot <= v[e] and s<e:
            e -= 1
        if s>e: break
        while pivot >= v[s] and s<e:
            s += 1
        if s>e: break
        # python 에선 swap을 이렇게
        alist[s], alist[v] = alist[v], alist[s]
 
    alist[bs], alist[s] = alist[s], alist[bs]
    if bs<s : qsort(alist, bs, s-1)
    if be>e : qsort(alist, s+1, be)