[1007] CountingSort(계수정렬), HeapSort(힙정렬)

1. 해결 방안

각각의 100개와 5000개의 데이터 셋을 계수정렬(Counting Sort)와 힙정렬(Heap Sort)를 사용하여 데이터 셋을 정렬하는 것이 목표이다.

 

우선 힙정렬은 데이터 셋을 불러와 배열에 넣은 다음, 배열을 트리 형태로 추상화 시켜 생각하여 MAX Heap 기준으로 heapify를 실행하는 함수를 이용해 최대힙을 구현한다. 그리고 나서 최대값의 원소를 새로운 배열에 넣고 지운다음, 마지막 원소를 root 자리에 넣어주고 다시 heapify를 실행한다. 이 작업을 반복하여 내림차순으로 정렬된 데이터 셋을 얻을 수 있을 것으로 기대된다.

 

두번째로 계수정렬을 이용하여 데이터 셋을 정렬한다. 숫자의 범위를 0부터 100000까지 잡고 그에 맞는 Counting용 정렬을 만든 뒤, 본래 배열에서 수를 0부터 arrary.length만큼 증가시켜가며 인덱스를 하나하나씩 접근해가면서 그 인덱스 안에 있는 수를 Counting 배열의 인덱스로 접근하여 값을 1씩 증가시켜주며 각 배열의 수를 카운팅한다. 모든 배열의 인덱스를 돌고 카운팅을 마쳤다면 이것들을 누적합으로 바꿔준다. 이 다음에, NewArray를 만들어 원래 정렬 되어있지 않은 배열을 뒤에서부터 접근하며 그 안에 있는 수가 어느 자리에 들어가야하는지 Counting 배열을 참고하여 NewArray 배열에 넣어준다. 마지막으로 NewArray 배열을 원래 배열에 복사해주면 정렬이 끝나게 된다.

이러한 방법으로 두가지 배열을 구현해보았다. 구현한 배열은 아래의 코드와 같다.

 

2. 코드 분석

[Heap Sort]

Heap Sort의 함수는 Max_Heapify, Build_Max_Heap, Max_Heap_Sort 세가지가 존재한다. 차례대로 코드를 보면서 그에 대한 설명을 첨부한다.

 

 

우선 Max_Heapify를 보면, 이 함수는 힙을 정렬할 때 쓰이는 swap함수와 비슷한 역할을 하는 함수이다. 최대힙을 구현하는 것이 이 Heap Sort의 기준이므로, 최대 힙을 구현하기 위해서는 힙의 root 즉 배열의 1번째에 가장 큰 수가 들어가야 한다. (여기서는 배열의 크기를 원래 크기보다 일부러 1많게 설정했다. 부모가 있음을 확인하기 위해서 index/2를 해야하는데, 0부터 하면 이 방법의 구현이 어렵기 때문에 힙의 시작 인덱스를 1로 잡았다.) 이렇게 정렬하기 위해서는 배열의 마지막 부분부터 즉 각각의 노드가 부모가 있는지를 확인하면서 부모 노드가 자식 노드보다 작으면 자식 노드와 부모노드가 자리를 바꾸는 것을 반복하며 MAX HEAP을 만들게 된다. 이렇게 최대힙을 만들게 정렬할 때 쓰이는 함수가 이 함수이다.

다음 Build_Max_Heap 함수는 앞에서 보았던 heapify함수로 정렬이 되지 않은 배열을 힙으로 간주하고, 최대 힙 형태로 정렬을 처음 수행하는 역할을 한다. 여기서는 heapify를 한 번 수행하여 처음으로 최대힙 형태로 배열을 정렬해준다.

 

다음 Max_Heap_Sort함수는 Build_Max_Heap으로 만들어진 최대힙을 시작으로 정렬을 본격적으로 시작하게 되는 함수이다. 앞전의 실행으로 만들어진 최대힙의 인덱스 1번째를 보면 배열에서 가장 큰 수가 있게 된다. 그럼 이 수를 새로 만든 배열 SortArray의 인덱스 1번째에 담은 다음 다음 최대 수도 다음 인덱스에 담을 수 있도록 index를 증가시켜준다. 그 다음 root(인덱스 1)에 있는 최대 수를 정렬될 배열에 담았으면, 배열의 마지막 인덱스에 있는 수를 root에 삽입하고 size를 줄여준다음(범위를 줄여준다음) 다시 heapify 함수를 실행하여 다음 최대 수를 찾는다. 이렇게 찾은 수는 또 정렬될 배열에 넣는다. 이러한 동작을 반복하여 정렬을 완료한다. 정렬은 내림차순을 기준으로 했다.

참고로, loopNum은 heapify 함수가 몇 번 실행되었는지를 측정하기 위해서 사용되었다.

 

[Counting Sort]

계수 정렬은 앞서 구현 방법을 생각해본 것을 그대로 코드를 구현해보니 완성되었다. 계수 정렬을 실행하기 위해서는 다음 순서대로 구현을 하면 된다.

 

1.    배열의 수의 범위를 파악하고 수에 맞는 크기의 배열을 생성하기

2.    각 배열에 있는 수를 각각의 인덱스에 접근하여 Counting하기

3.    Counting한 배열을 누적합으로 변환하기

4.    누적합의 배열을 가지고 새로운 배열에 기존 배열을 참고하여 어느 자리에 정렬이 되어야 할지 판단하기

 

위와 같은 순서의 동작을 거치면 계수정렬이 끝나게 된다.

가지고 있는 5000개의 데이터셋은 1부터 5000까지 있는 데이터 셋으로 1부터 5000까지의 범위의 배열만 필요하지만, 100개의 수가 있는 배열은 수의 범위가 6~990000이었으므로 넉넉잡아서 100000으로 수의 범위를 잡아놓았다.

0부터 배열의 크기만큼 +1씩 하면서 인덱스에 있는 수에 해당하는 Counting 배열의 인덱스에 해당 숫자가 있을 때마다 1씩 증가시켰다. 이렇게 하여 나온 값에 i번째 배열에 i+1번째 배열의 값을 더해서 넣는 방식으로 누적합을 구하였고, 이렇게 구해진 누적합 배열 Counting Array로 기존 배열에 있는 수가 어떤 곳에 들어가야 할지 판단한다. 자리를 찾아간 수를 Counting 배열에서는 그 해당 인덱스에 있는 수를 1씩 감소시킨다.

 

3. 분석결과

이러한 방법으로 두 가지 배열에 대해 Output 출력이 생성된 결과는 아래와 같다. 힙정렬은 내림차순으로, 계수정렬은 오름차순으로 소팅이 잘 실행된 것을 볼 수 있다.

 

정렬된 것을 확인했으면, 이번에는 각 정렬별, 그리고 정렬 안에 있는 함수별로 수행시간을 비교해 보았다. Heap Sort에서는 각각의 함수 Build Heap과 Sorting 과정에서의 heapify 실행 횟수를 비교하는 것과, 전체 실행시간을 3번 실행후 나오는 5번의 밀리세컨드 평균을 구해보았다. Counting Sort에서도 밀리세컨드 단위로 수행 시간을 구하여 Heap

Sort와 수행 시간을 비교해 볼 예정이다. 우선 Heap Sort의 수행시간부터 분석해보았다.

 

[Heap Sort 수행시간 분석]

우선, 각각의 함수마다 heapify가 실행된 횟수를 알기 위해서 loop를 사용하면, 이것을 세는 시간도 수행되기 때문에 이 부분에 있어서 전체 횟수를 셀 때에서는 loop 구문을 따로 빼고 수행하였다.

 

Build Heap + Max Heap Sort 함수의 전체 수행시간에 대한 평균은 943초이고, Build Heap을 하는 것은 처음 정렬되지 않은 배열을 최대힙 형태로 만드는 것이므로 한 번만 수행하면 되어서 비교적 매우 적은 시간이 걸리는 것을 확인할 수 있다. 반면 Max Heap Sort 함수는 처음 build로 생성된 최대힙을 시작으로 계속 반복하여 최대힙을 만들고 최대값을 찾아서 정렬하는 형식이므로 시간이 오래 걸렸다.

여기서 알 수 있는 계수정렬의 시간 복잡도는, 계수 정렬은 힙을 사용하여 최대값을 찾고, 그 최대값을 배열에 넣어 정렬을 하는 방식으로 어쨌든 힙을 정렬해야하는 시간이 걸린다. 이러한 힙을 최대힙으로 정렬하는 시간은 n개의 데이터를, 트리의 높이만큼 계속 정렬해야하는 시간이 걸리므로 시간복잡도는 O(nlog2n)이 됨을 예상할 수 있다.

 

마지막으로 각각의 함수에 대해 heapify 함수가 실행되는 횟수를 비교해 보았다.

어찌보면 당연한 결과이다. Build max 함수에서 아무것도 정렬되지 않은 배열을 트리 형태로 간주하고 최대값을 찾기 위해 최대힙으로 만들기 위한 실행으로 초기에 한 번만 해주게 된다. Max Heap Sort에서는 5000개의 데이터가 정렬이 되어야 하므로 실행이 데이터의 숫자와 같이 된다. 이렇게 실행횟수까지 비교를 완료했다.

 

[Counting Sort의 수행시간 분석]

계수정렬에 대한 수행 시간의 평균은 아래와 같다.

 

 

 

평균 수행 시간은 4.8초로 힙정렬보다 훨씬 빠른 정렬 수행시간을 보여주었다.

이러한 결과로 인해 알 수 있는 계수정렬의 시간 복잡도는 데이터가 n개일 때, Array를 카운트하면서 Counting 배열에 각각의 숫자의 개수를 세는 것에 O(n)이 걸린다. Counting 배열을 가지고 Array를 역순으로 접근하면서 다시 새로운 배열을 만들때에도 O(n)이 걸리는 것을 예상할 수 있다. 그 전에 수를 센 Counting 배열에서, 누적합을 구할 때 직전요소와 현재요소를 더하는 것을 k번 만큼 반복해야 하므로 이는 k번(리스트 중 가장 큰 값)이 걸리는 것을 알 수 있다. 가장 큰 값이 Counting 배열의 크기가 되기 때문이다. 그래서 계수정렬의 시간복잡도는 O(n+k)로 예상할 수 있다. 그러나, 이 배열은 메모리 공간 낭비가 심해서 A의 최대값이 매우 큰 값이라면 비효율적인 알고리즘이 될 수 있다고 생각한다.