Chapter 3. Linear Time Sorting

Chapter : CLRS 8.1-8.2

 

1. Limit of Comparsion-based Sorting Algorithm
2. Counting Sort
3. Bucket Sort
4. Radix Sort

 

 

---

 

---

Limit of Comaprsion-based Sorting

우리가 아까 이전 챕터에서 본 Algorithm들은 element 두개를 비교한다.

이것을 트리로 만들어 보면?

 

 최소한 n!개의 leaf를 가진 tree로 변한다.

 

완전히 balanced tree라고 가정하면 log(n!)의 선택을 하게 되므로

복잡도는 최소 n log(n/e) = Ω(n log(n)) 이다.

log(n!) = Ω(n log(n))

 

log(1) + ... + log(n/2) + ... + log(n) >=

log(n/2) + ... + log(n) = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n) >=

log(n/2) + ... + log(n/2)

= n/2 * log(n/2)

그렇다면 어떻게 Linear Time Sorting을 하겠다는건지 궁금할 수 있다.

아래 예시를 보며 알아보자.

---

Counting Sort

def counting_sort(A, k):
    counts = [0] * k
    for i in range(len(A)):
        counts[A[i]] += 1
    result = []
    print(counts)
    for i in range(k):
        result.extend([i] * counts[i])
    return result

counting_sort([1,4,2,3,2,5,2,3,4,1,2],6)

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

 

Time : O(n+k)

 

---

Bucket Sort

 

def bucket_sort(A, k, num_buckets):
    num_buckets = min(num_buckets, k)
    buckets = [[] for i in range(num_buckets)]
    for i in range(len(A)):
        b = get_bucket(A[i], k, num_buckets)
        buckets[b].append(A[i])
    result = []
    print(buckets)
    if num_buckets < k:
        for j in range(num_buckets):
            result.extend(sorted(buckets[j]))
    else: #counting sort
        for j in range(num_buckets):
            result.extend(buckets[j])
    return result

def get_bucket(value, k, num_buckets):
    return math.floor(value/math.ceil(k / num_buckets))

bucket_sort([17, 13, 16, 12, 15, 1, 28, 0, 27],30,5)

[[1, 0], [], [17, 13, 16, 12, 15], [], [28, 27]]
[0, 1, 12, 13, 15, 16, 17, 27, 28]

Time : Θ(max{n log(n), n+k})

---

Radix Sort

def radix_sort(A, d, k):
    for i in range(d):
        A_pairs = make_pairs(A, k, i)
        print(A_pairs)
        A_new = bucket_sort_with_pairs(A_pairs, k)
        A = A_new
    return A
    
def make_pairs(A, k, i):
    result = []
    for a in A:
        key = int((a / (k ** i)) % k)
        result.append((key, a))
    return result
    
def bucket_sort_with_pairs(A_pairs, k):
    buckets = [[] for i in range(k)]
    result = []
    for i in range(len(A_pairs)):
        b = A_pairs[i][0]
        buckets[b].append(A_pairs[i][1])
    for j in range(k):
        result.extend(buckets[j])
    print(result)
    return result​

radix_sort([31,5,210,14,95,477,555,125],3,10)


[(1, 31), (5, 5), (0, 210), (4, 14), (5, 95), (7, 477), (5, 555), (5, 125)]
[210, 31, 14, 5, 95, 555, 125, 477]
[(1, 210), (3, 31), (1, 14), (0, 5), (9, 95), (5, 555), (2, 125), (7, 477)]
[5, 210, 14, 125, 31, 555, 477, 95]
[(0, 5), (2, 210), (0, 14), (1, 125), (0, 31), (5, 555), (4, 477), (0, 95)]
[5, 14, 31, 95, 125, 210, 477, 555]
[5, 14, 31, 95, 125, 210, 477, 555]​

Time : Θ(d(n+k))

 

와 같이 Comparision Based가 아닌 Sorting을 하면 O(N) time에 가까운 Sort를 할 수 있다.