알고리즘 - 힙정렬, 기수 정렬, 계수 정렬(Heap sort, Radix sort, Counting sort)

1) 힙 정렬

원리:

1. 배열 전체 최대 힙으로 바꾼다

2. 배열의 첫 원소(=최댓값)와 마지막 원소를 교환한다

3. 배열의 마지막 원소를 가르키는 포인터를 1 줄인다

4. 배열을 최대 힙으로 다시 바꿔준다

코드(파이썬):

def heapsort(a,n):
	for i in range(n//2-1,0,-1):
    		rebuildheap(a,i,n)
	heapsize = n
        for last in range(n-1,1,-1):
            a[0],a[last] = a[last],a[0]
            heapsize -= 1
            rebuildheap(a,0,heapsize)

def rebuildheap(a,r,n):
	current = r
        value = a[r]
        while 2*current + 1 < n:
            leftchild = 2*currrent + 1
            rightchild = leftchild + 1
            if rightchild < n and a[rightchild] > a[leftchild]:
                largerchild = rightchild
            else:
                largerchild = leftchild

            if value < a[largerchild]:
                a[current] = a[largerchild]
                current = largerchild
            else:
                break

        a[current] = value

시간복잡도:

O(nlogn)

 

2) 기수 정렬

원리:

1. 리스트 내의 최대 자릿수를 구한다

2. 각 원소들의 특정 자릿수의 숫자에 따라 원소들을 다른 배열에 담아둔다

3. 그 순서에 따라 원본리스트를 바꾼다

4. 최대 자릿수에 달할 때까지 2,3번을 반복한다

 

코드(파이썬):

def radixsort(a):
	maxval = max(a)
        digit = 1
        while int(maxval/digit) > 0:
            count(a,digit)
            digit *= 10

def count(a,digit):
	n = len(a)
    
        output = [0] * n
        count = [0] * 10

        for i in range(0,n):
            index = int(arr[i]/digit)
            count[index % 10] += 1

        for i in range(1,10):
            count[i] += count[i-1]

        i = n-1
        while i >= 0:
            index = int(arr[i]/digit)
            output[count[index%10]-1] = arr[i]
            count[index%10] -= 1
            i -= 1

        for i in range(0,len(arr)):
            arr[i] = output[i]

 

시간복잡도:

O(kn) 

*k는 가장 큰 데이터의 자릿수

 

데이터들의 자릿수가 크지 않고 고르게 분포돼 있다면, 다른 정렬 알고리즘보다 더 빠른

수행시간을 가진다. 입력을 잘 살피고 사용하면 상당히 유용할 것 같다.

 

3) 계수 정렬

원리:

1. 리스트 내 최대값의 크기를 지닌 배열을 선언한다

2. 리스트를 순회하며 값에 해당하는 인덱스의 배열원소를 1 증가시킨다 (값들의 수를 세서 저장한다)

3. 배열의 원소를 하나씩 빼면서 새로운 리스트에 저장한다

 

코드(파이썬):

def countingsort(a,b,k):
	for i in range(k):
            c[i] = 0
        for j in range(n-1):
            c[a[j]] += 1
        for i in range(k-1):
            c[i] = c[i] + c[i-1]
        for j in range(n-1,0,-1):
            b[c[a[j]-1]] = a[j]
            c[a[j]] -= 1

시간복잡도:

O(n+k)

*k는 리스트 내 최대값

 

시간복잡도 측면에서 기수 정렬보다도 빨라보이지만 k가 자릿수가 아닌 값이기에 상당히 쉽게 높아질 수 있다.

그만큼의 배열도 생성해야 하기에 메모리 측면에서도 불리한 점이 많은 정렬 방법이다.

상황을 신중히 따져 사용해야 할 것 같다.