정렬 알고리즘이란?

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

정렬 알고리즘은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등 다양한 방법이 있다. 이 알고리즘을 통해 알고리즘의 효율성을 쉽게 이해할 수 있어서, 알고리즘 개론에서 자주 다루어진다. 상황에 맞는 적절한 정렬 알고리즘을 선택했느냐에 따라 프로그램의 성능이 크게 좌우될 수 있기 때문에, 이 학습을 통해 알고리즘 효율의 중요성을 깨달을 수 있다.

선택 정렬 (Selection Sort)

리스트에서 가장 작은 원소를 선택하여 맨 앞에 위치한 원소와 교환하는 과정을 반복하여 정렬하는 방법

def selection_sort(arr):
    arr_len = len(arr)
    for i in range(arr_len):
        min_index = i # 현재 위치를 최소값 인덱스로 설정

        for j in range(i + 1, arr_len):
            if arr[j] < arr[min_index]:
                min_index = j # 더 작은 값이 있으면 인덱스 갱신

        # 최소값과 현재 위치의 값을 교환
        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr

위의 코드를 통해 알 수 있듯이 선택 정렬은 N + (N-1) + (N-2) + ... + 2 번의 비교 연산을 수행한다. 따라서 이는 (N^2 + N)/2로 정리할 수 있으며, 빅오 표기법에 따라 시간 복잡도는 O(N^2)이 된다.
선택 정렬은 구현이 간단하고 이해하기 쉬운 장점이 있지만, 다른 정렬 알고리즘에 비해 비효율적이다. 다만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩 테스트에서 자주 출제되므로 이 알고리즘에 익숙해질 필요가 있다.

삽입 정렬 (Insertion Sort)

데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입하여 정렬하는 방법

def insertion_sort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1): # i부터 1까지 감소하며 반복
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j] # 자신과 바로 앞의 원소를 비교하여 교환
            else:
                break # 이미 정렬된 상태이면 멈춤

    return arr

삽입 정렬의 시간 복잡도는 최악의 경우 O(N^2)이지만, 이미 거의 정렬된 상태에서는 O(N)의 시간 복잡도를 가진다. 따라서 데이터가 거의 정렬된 상태라면 삽입 정렬이 매우 효율적일 수 있다. 따라서 거의 정렬된 상태로 입력이 주어지는 문제라면 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.

퀵 정렬 (Quick Sort)

기준 데이터를 설정하고, 그 기준보다 작은 데이터와 큰 데이터의 위치를 바꾸는 과정을 반복하여 정렬하는 방법

def quick_sort_normal(arr, start, end):
    '''
    일반적인 퀵 정렬 구현

    추가적인 메모리 공간을 사용하지 않으나,
    코드가 다소 복잡하여 빠르게 파악하기 어렵다.
    '''
    if start >= end: # 원소가 1개인 경우 종료
        return

    pivot = start # 피벗은 첫 번째 원소
    left = start + 1
    right = end

    while left <= right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and arr[right] >= arr[pivot]:
            right -= 1

        if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체
            arr[right], arr[pivot] = arr[pivot], arr[right]
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            arr[left], arr[right] = arr[right], arr[left]

    # 분할 이후 왼쪽과 오른쪽 부분에서 각각 정렬 수행
    quick_sort_normal(arr, start, right - 1)
    quick_sort_normal(arr, right + 1, end)


def quick_sort_for_python(arr):
    '''
    파이썬의 장점을 살린 퀵 정렬 구현

    피벗과 데이터를 비교하는 연산 횟수가 증가하며
    리스트를 위한 새로운 메모리 공간을 할당하기 때문에
    비효율적일 수 있다.
    그러나 코드가 간결해지고 이해하기 쉽다는 장점이 있다.
    '''
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(arr) <= 1:
        return arr

    pivot = arr[0] # 기준 데이터 설정
    tail = arr[1:] # 기준 데이터를 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 기준보다 작은 데이터 리스트
    right_side = [x for x in tail if x > pivot] # 기준보다 큰 데이터 리스트

    return quick_sort_for_python(left_side) + [pivot] + quick_sort_for_python(right_side)

퀵 정렬은 분할 정복 알고리즘의 일종으로, 리스트를 분할하여 각각 정렬하는 방식으로 동작한다.
먼저 첫 번째 원소를 피벗으로 설정한다. 그리고 왼쪽부터 피벗보다 큰 원소를 찾고, 오른쪽부터는 피벗보다 작은 원소를 찾는다. 그런 다음 두 원소의 위치를 바꾸는 과정을 반복한다. 이 과정이 엇갈리면 피벗과 작은 원소의 위치를 바꾸고, 그 후에 피벗을 기준으로 왼쪽과 오른쪽 부분 리스트를 각각 재귀적으로 정렬한다.
퀵 정렬은 평균 시간 복잡도는 O(N log N)이다. 그러나 최악의 케이스에는 O(N^2)이 된다.
퀵 정렬의 핵심은 얼마나 균등하게 리스트를 분할하느냐에 달려 있다. 균등 분할 여부가 작업의 깊이를 결정하고, 깊이는 총 비교 연산 횟수에 직접적인 영향을 미치기 때문이다. 따라서 데이터가 무작위로 입력되는 경우 평균적으로 균등하게 분할되어 빠르게 동작할 확률이 높다.

최선의 경우 - 균등 분할

정렬되지 않은 8개 원소를 정렬한다고 가정해보자.

1단계: [8개] 전체를 비교하며 분할 → 8번 비교
2단계: [4개][4개] 각각 분할 → 4+4 = 8번 비교  
3단계: [2][2][2][2] 각각 분할 → 2+2+2+2 = 8번 비교

깊이: 3단계 (log₂ 8)
각 단계마다 N번 비교 → 총 N × log N = 8 × 3 = 24번

각 단계에서 "모든 원소"를 한 번씩은 봐야 하므로 단계마다 약 N번의 비교가 필요하다. 즉, 단계 수가 적을수록 총 비교 횟수가 줄어들게 된다.

최악의 경우 - 불균등 분할

이번엔 정렬된 상태의 8개 원소를 정렬한다고 가정해보자.

1단계: [8개] 분할 → 7번 비교 (1개 | 7개)
2단계: [7개] 분할 → 6번 비교 (1개 | 6개)
3단계: [6개] 분할 → 5번 비교 (1개 | 5개)
...
7단계: [2개] 분할 → 1번 비교

깊이: 7단계 (N-1)
총 비교: 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28번 ≈ N²/2

이 경우 첫 번째 원소가 계속 피벗이 되어 한쪽만 반복적으로 처리하게 된다. 결과적으로 선택 정렬과 유사하게 동작하게 되어 효율이 매우 떨어진다.

계수 정렬 (Counting Sort)

데이터의 크기 범위가 제한되어 있을 때, 각 데이터가 몇 번 등장했는지를 세어 정렬하는 방법

def counting_sort(arr):
    max_value = max(arr) # 입력 데이터 중 최댓값 찾기
    count_arr = [0] * (max_value + 1) # 모든 값의 개수를 담을 리스트 초기화

    # 각 데이터에 해당하는 인덱스의 값 증가
    for num in arr:
        count_arr[num] += 1

    sorted_index = 0
    # 각 데이터의 개수만큼 반복하여 원래 배열에 값 채우기
    for i in range(len(count_arr)):
        # i가 arr에 등장한 횟수만큼 반복
        for _ in range(count_arr[i]):
            arr[sorted_index] = i
            sorted_index += 1

    return arr

계수 정렬은 특정한 조건이 부합할 때, 매우 효율적으로 동작하는 정렬 알고리즘이다. 데이터의 크기 범위가 제한되어 있고, 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 데이터 크기 범위는 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다. 계수 정렬의 시간 복잡도는 O(N + K)이다. 여기서 N은 데이터의 개수, K는 데이터 중 최대값의 크기이다. 따라서 데이터의 크기 범위가 한정되어 있다면, 현존하는 정렬 알고리즘 중 기수 정렬(Radix Sort)과 더불어 가장 빠르다고 할 수 있다.
보통 기수 정렬은 계수 정렬에 비해서 동작은 느리지만, 처리할 수 있는 정수의 크기는 더 크다. 다만 알고리즘 원리나 소스 코드는 더 복잡하다. 다만 기수 정렬은 코딩 테스트에서 거의 다루어지지는 않는다.

계수 정렬의 공간 복잡도는 O(N + K)로 때에 따라 심각한 메모리를 낭비할 수 있다. 예를 들어, 데이터가 1, 1000000 두 개만 존재한다면, 크기가 1,000,001인 리스트를 생성해야 한다. 따라서 계수 정렬을 사용할 때는 데이터의 분포를 반드시 고려하여 동일한 값을 가지는 데이터가 다수 존재하는 경우에만 사용하는 것이 좋다.
일반적인 코딩 테스트에서 이 유형의 문제가 출제될 때는 메모리 공간과 시간의 제약으로 인해 입력되는 데이터의 개수를 1,000만개 미만으로 출제될 가능성이 높다.

정리

정렬 알고리즘은 이미 너무 많이 연구되어 왔다. 따라서 정렬 알고리즘 문제는 어느 정도 정해진 방법이 이어서 외워서 풀어낼 수 있는 유형이라고 할 수 있다.
파이썬에서는 기본 정렬 라이브러리로 sort()와 sorted()가 제공된다. 이 함수들은 모두 최악의 경우에도 O(N log N)의 시간 복잡도를 보장한다. 이는 병합 정렬과 삽입 정렬의 장점을 결합한 하이브리드 방식인 Timsort라는 알고리즘을 사용하기 때문이다.

코딩 테스트에서 정렬 알고리즘 유형의 문제는 3가지로 분류될 수 있다.

1. 정렬 라이브러리로 풀 수 있는 문제 - 단순히 정렬 기법을 알고 있는지 묻는 문제로 정렬 라이브러리를 사용하여 쉽게 해결할 수 있다.
2. 정렬 알고리즘의 원리에 대해 물어보는 문제 - 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 이해하고 있어야 풀이가 가능하다.
3. 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반의 정렬 기법으로 풀 수 없으며, 계수 정렬 등의 다른 정렬 알고리즘을 이용하거나 문제에서 기존에 알려진 알고리즘의 구조적인 개선을 요구하는 문제이다.