[Algorithm]정렬(2) - 퀵 정렬, 계수 정렬

저번 포스팅에서 다루었던 삽입, 선택 정렬에 이어 이번에는 퀵, 계수 정렬을 공부하고 넘어가 보자.

2024.07.09 - [LeetCode + 알고리즘] - [Algorithm]정렬(1) - 선택, 삽입 정렬

[Algorithm]정렬(1) - 선택, 삽입 정렬

 

📍퀵 정렬(Quick Sort)

퀵 정렬은 지금까지 사용되는 모든 정렬 알고리즘중 가장 많이 사용되는 알고리즘이다. 이름에서 부터 알 수 있듯이 실행 시간이 빠른, 효율적인 정렬 알고리즘이다. 그렇다면 퀵 정렬은 어떠한 방식으로 동작될까?

 

'기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?'

 

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환 후 리스트를 나누는 방식으로 동작한다. 여기서 이 기준을 '피벗(pivot)' 이라 부른다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라 표현한다. 이 피벗을 어떻게 설정 하느냐에 따라 알고리즘의 효율이 달라지는데, 여기서는 가장 대표적인 분할 방식인 호어 분할 방식을 기준으로 퀵 정렬을 설명 하겠다. 호어 분할 방식에서의 피벗은 항상 리스트의 첫번째 요소를 피벗으로 삼는다. 이와 같이 피벗을 설정한 후에는 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부턴 피벗보다 작은 데이터를 찾는다. 그 다음 큰 데이터와 작은 데이터의 위치를 서로 교환 해준다. 이러한 과정을 반복하면 '피벗'에 대해 정렬이 수행된다. 다음과 같이 초기 데이터가 구성되어 있다고 해 보자.

퀵 정렬 수행 전의 초기 상태

퀵 정렬은 전체를 3개의 파트로 나눠서 보는게 편하다.

다음은 퀵 정렬의 소스 코드이다.

 

array = [7, 5, 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]:
            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)

 

 

📚 퀵 정렬의 시간 복잡도

퀵 정렬은 평균적으로 O(n log N)의 시간 복잡도를 가진다. 이는 O(N^2)를 가지던 삽입, 선택 정렬에 비해 매우 빠른 정렬 알고리즘이다. 일반적으로 cs에서의 log는 밑이 2인 로그를 의미한다. 즉, 데이터의 갯수가 1,000일때 밑이 2인 로그를 취하면 대략 10이다. 이는 O(N^2)일때는 1,000,000에 비해 10은 매우 작은 숫자이다.

 

데이터의 갯수가 많을수록 차이는 극명하게 드러난다. 다음 표를 보면 데이터의 갯수가 많을수록 퀵 정렬은 앞서 다루었던 선택 정렬, 삽입 정렬에 비해 압도적으로 빠르게 동작한다고 추측 할 수 있다. BUT, 퀵 정렬에 대해 한가지 명심 해야 할 것이 있다. 퀵 정렬의 평균 시간 복잡도는 O(n log N)이지만, 최악의 경우에는 O(n^2)이다. 데이터가 무작위로 입력되는 경우 퀵 정렬은 빠르게 동작할 확률이 높다. 하지만 데이터가 미리 정렬이 어느정도 되어있는 데이터에 대해서는 매우 느리게 동작한다. 이전에 다룬 삽입 정렬은 이미 데이터가 정렬된 상태에서 빠르게 동작한다고 했는데, 퀵 정렬은 그와 반대라고 이해하면 될것 같다. 하지만 파이썬의 .sort()정렬 메서드도 이미 정렬이 된 데이터에 대해 최적화가 되어있기 때문에, 큰 걱정은 하지 않아도 된다.

 

📍계수 정렬(Count Sort)

계수 정렬 알고리즘은 특정 조건이 부합 할때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다. 이 정렬 알고리즘은 최악의 경우에도 수행시간 O(N + K)를 보장하지만, 데이터의 크기 범위가 제한되어 정수 형태로 표현 할 수 있을때만 사용 할 수 있다. 예를들어 데이터의 값이 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우 계수 정렬은 사용하기 어렵다.

 

📦 파이썬의 정렬 라이브러리

파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted()는 퀵 정렬과 비슷한 방식인 병합 정렬을 베이스로 구현되었는데, 이는 최악의 경우에도 O(n log n)을 보장한다. 이러한 sorted()함수는 리스트, 딕셔너리 자료형을 입력받아 정렬된 결과를 출력한다. 집합 자료형이나 딕셔너리 자료형을 입력 받아도 반환되는 결과는 리스트 자료형이다.

 

• sorted()를 이용한 정렬

arr = [7,5,4,1,0,9,8,2,3,6]
result = sorted(arr)

#결과 : result = [0,1,2,3,4,5,6,7,8,9]

 

• sort()를 이용한 정렬

arr = [7,5,4,1,0,9,8,2,3,6]
arr.sort()

#결과 : result = [0,1,2,3,4,5,6,7,8,9]

 

이는 별도의 정렬된 리스트를 반환하지 않고, 내부 원소가 바로 정렬된다. 또한 sort()나 sorted()를 이용할땐 key 파라미터를 입력으로 받을 수 있다. key값으로는 하나의 함수가 들어가야 하며, 이를 기준으로 정렬된다. 예를들어, 리스트의 데이터가 튜플로 구성되어 있을때, 각 데이터의 두 번째 원소를 기준으로 정렬을 원하는 경우 다음과 같이 소스 코드를 작성 할 수 있다.

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

def setting(data):
    return data[1]

result = sorted(array, key=setting)
print(result)

 

파이썬의 `sorted` 함수와 `list.sort` 메서드에서 `key` 매개변수에는 반드시 함수 또는 람다 표현식이 들어가야 한다. `data[1]`과 같은 직접적인 표현식을 사용할 수는 없다. 대신 `key` 매개변수에 함수를 전달하거나, 람다 표현식을 사용하여 원하는 기준으로 정렬할 수 있다.

다음은 예제를 통해 `key` 매개변수에 함수를 직접 전달하거나 람다 표현식을 사용하는 방법이다.

함수를 사용하는 방법

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

# 함수 정의
def setting(data):
    return data[1]

# 함수를 key 매개변수에 전달
result = sorted(array, key=setting)
print(result)  # 출력: [('바나나', 2), ('당근', 3), ('사과', 5)]

람다 표현식을 사용하는 방법

array = [('바나나', 2), ('사과', 5), ('당근', 3)]

# 람다 표현식을 key 매개변수에 전달
result = sorted(array, key=lambda data: data[1])
print(result)  # 출력: [('바나나', 2), ('당근', 3), ('사과', 5)]

설명

- 함수 사용: `key` 매개변수에 `setting`이라는 함수를 전달하여, 각 튜플의 두 번째 요소를 기준으로 정렬한다.
- 람다 표현식 사용: 람다 표현식을 사용하여 `key` 매개변수에 간단한 함수를 직접 전달한다. `lambda data: data[1]`는 익명 함수로, 각 튜플의 두 번째 요소를 반환한다.

`key` 매개변수에는 함수 또는 람다 표현식만을 사용할 수 있다. 따라서 `data[1]`과 같은 표현식은 직접 사용할 수 없고, 이를 포함하는 함수나 람다 표현식을 사용해야 한다.