Counting Sort

이번에는 기존과는 색다른 Sorting 알고리즘 입니다.

 

기존의 Sorting 알고리즘은 Element끼리 값을 "비교"를 통해서 값을 정렬하는 비교기반 알고리즘 이었습니다.

 

반면 Counting Sort 알고리즘은 Element의 분포를 기반으로 정렬하는 알고리즘이 되겠습니다.

Counting Sort는 가장먼저 Element 전체를 확인하고, 이를 기반으로 Element의 분포표를 얻게됩니다.

 

이제 이를 바탕으로 각 Element가 Sort 되었을 때 몇개의 칸을 차지할지를 알 수가 있습니다.

(예를들어서 7 같은 경우 Sorted List에서 3개의 칸을 차지할 것을 예상할 수 있습니다)

 

이제 Element를 순서대로 Sort List Frame에 집어넣어주면 됩니다.

 

(분포표가 있기 때문에, 특정 값의 Element가 어디 위치할 지는 쉽게 알수있습니다)

 

이때 4,5 번째 Element인 6을 봅니다.

 

6은 2개가 존재하기 때문에, 4번째 Element가 Sort List Frame에 들어가면서 이미 들어갈 자리를 차지하게 됩니다.

 

이때 원소가 없는 위치까지 이동 후 5번째 6을 삽입하게 됩니다.

 

각 Element의 분포를 고려하여 Frame이 생성되었기 때문에, 다른 Element와 섞일 위험이 없다고 할 수 있습니다.

 

이제 모든 Element에 대해서 위 과정을 반복하면, Sorting 된 List를 얻을 수가 있습니다.

 

해당 알고리즘은 Element의 분포를 찾는데 N, 그리고 분포를 기반으로 정렬하는데 N번의 반복문이 필요하며

 

이를 시간복잡도로 표현하면 O(n)의 시간복잡도를 보여줍니다!

 

비교기반의 정렬 알고리즘의 최대 성능이 O(nlogn)인것을 생각하면, 가장 빠른 성능이 예상되는것을 알 수 있습니다.

 

하지만, Element의 중복이 적을수록 알고리즘의 수행 시간이 증가하기 때문에

 

항상 고성능의 Sorting 알고리즘이라곤 할 수 없습니다.

 

아래는 Python으로 구현된 counting Sort 알고리즘입니다 :)

class counting_sort:
    def __init__(self, DT_list):
        #각 Element의 출현 횟수를 기록할 List를 정의합니다.
        self.counting_list = [0]*max(DT_list)        
        self.ori_list = DT_list
        #Sort된 List는 별도로 추가 할당이 필요합니다.
        self.sorted_list = [None]*len(self.ori_list)
        self.counting()
    
    #한차례 모든 Element를 확인 후 Element들의 분포를 확인합니다.
    def counting(self):
        for i in self.ori_list:
            self.counting_list[i-1] = self.counting_list[i-1] + 1    

        
    def sorting(self):
        #순서대로 Element를 뽑고, 해당 Element의 분포를 기반으로
        #Element의 시작 위치를 정합니다(this_index)
        for i in self.ori_list:            
            this_index = sum(self.counting_list[0:i-1])
            #이때, this_index 위치에 Element가 존재하면
            #Element가 없을때 까지 오른쪽으로 이동 후 Element를 삽입합니다.
            #Element의 분포를 기반으로 this_index를 산출하기 때문에
            #값이 다른 Element끼리 섞일 일이 없습니다.
            while True:
                if self.sorted_list[this_index] != None:
                    this_index = this_index +1
                else:
                    self.sorted_list[this_index] = i
                    break            
        #정렬된 List를 반환합니다.
        return self.sorted_list
    
    
import random
test = [random.randint(1,20) for i in range(50)]
==>[12, 17, 16, 19, 15, 10, 17, 19, 10, 9, 8, 15,\
     9, 4, 18, 18, 13, 10, 19, 1, 11, 15, 16, 19, 5,\
     13, 16, 1, 15, 19, 1, 13, 6, 17, 6, 5, 2, 8, 16,\
     4, 19, 10, 10, 2, 5, 6, 13, 4, 3, 17]
sort_oj = counting_sort(test)
sort_oj.sorting()
Out[27]: 
[1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 8, 8, 9,\
 9, 10, 10, 10, 10, 10, 11, 12, 13, 13, 13, 13, 15, 15,\
 15, 15, 16, 16, 16, 16, 17, 17, 17, 17, 18, 18, 19, 19,\
 19, 19, 19, 19]