[알고리즘] Linear-Time Sorting

Python

def counting_sort(arr, k):
    """
    Counting Sort 알고리즘을 사용하여 배열을 정렬합니다.

    Args:
      arr: 정렬할 배열.
      k: 배열의 최대값.

    Returns:
      정렬된 배열.
    """
    counts = [0] * (k + 1)  # 0부터 k까지의 요소 개수를 저장할 배열
    result = [0] * len(arr)  # 정렬된 결과를 저장할 배열

    # 각 요소의 개수를 센다
    for x in arr:
        counts[x] += 1

    # 누적 합을 계산한다
    for i in range(1, k + 1):
        counts[i] += counts[i - 1]

    # 입력 배열을 순회하며 각 요소를 정렬된 배열에 배치한다
    for x in arr[::-1]:  # 안정성을 위해 뒤에서부터 순회
        result[counts[x] - 1] = x
        counts[x] -= 1

    return result

def bucket_sort(arr, k):
    """
    Bucket Sort 알고리즘을 사용하여 배열을 정렬합니다.

    Args:
      arr: 정렬할 배열.
      k: 버킷의 개수.

    Returns:
      정렬된 배열.
    """
    buckets = [[] for _ in range(k)]  # k개의 빈 버킷 생성

    # 각 요소를 해당하는 버킷에 넣는다
    for x in arr:
        buckets[int(x * k)].append(x)

    # 각 버킷 내에서 정렬을 수행한다
    for i in range(k):
        buckets[i].sort()  # 삽입 정렬 등 다른 정렬 알고리즘 사용 가능

    # 모든 버킷을 순서대로 합친다
    result = []
    for bucket in buckets:
        result.extend(bucket)

    return result

def radix_sort(arr, d):
    """
    Radix Sort 알고리즘을 사용하여 배열을 정렬합니다.

    Args:
      arr: 정렬할 배열.
      d: 배열 요소의 자릿수.

    Returns:
      정렬된 배열.
    """
    for i in range(d):  # 가장 낮은 자릿수부터 시작
        arr = counting_sort_for_radix(arr, i)  # i번째 자릿수에 대해 Counting Sort 수행
    return arr

def counting_sort_for_radix(arr, digit):
    """
    Radix Sort에서 사용하는 Counting Sort 알고리즘입니다.

    Args:
      arr: 정렬할 배열.
      digit: 정렬 기준이 되는 자릿수.

    Returns:
      정렬된 배열.
    """
    counts = [0] * 10  # 0부터 9까지의 숫자 개수를 저장할 배열
    result = [0] * len(arr)  # 정렬된 결과를 저장할 배열

    # 각 요소의 i번째 자릿수를 센다
    for x in arr:
        counts[(x // 10**digit) % 10] += 1

    # 누적 합을 계산한다
    for i in range(1, 10):
        counts[i] += counts[i - 1]

    # 입력 배열을 순회하며 각 요소를 정렬된 배열에 배치한다
    for x in arr[::-1]:  # 안정성을 위해 뒤에서부터 순회
        result[counts[(x // 10**digit) % 10] - 1] = x
        counts[(x // 10**digit) % 10] -= 1

    return result

코드 출력

Code executed successfully!

제목: 정렬 알고리즘에서 시간 복잡도 O(n)을 달성할 수 있을까?

서론

이전 포스팅에서 Merge Sort에 대해 다룬 적이 있다. Merge sort는 O(n log n) 시간 복잡도를 갖는 효율적인 알고리즘이었다. 그러나 Merge Sort는 비교 기반 정렬 알고리즘으로, 입력 데이터의 크기 n에 대해 최소 Ω(n log n) 시간이 소요됨이 증명되었다. 이는 다음의 Decision tree를 통해 알 수 있다.

Comparison Based Sorting

비교 기반 정렬 알고리즘은 '비교'라는 행위에 의해 decision tree로 표현될 수 있다. 그리고 decision tree에서의 runtime은 Ω(경로의 길이)로 알 수 있다. (runtime analysis 참조)

decision tree

우리가 구하고자 하는 것은 가장 빠른 알고리즘의 최소한의 runtime을 구하는 것이다. 어떻게 구할 수 있을까? 일단 runtime analysis를 위해 longest path를 찾아야 한다. 그리고 가장 빠른 알고리즘을 판단하기 위해서는 path가 한쪽만 길어지지 않도록 balanced tree를 생각해 볼 수 있다. 

runtime analysis

즉, 그림과 같은 양쪽으로 균일한 tree의 경우가 comparison based sorting 중 가장 빠른 경우이다. Tree의 depth, 즉 longest path가 log(n!)이므로 이 알고리즘은 최소한 Ω(log(n!))의 실행 시간을 갖는다. 그리고 이는 n log(n/e)로 근사되어 Ω(n log(n))의 runtime을 갖게 된다.

그렇다면 정렬 문제를 더 빠르게 해결할 수 있는 방법은 없을까? 이 질문에 대한 답이 바로 선형 시간 정렬 알고리즘이다.

Linear Time Sorting

선형 시간 정렬 알고리즘은 특정 조건을 만족하는 입력 데이터에 대해 O(n) 시간 복잡도를 달성하는 알고리즘이다. 즉, 입력 데이터의 크기에 비례하는 시간 안에 정렬을 완료할 수 있다. 이러한 알고리즘들은 비교 기반 정렬 알고리즘과 달리, 데이터의 값 자체를 이용하여 정렬을 수행한다.

Counting Sort

Counting Sort는 입력 배열의 각 요소가 0과 k 사이의 정수라는 가정 하에 동작한다. 

Counting sort code

코드를 살펴보면, counts에 특정값의 개수를 세고 개수만큼 result에 집어넣음으로써 구현된다.

counts

result

Counting sort는 k가 충분히 작을 때 매우 효율적이, 시간 복잡도는 O(n+k)이다. 하지만 k가 매우 큰 경우, Counting Sort는 비효율적이 된다. 예를 들어, 입력 배열의 요소가 0과 1,000,000 사이의 정수라면, Counting Sort는 O(n+1,000,000) 시간이 소요되어 O(n log n) 알고리즘보다 느릴 수 있다.
그리고 stable한 정렬 알고리즘으로, 입력 배열에서 같은 값을 갖는 요소들의 상대적인 순서가 정렬된 배열에서도 유지된다.

Bucket Sort

Bucket Sort는 입력 배열의 요소들이 균등 분포를 따른다는 가정 하에 동작한다. 

Bucket sort code

코드를 통해 Bucket sort는 Bucket들로 분할하고, 분할된 요소들을 정렬함으로써 수행됨을 알 수 있다.

Bucket

이때 k ≤ Bucket 수라면 저장할 index가 충분하므로 counting sort를 이용하여 정렬할 수 있고, k > Bucket 수라면 다른 stable sort를 이용해서 정렬한다.

Bucket sort는 '분할'의 특성에 의해 k가 커도 상관없지만, 입력 데이터가 균등 분포를 따르지 않으면 성능이 저하될 수 있다. 만약 입력 데이터가 균등 분포를 따르지 않는다면, 특정 버킷에 많은 요소가 몰릴 수 있다. 이 경우 해당 버킷 내에서 정렬하는 데 O(n log n) 시간이 소요될 수 있으며, 전체적인 성능이 저하된다. 

정리하면 최악의 경우 시간 복잡도는 O(n^2)이지만, 평균적으로 O(n) 시간 복잡도를 갖는다.

Radix Sort

Radix Sort는 입력 배열의 요소들이 d자리 정수라는 가정 하에 동작한다. 

Radix sort code

이 알고리즘은 각 자릿수에 대해 오름차순으로 stable한 정렬 알고리즘을 반복적으로 적용하여 정렬을 수행한다. 

Radix

Radix sort의 시간 복잡도는 O(d(n+k))이며, d가 작고 k가 n에 비해 크지 않을 때 효율적이다.

Radix Sort에서 stable한 정렬 알고리즘을 사용하는 이유는 각 자릿수를 정렬할 때 이전 자릿수의 정렬 순서를 유지하기 위해서이다. 만약 stable하지 않은 정렬 알고리즘을 사용한다면, 이전 자릿수에서 정렬된 순서가 섞여 최종 결과가 잘못될 수 있다.

결론

선형 시간 정렬 알고리즘은 특정 조건을 만족하는 입력 데이터에 대해 매우 효율적인 정렬 방법을 제공한다. Counting Sort는 k가 작을 때, Bucket Sort는 데이터가 균등 분포를 따를 때, Radix Sort는 d가 작을 때 효과적이다. 반면, 비교 기반 정렬 알고리즘은 입력 데이터에 대한 제약이 없지만, 최소 Ω(n log n) 시간이 소요된다. 따라서 각 알고리즘의 특징을 정확하게 이해하고, 입력 데이터의 특성에 맞는 알고리즘을 선택하는 것이 중요하다.

추천글 : 

[알고리즘] merge sort algorithm analysis
(https://hyeonb.blogspot.com/2024/09/merge-sort-algorithm-analysis.html)

[알고리즘] Algorithmic analysis - runtime with asymptotic analysis
(https://hyeonb.blogspot.com/2024/09/algorithmic-analysis-runtime-with.html)