[알고리즘] 이코테(3) - 정렬 알고리즘

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/KGyK-pNvWos?si=w2ozPGhJxDhH5aNy

레퍼런스: https://gyoogle.dev/blog/

---

정렬

데이터를 특정한 기준에 따라 순서대로 나열하는 것.

 

선택 정렬 selection sort

선택 정렬 (출처: GimunLee)

요약

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 알고리즘.

각 탐색마다 결정될 자리를 먼저 선택하고, 자리에 올 값을 찾는 과정이라고 생각하면 좋다.

 

구현

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i # 최솟값의 인덱스, 최초에는 이번 탐색에서 결정될 인덱스로 초기화
    
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]: # 현재 인덱스보다 작은 값을 발견하면
            min_index = j # 최솟값의 인덱스를 갱신
    
    array[i], array[min_index] = array[min_index], array[i] # 탐색이 끝나면 스왑

print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

시간 복잡도

N + (N - 1) + (N - 2) + ... + 2 # 마지막 원소는 이미 확정되었으므로 정렬을 하지 않아도 괜찮다.

 

 

데이터의 개수가 N개라고 했을 때,

• 첫 번째 탐색에서 비교횟수: 1 ... N-1 => N-1
• 두 번째 탐색에서 비교횟수: 2 ... N-1 => N-2
• ...
• (N-1) + (N-2) + .... + 2 => N(N-1) / 2 - 1

시간복잡도는 O(N^2)이다.

최선, 평균, 최악의 경우 모두 같다.

 

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 수행되므로, O(N)이다.

 

특징

• 제자리 정렬 (in-place sorting)
• 불안정 정렬 (unstable sorting)

 

삽입 정렬 insertion sort

삽입 정렬 (출처: GimunLee)

요약

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬 알고리즘.

선택 정렬에 비해 구현 난도는 높지만, 일반적으로 더 효율적.

 

구현

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)): # 1번째 원소는 결정된 것으로 간주하고, 2번째 원소부터 정렬
    for j in range(i, 0, -1): # 삽입할 원소를, 역순으로 기존 원소와 비교하며 삽입 위치를 결정
        if array[j] < array[j-1]: # 현재 원소가 이전 원소보다 작은 경우
            array[j], array[j-1] = array[j-1], array[j] # 위치를 바꿈 # 이전 원소의 왼쪽으로
        else:
            break # 작지 않을 경우 해당 자리에서 멈춤

print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

시간 복잡도

N + (N - 1) + (N - 2) + ... + 1 # 마지막 원소까지 정렬해야 함

 

최악, 평균의 경우: 선택 정렬과 마찬가지로 O(N^2)

최선의 경우: O(N)

 

이미 정렬이 되어 있을 경우, 한 번씩만 비교한다.

즉, 상수 시간이 소요된다.

전체 배열 탐색 + 탐색마다 한 번씩 비교만 하면 되므로 O(N)

 

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 수행되므로, O(1)이다.

추가적인 메모리가 필요하지 않다.

 

특징

• 대부분의 원소가 정렬되어 있는 경우, 매우 효율적이다.
• 제자리 정렬 (in-place sorting)
• 안정 정렬 (stable sorting)

퀵 정렬 quick sort

주황색이 pivot (출처: GimunLee)

요약

기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법.

분할 정복(divide and conquer) 방법을 사용한다.

 

병합 정렬과 더불어 대부분 언어의 기본 정렬 라이브러리의 근간이다.

 

구현1: 일반적인 방식

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return

    pivot = start # 첫 번째 원소를 피봇으로
    left = start + 1 # 왼쪽 포인터의 인덱스
    right = end # 오른쪽 포인터의 인덱스

    while left <= right:
        while left <= end and array[left] <= array[pivot]: # 왼쪽 출발. pivot보다 큰 값을 찾을 때까지.
            left += 1
        
        while right > start and array[right] >= array[pivot]: # 오른쪽 출발. pivot보다 작은 값을 찾을 때까지.
            right -= 1
        
        if left > right: # 포인터가 엇갈렸다면, 작은 값과 피봇 값을 교체
            array[right], array[pivot] = array[pivot], array[right]
        
        else: # 엇갈리지 않았다면, 각 포인터의 값을 교체
            array[left], array[right] = array[right], array[left]
    
    quick_sort(array, start, right - 1) # 분할divide 이후 각각 재귀적으로 정렬
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

 

구현2: pythonic한 방식

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    if len(array) <= 1: # 리스트 원소가 1개라면 재귀 끝 !
        return array
    
    pivot = array[0] # 첫 번째 원소를 피봇
    tail = array[1:] # 피봇을 제외하고 나머지 배열

    left_side = [x for x in tail if x <= pivot] # filter를 사용하듯, pivot 보다 작은 원소만
    right_side = [x for x in tail if x > pivot] # pivot 보다 큰 원소만

    # 재귀적으로 반복하면, left_side에는 min이, right_side에는 max만 남고 return을 시작한다.
    # 차곡차곡 min + 1, max - 1 -> min + 2, max - 2 ... 쌓이고, 정렬이 완성된다.
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array)

 

시간 복잡도

출처: gyoogle

데이터의 크기가 N이라면,

각 순환 호출 단계의 비교 연산: O(N)

총 호출의 횟수: O(logN)

따라서 평균, 최선의 시간복잡도는 O(NlogN)이다.

 

출처: gyoogle

최악의 경우는 O(N^2)이다.

정렬하고자 하는 배열이 이미 오름차순 혹은 내림차순으로 정렬이 되어있는 경우,

각 호출 단계 비교 횟수 O(N), 총 호출 횟수 O(N)이 되어 O(N^2)이다.

 

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 수행된다.

재귀 호출 깊이 만큼 추가적인 공간이 필요하므로 O(logN)이다.

최악의 경우 O(N)이다.

 

특징

• 불안정 정렬
• 불균형 분할 (분할이 항상 절반으로 뚝 나뉘는 것이 아니다. 최악의 경우 시간 복잡도의 비효율을 초래한다.)

 

계수 정렬 Counting sort

반복문을 활용한 방식 (출처: manishsundriyal)

누적합을 활용한 방식 (출처: spagnuolocarmine)

요약

비교하지 않는 정렬이다.

데이터의 값 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.

위 조건에서는 매우 빠르게 동작한다.

 

구현1: 카운트한 값만큼 반복하는 방식

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
result = []

count = [0] * (max(array) + 1) # 값의 모든 범위를 포함하는 카운터 배열. 0으로 초기화

for i in range(len(array)):
    count[array[i]] += 1 # array 원소의 개수를 센다.

for i in range(len(count)):
    for j in range(count[i]): # 현재 원소가 count된 수만큼 반복해서 추가한다.
        result.append(i)

print(result) # [0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9]

 

구현2: 누적합을 사용하는 방식 (다소 직관적이지 않다)

def counting_sort(arr):
    # 1단계: 입력 배열에서 최대값 찾기
    max_val = max(arr)
    count = [0] * (max_val + 1)  # 각 숫자의 등장 횟수를 저장할 배열 초기화
    
    # 각 숫자의 등장 횟수 세기
    for num in arr:
        count[num] += 1
    
    # 2단계: 누적합 계산
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 3단계: 정렬된 배열을 생성하기 위한 임시 배열
    output = [0] * len(arr)
    
    # 원본 배열을 거꾸로 순회하며 정렬된 위치에 숫자 배치
    for num in reversed(arr):
        idx = count[num] - 1  # 정렬된 배열에서의 위치 계산. 누적합에서 1을 빼야 0부터 시작하는 인덱스 반영.
        output[idx] = num
        count[num] -= 1  # 다음 같은 숫자가 올 위치를 위해 누적합 감소
    
    return output

# 예제 배열
arr = [1, 4, 1, 2, 7, 5, 2]
sorted_arr = counting_sort(arr)
print(sorted_arr) # [1, 1, 2, 2, 4, 5, 7]

시간 복잡도

데이터의 개수가 N / 정수의 최대값이 K라면,

카운터 배열의 초기화: O(N)

카운터 배열의 누적합을 만드는 과정: O(K)

 

O(N + K)의 시간 복잡도를 갖는다.

O(N)이 아닌 이유는 [1, 999999] 배열을 정렬할 경우, N = 2임에도 K의 크기만큼 누적합을 계산해야 하기 때문에.

 

공간 복잡도

누적합 배열: O(K)

정렬된 배열: O(N)
따라서 추가적으로 필요한 공간은 O(N + K)이다.

 

비교 기반 알고리즘과 다르게 동작하기 때문에, 정렬된 배열을 위한 공간 O(N)이 필요하다는 것을 기억하자.

 

특징

• 안정 정렬 (stable sorting)
• 제자리 정렬이 아니다 !!! 비교 기반 알고리즘과는 다르다.