[TIL] 20240311 19일차

정렬 알고리즘

 

	버블 정렬	삽입 정렬	선택 정렬	병합 정렬	퀵 정렬
시간 복잡도	O(n²)	O(n²)	O(n²)	O(nlogn)	O(nlogn)
공간 복잡도	O(n)	O(n)	O(n)	O(nlogn)	O(nlogn)

 

버블 정렬, 삽입 정렬, 선택 정렬은 반복문을 2번 돌려서 정렬을 수행한다.

-> 시간 복잡도로 제곱 형태가 나오게 된다.

 

리스트 안에서 요소들의 교환만 일어나기 때문에, 공간 복잡도는 n으로 표현된다.

 

반면 병합 정렬, 퀵 정렬은 반으로 쪼개거나 피벗을 두고 쪼개서 정렬하고 다시 합치는 과정을 거치기 때문에

쪼개는 과정이 log로, 정렬 과정이 n으로 표현된다.

 

리스트를 분해했다가 다시 병합하기 때문에 공간 복잡도에 log가 추가로 붙게 된다.

 

 

구현 코드

# [버블 정렬]

def bubble_sort(arr, reverse=False):
    # 배열 크기
    n = len(arr)

    for i in range(n - 1):
        for j in range(n - i - 1):
            # 오름차순 옵션
            if arr[j] > arr[j + 1] and reverse is False:
                # 왼쪽이 오른쪽보다 크면 서로 자리를 바꿈
                # 최댓값을 오른쪽(인덱스가 큰 쪽)으로 계속 밀어놓는 방식
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            # reverse(내림차순) 옵션
            elif arr[j] < arr[j + 1] and reverse is True:
                # 왼쪽이 오른쪽보다 작으면 서로 자리를 바꿈
                # 최솟값을 오른쪽(인덱스가 큰 쪽)으로 계속 밀어놓는 방식
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
        # 중간 과정 출력
        print(arr)

 

# [선택 정렬]

def selection_sort(arr, reverse=False):
    # 배열 크기
    n = len(arr)

    for i in range(n):
        # 오름차순일 경우 최솟값을 가지는 요소의 인덱스
        # 내림차순일 경우 최댓값을 가지는 요소의 인덱스
        # 0 ~ n을 정렬, 1 ~ n을 정렬, ... 반복
        idx = i
        for j in range(i + 1, n):
            # 오름차순일 경우 최솟값을 왼쪽(인덱스가 작은 쪽)으로 계속 밀어놓는 방식
            # 그러므로 최솟값을 가지는 요소의 인덱스를 갱신해준다.
            # 내림차순일 경우 최댓값을 왼쪽(인덱스가 작은 쪽)으로 계속 밀어놓는 방식
            # 그러므로 최댓값을 가지는 요소의 인덱스를 갱신해준다.
            if arr[j] < arr[idx] and reverse is False:
                idx = j
            elif arr[j] > arr[idx] and reverse is True:
                idx = j
        arr[i], arr[idx] = arr[idx], arr[i]
        # 중간 과정(왼쪽부터 정렬되는)을 출력한다.
        print(arr[:i + 1])

 

# [삽입 정렬]

def insertion_sort(arr, reverse=False):
    # 배열 크기
    n = len(arr)

    for i in range(1, n):
        # 두번째 요소부터 선택해서 확인하므로 인덱스가 1부터 증가
        for j in range(i, 0, - 1):
            # 여기서부턴 bubble sort랑 같다.
            # bubble과 다른 것은 요소를 살펴보는 방향성이 다르다
            # bubble: 인덱스가 증가하는 방향
            # insertion: 인덱스가 감소하는 방향
            if arr[j - 1] > arr[j] and reverse is False:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
            elif arr[j - 1] < arr[j] and reverse is True:
                arr[j - 1], arr[j] = arr[j], arr[j - 1]
        # 중간 과정(왼쪽부터 정렬되는)을 출력한다.
        print(arr[:i + 1])