주노 정

유저의 눈을 가진 프론트엔드 개발자입니다.
근거있는 코드를 작성하기 위해 노력합니다.

6 분 소요

정렬 (Sorting)

정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.

프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 어떤 식으로든 정렬해서 사용하는 경우가 많아 정렬 알고리즘은 필수적으로 알아야한다고 할 수 있다.

정렬 알고리즘은 선택 정렬, 삽입 정렬, 퀵 정렬 등등 다양한 알고리즘이 존재하는데, 상황에 적절하지 못한 정렬 알고리즘을 사용할 경우 당연히 프로그램이 비효율적으로 동작하며 필요 이상으로 시간을 많이 소요하게 된다.

따라서 시간과 메모리 요구 조건에 맞는 적절한 알고리즘 선택이 가능해야 한다. 사실상 파이썬 기본 정렬 라이브러리와 계수정렬만 알면 웬만한 문제는 해결되긴 하지만 말이다..

선택 정렬 (Selection Sort)

굉장히 원시적인 방법으로, 정렬되지 않은 요소들 중 가장 작은 요소를 선택해 맨 앞부터 쌓는 방식이다.

좀 더 구체적으로 말하자면 데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 말한다.

파이썬으로 작성한 선택 정렬의 소스코드는 다음과 같다.

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

for i in range(len(array)):
    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-1번 만큼 가장 작은 수를 찾고, 매번 가장 작은 수를 찾기 위해 비교 연산이 필요하다. 따라서 N + (N - 1) + (N - 2) + ... + 2이고, 이는 N * (N + 1) / 2, 즉, O(N^2) 라고 표현할 수 있다.

선택 정렬은 기본 정렬 라이브러리를 포함한 다름 알고리즘들과 비교했을 때 매우 비효율적이지만, 특정 리스트에서 가장 작은 데이터를 찾을 때 자주 사용하는 방법이므로 익숙해질 필요가 있다.

삽입 정렬 (Insertion Sort)

삽입 정렬은 데이터를 하나씩 확인하며 각 데이터를 적절한 위치에 삽입해나가는 방식으로 작동하는 정렬 알고리즘이다.

삽입 정렬은 선택 정렬에 비해 구현 난이도가 높은 편이지만 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘이다. 특히 삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다.

삽입 정렬은 특정한 데이터가 적절한 위치에 삽입되기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 즉 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다.

파이썬으로 작성한 삽입 정렬의 소스코드는 다음과 같다.

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

for i in range(1, len(array)):  # 두 번째 인덱스부터 반복
    for j in range(i, 0, -1):   # 마지막 인덱스부터 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]

삽입 정렬의 시간 복잡도는 O(N^2)이다. 선택 정렬과 마찬가지로 반복문이 2번 중첩되어 사용되었다. 하지만 꼭 기억해야 할 것은 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다는 것이다. 최선의 경우 O(N)의 시간 복잡도를 가진다. 따라서 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 여타 정렬 알고리즘들 보다 삽입 정렬을 이용하는 것이 유리하다.

퀵 정렬 (Quick Sort)

퀵 정렬 알고리즘은 지금까지 배운 정렬 알고리즘 중 가장 많이 사용되는 알고리즘으로, 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿔가며 정렬해나가는 알고리즘이다.

퀵 정렬은 기준(pivot)을 설정한 뒤 pivot보다 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 퀵 정렬을 수행하기 전에는 이러한 피벗을 어떻게 설정할 것인지 미리 명시해야 한다.

피벗을 설정하고 리스트를 분할하는 방법에 따라 여러 가지 방식으로 퀵 정렬을 구분하는데, 이 중 호어 분할 (Hoare Partition)을 기준으로 순서대로 퀵 정렬을 살펴보자.

  1. 리스트의 첫 번째 데이터를 피벗으로 설정한다.
  2. 피벗을 제외한 데이터의 맨 왼쪽에서부터 피벗보다 큰 데이터를, 맨 오른쪽에서부터 피벗보다 작은 데이터를 선택한다.
  3. 두 데이터의 위치를 서로 변경한다.
  4. 2번의 과정을 반복한다.
  5. 피벗보다 큰 데이터와 작은 데이터가 엇갈렸을 경우 작은 데이터와 피벗의 위치를 서로 변경한다.
  6. 5번의 과정을 완료하면 리스트에서 피벗을 기준으로 왼편에는 작은 데이터들이 오른편에는 큰 데이터들이 분할되어 있을 것이다. 이후 왼쪽 리스트와 오른쪽 리스트를 개별적으로 1번과 5번의 방법을 통해 정렬시킨다.

6번에서 2개의 파티션이 분리되고, 똑같은 방식으로 두 파티션을 나눠나가는 것은 재귀 함수와 동작 원리가 동일하기 때문에 실제로 퀵 정렬은 재귀 함수 형태로 작성했을 때 구현이 매우 간결해진다. 재귀 함수로 구현을 할 경우 재귀 함수의 종료 조건은 리스트의 원소가 1개일 때이다.

파이썬으로 작성한 가장 직관적인 형태의 퀵 정렬 소스코드는 다음과 같다.

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

def quick_sort(array, start, end):
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end
    while left <= right:
        while left <= end array[left] <= array[pivot]:
            left += 1
        while right > start and array[right] >= array[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)
    quick_sort(array, right + 1, end)

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

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

파이썬의 장점을 살려 짧게 작성한 퀵 정렬 소스코드는 다음과 같다.

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

def quick_sort(array):
    if len(array) <= 1:
        return array
    
    pivot = array[0]
    tail = array[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

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

print(quick_sort(array))

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

퀵 정렬의 평균 시간 복잡도는 O(NlogN)이다. 퀵 정렬에서 최선의 경우는 피벗값의 위치가 변경되어 분할이 일어날 때마다 정확히 왼쪽 리스트와 오른쪽 리스트를 절반씩 분할했을 때이다. 그럴 경우 분할은 logN만큼 분할이 되고, 마지막 노드들은 N개가 되므로 총 NlogN의 시간 복잡도가 나타나게 된다.

하지만 퀵 정렬은 최악의 경우 시간 복잡도가 O(N^2)가 될 수도 있다. 퀵 정렬의 피벗의 기준이 가장 왼쪽 데이터이고, 이미 데이터가 대부분 정렬되어 있을 경우에는 매우 느리게 작동할 수 있다. 앞서 다룬 삽입 정렬은 이미 데이터가 정렬되어 있을 때 빠르게 동작한다고 했는데, 퀵 정렬은 그와 반대된다고 볼 수 있다.

계수 정렬 (Count Sort)

계수 정렬은 모든 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있다. 계수 정렬은 최악의 경우에도 수행시간 O(N + K)를 보장하는 정렬 알고리즘이지만, 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때에만 효과적으로 사용할 수 있다는 점이 특징이다.

계수 정렬은 데이터의 모든 범위를 담을 수 있는 크기의 리스트를 선언한 뒤, 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가시키면 계수 정렬이 완료된다.

파이썬으로 작성한 계수 정렬의 소스코드는 다음과 같다.

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

count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1

for i in range(len(count)):
    for j in range(count[i]):
        print(i, end=' ')

# 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9

계수 정렬의 시간 복잡도는 앞서 언급했듯이 모든 데이터가 양의 정수인 상황에서 데이터의 개수를 N, 데이터 중 최대값의 크기를 K라고 할 때, O(N + K)이다. 따라서 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다. 사실상 현존하는 정렬 알고리즘 중 기수 정렬 (Radix Sort)과 더불어 가장 빠르다고 할 수 있다.

시간상 효율적이라고 할 지라도, 계수 정렬은 때에 따라 심각한 공간적 비효율성을 초래할 수 있다. 예를 들어 데이터가 0과 999,999 단 2개만 존재한다고 가정할 경우, 이럴 때에도 리스트의 크기가 1,000,000이 되도록 선언해야 한다.

따라서 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하며, 데이터의 특성을 파악하기 어렵되면 퀵 정렬을 이용하는 것이 유리하다.

파이썬 정렬 라이브러리

파이썬의 기본 정렬 라이브러리인 sorted() 함수는 퀵 정렬과 동작 방식이 비슷한 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다.

정렬된 리스트를 리턴해주는 sorted() 함수 외에도 리스트의 내부 원소를 바로 정렬해주는 sort() 함수도 존재하는데, 이를 이용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다.

arr = [4, 5, 0, 2, 1, 3]

result = sorted(arr)
print(arr)

# [0, 1, 2, 3, 4, 5]

arr = [4, 5, 0, 2, 1, 3]

arr.sort()
print(arr)

# [0, 1, 2, 3, 4, 5]

또한 sorted()나 sort()를 이용할 때에는 key 매개변수를 입력으로 받을 수 있다.

arr = [(홍길동, 95), (이순신, 77)]
arr = sorted(arr, key = lambda x : x[1])

파이썬 정렬 라이브러리는 항상 최악의 경우에도 시간 복잡도 O(NlogN)을 보장하며, 이는 이미 우리가 직접 퀵 정렬을 구현할 때보다 더욱더 효과적이다.

결론

코딩테스트 문제에서 별도의 요구가 없다면 단순히 정렬해야 하는 상황에서는 기본 정렬 라이브러리를 사용하고, 데이터의 범위가 한정되어 있으며 더 빠르게 동작해야 할 때는 계수 정렬을 사용하자.

References

이것이 취업을 위한 코딩테스트다 with 파이썬

댓글남기기

참고