[알고리즘] O(N^2) 정렬 알고리즘 정리 : 선택 정렬, 삽입 정렬, 거품 정렬

선택 정렬 (Selection Sort)

현재 위치에 들어갈 값을 선택해서 정렬하는 배열이다. 일상에서 크기 순으로 나열할때 하나씩 끄집어내서 정렬하는 걸 생각하면 쉽다.

예를 들어서 오름차순으로 정렬하는 경우에, index 0번에 오는 원소는 모든 값중에서 가장 작은 값을 선택해서 정렬한다. 그후 index 1 번에 오게 될 원소를 찾아서 선택하여 정렬하게 되는데, 0 번에 정렬한 값을 제외하고 나머지 값들 중에서 가장 작은 값을 선택해서 정렬하게 되면 된다.

• 시간 복잡도 : O(N**2)

시간 복잡도는 루프문을 통해 모든 인덱스에 접근해야 하므로, 기본적으로 O(N)이 걸리고, 하나의 루프에서 현재 인덱스 값과 다른 인덱스의 값들과 비교를 각각 한번씩 수행하여 최소값을 찾은 후 현재 인덱스에 있는 값과 swap 해야하므로 O(N)이 걸리게 된다. 따라서 O(N**2) 이라는 시간 복잡도가 나오게 된다. 

• 공간 복잡도 : O(1)

선택 정렬은 추가 공간을 사용하지 않고, 주어진 배열이 차지하고 있는 공간 내에서 값들의 위치만 바꾸기 때문에 O(1)의 공간 복잡도를 가진다.

# 선택 정렬 - 오름차순으로 정렬
# O(N**2)
def selection_sort(arr):
    N = len(arr)
    for i in range(N-1):
        min_idx = i # 확인하려는 인덱스 위치
        for j in range(i+1, N):
            if arr[min_idx] > arr[j]: # 더 작은 값을 발견하면
                min_idx = j # min_idx 를 갱신!
        # swap
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

 

삽입 정렬 (Insertion Sort)

정렬 범위를 하나씩 넓혀가면서, 새로운 원소를 정렬 범위에 포함시킨다. 그리고 새롭게 정렬 범위에 포함된 원소를 기존에 정렬된 값들과 비교하여 알맞은 위치에 삽입해주는 알고리즘이다. 

• 시간 복잡도 : O(N^2)

정렬범위에 하나씩 원소들을 추가해야 하므로 O(N) 이 걸리고, 정렬 범위 내에서 새로 들어온 원소와 비교 작업을 해야 하므로 여기서 O(N)이 걸리게 된다. 따라서 O(N^2) 의 시간 복잡도가 걸린다. 

• 공간 복잡도 : O(1)

삽입 정렬은 별도의 추가 공간을 사용하지 않으며, 주어진 배열 내부에서 원소들의 위치만 swap 하기 때문에 O(1)의 공간 복잡도를 가진다. 

# 삽입 정렬 - 오름차순 정렬
# O(N**2)
def insertion_sort(arr):
    N = len(arr)
    for i in range(1, N): # 정렬 범위를 하나씩 늘려가기 
        for j in range(i, 0, -1): # 정렬 범위 내에서 정렬하기 
            if arr[j] < arr[j-1]:
                arr[j], arr[j-1] = arr[j], arr[j-1] # swap

 

거품 정렬 (Bubble Sort)

배열 내의 값들을 앞뒤로 비교해서 자리를 바꾸는 작업을 지속적으로 수행해서 정렬하는 방식. 큰 값을 계속해서 뒤로 보내는 것이 거품이 이동하는 것과 같아서 (?) bubble sort 라고 한다고 한다.

• 시간 복잡도 : O(N^2)

맨 뒤에서 부터 맨 앞까지 모든 원소에 접근해야 하므로 O(N) 이 걸리며, 하나의 루프 내에서는 원소간 값을 비교하여 swap 연산으로 큰 값을 뒤로 보내는 작업을 해야 하므로 O(N) 이 걸린다. 따라서 O(N^2) 이 소요된다. 

• 공간 복잡도 : O(1)

별도의 추가 공간을 사용하지 않으며, 주어진 배열 내부에서 원소들의 위치만 swap 하기 때문에 O(1)의 공간 복잡도를 가진다. 

# 버블 소트 - 오름차순으로 정렬 
# O(N^2)
def bubble_sort(arr):
    N = len(arr)
    for i in range(N-1, 0, -1):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
        print(arr)
    return arr