글 작성자: ST_
728x90



 

[정렬 알고리즘 모음]

 

 

 

 

 

 

  • Heap Sort [힙 정렬]

 

 

 

 

 

힙 정렬은 기본적으로 힙 자료구조를 기반으로 하기 때문에 만약 힙을 모르신다면 이 글을 읽기 전에 반드시 '힙 자료구조'를 보고 오시길 바란다.

 

 

 

바로 위에서 말했듯 힙 정렬은 힙 자료구조를 기반으로 한다고 했다.

 

 

 

잠깐 힙 자료구조에 대해 말해보자면 이렇다.

 

힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'다.

위 문장에서 중요한 키워드 3가지가 있다. 바로 '최솟값 또는 최댓값' , '빠르게', '완전이진트리' 이다.

 

여러분이 어떤 리스트에 값을 넣었다가 빼낼려고 할 때, 우선순위가 높은 것 부터 빼내려고 한다면 대개 정렬을 떠올리게 된다.

쉽게 생각해서 숫자가 낮을 수록 우선순위가 높다고 가정할 때 매 번 새 원소가 들어올 때 마다 이미 리스트에 있던 원소들과 비교를 하고 정렬을 해야한다.

 

문제는 이렇게 하면 비효율적이기 때문에 좀 더 효율이 좋게 만들기 위하여 다음과 같은 조건을 붙였다.

 

'부모 노드는 항상 자식 노드보다 우선순위가 높다.'

 

즉, 모든 요소들을 고려하여 우선순위를 정할 필요 없이 부모 노드는 자식노드보다 항상 우선순위가 앞선다는 조건만 만족시키며 완전이진트리 형태로 채워나가는 것이다.

 

 

이를 조금만 돌려서 생각해보면 루트 노드(root node)는 항상 우선순위가 높은 노드라는 것이다. 이러한 원리로 최댓값 혹은 최솟값을 빠르게 찾아낼 수 있다는 장점(시간복잡도 : O(1))과 함께 삽입 삭제 연산시에도 부모노드가 자식노드보다 우선순위만 높으면 되므로 결국 트리의 깊이만큼만 비교를 하면 되기 때문에 O(logN) 의 시간복잡도를 갖아 매우 빠르게 수행할 수 있다.

 

그리고 위 이미지에서도 볼 수 있지만 부모노드와 자식노드간의 관계만 신경쓰면 되기 때문에 형제 간 우선순위는 고려되지 않는다.

이러한 정렬 상태를 흔히 '반 정렬 상태' 혹은 '느슨한 정렬 상태' , '약한 힙(weak heap)'이라고도 불린다.

 

 

 

그럼 이런 질문이 나올 수 있다. "왜 형제간의 대소비교가 필요 없다는 거죠?"

우선순위가 높은 순서대로 뽑는 것이 포인트다. 즉, 원소를 넣을 때도 우선순위가 높은 순서대로 나올 수 있도록 유지가 되야하고 뽑을 때 또한 우선순위가 높은 순서 차례대로 나오기만 하면 된다.

 

 

 

 

 

힙 자료구조는 크게 두 가지로 나뉘는데, 최대 힙과 최소 힙이다. (바로 위 이미지에서는 최소 힙에 해당한다.)

 

힙은 우선순위가 높은 순서대로 나온다고 했다. 이 말은 여러분이 어떻게 우선순위를 매기냐에 따라 달라지겠지만, 기본적으로 정수, 문자, 문자열 같은 경우 언어에서 지원하는 기본 정렬 기준들이 있다.

 

예로들어 정수나 문자의 경우 낮은 값이 높은 값보다 우선한다.

우리가 예로 {3, 1, 6, 4} 를 정렬한다고 하면 낮은 순서대로 {1, 3, 4, 6} 이렇게 정렬하게 된다. 이렇게 정렬되는 순서, 즉 기본적으로 어떤 것을 우선순위가 높다고 할지에 따라 두 가지로 나뉜다.

 

 

 

 

 

 

최소 힙 : 부모 노드의 값(key 값) ≤ 자식 노드의 값(key 값)

최대 힙 : 부모 노드의 값(key 값) ≥ 자식 노드의 값(key 값)

 

이렇게 두 가지로 나뉜다.

 

 

 

 

 

 

 

 

 

그럼 위의 트리 구조를 어떻게 구현할 것인가?

가장 표준적으로 구현되는 방식은 '배열' 이다. 물론 연결리스트로도 구현이 가능하긴 하지만, 문제는 특정 노드의 '검색', '이동' 과정이 조금 더 번거롭기 때문이다.

배열의 경우는 특정 인덱스에 바로 접근할 수가 있기 때문에 좀 더 효율적이기도 하다. 

 

 

배열로 구현하게 되면 특징 및 장점들이 있다. 일단 아래 그림을 한 번 봐보도록 하자.

 

 

 

위 이미지를 보면 볼 수 있는데, 각 인덱스별로 채워넣으면 특이한 성질이 나온다. 정리하자면 다음과 같다.

 

(아마 필자가 포스팅한 힙 자료구조 구현과는 시작 인덱스가 다를 것이다. 우리는 기존 배열을 정렬해야하므로 첫 번째 인덱스는 0부터 시작하는 것으로 하겠다.)

 

 

[성질]

1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1

2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 2

3. 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2

 

위 세개의 법칙은 절대 변하지 않는다.

예로들어 index 3 의 왼쪽 자식 노드를 찾고 싶다면 3 × 2 + 1를 해주면 된다. 즉 index 7 이 index 3 의 자식 노드라는 것이다.

반대로 index 5의 부모 노드를 찾고 싶다면 (5 - 1) / 2 를 해주면 된다.(몫만 취함) 그러면 2 이므로 index 2가 index 5의 부모노드라는 것이다.

 

 

 

 

 

 

 

 

 

 

 

 




  • 힙 정렬과 힙 자료구조

 



 

 

 

 

다시 힙 정렬로 돌아가보자.

 

아마 위의 글로만 보자면 힙 자료구조로 어떻게 정렬을 한다는 것이지? 라고 의아해 할 수도 있다. 한 번 복기해보자. 힙 자료구조는 우선순위가 가장 높은 노드가 root노드, 배열로 치자면 첫 번째 원소를 의미하고 있다.

 

그리고 힙 자료구조는 우선순위 큐 자료구조를 구현하는데 기반이 된다고 했다. (우선순위 큐도 현재 리스트 내에 우선순위가 높은 순서대로 원소를 반환하는 자료구조이기 때문이다.)

 

 

여기서 한 가지 아이디어를 떠올린 것이다. 배열을 힙으로 만들어서 정렬을 하면 되지 않을까?

 

쉽게 말하면 힙 자료구조를 기반으로 구현된 우선순위 큐 자료구조를 이용하여 다음과 같이 만들면 정렬이 되는 것이다.

 

import java.util.PriorityQueue;

public class test {
	public static void main(String[] args) {
    
		int[] arr = {3, 7, 5, 4, 2, 8};
		System.out.print(" 정렬 전 original 배열 : ");
		for(int val : arr) {
			System.out.print(val + " ");
		}
		
		PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
		
		// 배열을 힙으로 만든다.
		for(int i = 0; i < arr.length; i++) {
			heap.add(arr[i]);
		}
		
		// 힙에서 우선순위가 가장 높은 원소(root노드)를 하나씩 뽑는다.
		for(int i = 0; i < arr.length; i++) {
			arr[i] = heap.poll();
		}
		
		
		System.out.print("\n 정렬 후 배열 : ");
		for(int val : arr) {
			System.out.print(val + " ");
		}
		
	}
}

 

 

[결과]

 

 

 

 

 

 

하지만 위처럼 힙을 만들기 위한 별도의 공간을 마련하는 것은 메모리를 그만큼 따로 잡아줘야 하기 떄문에 비효율적인 것 같다.

그러면 어떻게 해야할까?

 

한 번 고민해보자.

 

일단 가장 첫 번째로 해야 할 것은 기존 배열을 힙 트리 상태로 만들어야 한다는 점이다. 그 다음에는 힙 트리로 구성 된 배열을 정렬을 해야 한다.

 

자세한 내용은 밑의 다음 파트에서 보도록 하자.

 

 

 

 

 

 

 

 

 

 

 

 

 

 




  • 정렬 방법

 



 

 

 

이참에 위 코드에서 예로 들었던 {3, 7, 5, 4, 2, 8} 을 기준으로 한 번 보도록 하자.

 

먼저 위 배열을 그대로 완전이진트리 형태로 본다면 다음과 같을 것이다.

 

 

위 배열은 아직 힙은 아니다. 위 상태에 이제 힙 조건, 정확하게는 최대 힙(max heap) 조건을 만족하도록 재구성을 해야한다.

 

오름차순으로 정렬할 것인데 왜 최대 힙을 만드는 것인가요?

힙은 부모노드와 자식노드의 우선순위여 항상 부모노드가 자식노드보다 우선순위가 높다는 것이다. 이 때 형제노드 사이에서의 우선순위는 고려되지 않는다.

즉, 힙 구조는 반 정렬 상태이지 완전정렬상태가 아니다.

 

바로 이 점 때문에 오름차순으로 구현 할 시, 최소 힙으로 정렬하여 쓰게 되면 형제간의 우선순위는 고려되지 않아 제대로 정렬이 되지 않는다.

 

위 예시의 배열을 최소 힙으로 만들면 {2, 5, 3, 7, 8, 4} 이러한 형태여도 정렬된 상태로 보게 되어버린다는 것이다.

 

잘못된 정렬

 

결과적으로 우리는 최종 결과물이 오름차순으로 정렬된 형태를 원하기 때문에 한 과정을 추가하는 것이다. 바로 최대 힙을 구성하여 root노드가 항상 큰 값을 가지게 만들고 그렇게 만들어진 최대 힙에서 root노드 값을(큰 값)을 하나씩 삭제하며 뒤에서부터 배치하는 것이다.

 

즉, 전체적인 과정은 다음과 같다.

 

 

 

 

 

 

 

아마 가장 궁금한 것은 최대 힙에서 정렬로 가는 과정일 것이다.

 

그럼 차근차근 구현해보도록 하자.

 

 

 

 

 

 

 

[과정 1] : 최대 힙 만들기

 

 

최대 힙 만드는 방법 자체는 여러 방법이 있지만, 우리가 왜 힙 자료구조를 통해 저장한뒤 반환하는 형식이 아니라 따로 구현하는 이유를 필자가 초반에 말했다.

 

바로 추가적인 메모리 공간을 생성하지 않고 원본 배열 안에서 정렬하기 위함이었다.

 

즉, 초기 상태의 배열 자체를 별도의 배열 선언 없이 최대 힙으로 만들어야 한다. 방법은 간단하다.

'가장 작은 서브트리부터 최대 힙을 만족하도록 순차적으로 진행하는 것이다.

 

무슨 말인가 싶을테니 아래 그림을 보면서 이해해보도록 하자.

 

 

 

 

 

 

 

 

 

 

위와 같이 힙을 만드는 과정을 'heapify' 라고도 한다. 그리고 heapify는 부모노드(상위 노드)부터 자식노드(하위 노드)로 진행되기 때문에 sift-down 과정이라고도 한다.

 

 

알고리즘으로 어떻게 작성해야 할까? 일단, 아래 코드를 보고 이해해보자.

 

public class HeapSort {

	// 부모 인덱스를 얻는 함수
	private static int getParent(int child) {
	    return (child - 1) / 2;
	}

	// 두 인덱스의 원소를 교환하는 함수
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	

	// 힙을 만드는 함수
	private static void heapify(int[] a, int parentIdx, int lastIdx) {
		
		/*
		 * 현재 트리에서 부모 노드의 자식노드 인덱스를 각각 구해준다.
		 * 현재 부모 인덱스를 가장 큰 값을 갖고있다고 가정한다.
		 */
		int leftChildIdx = 2 * parentIdx + 1;
		int rightChildIdx = 2 * parentIdx + 2;
		int largestIdx = parentIdx;
		
		/*
		 *  left child node와 비교
		 *  
		 *  자식노드 인덱스가 끝의 원소 인덱스를 넘어가지 않으면서
		 *  현재 가장 큰 인덱스보다 왼쪽 자식노드의 값이 더 클경우
		 *  가장 큰 인덱스를 가리키는 largestIdx를 왼쪽 자식노드인덱스로 바꿔준다.
		 *  
		 */
		if(leftChildIdx <= lastIdx && a[largestIdx] < a[leftChildIdx]) {
			largestIdx = leftChildIdx;
		}
		
		/*
		 *  left right node와 비교
		 *  
		 *  자식노드 인덱스가 끝의 원소 인덱스를 넘어가지 않으면서
		 *  현재 가장 큰 인덱스보다 오른쪽 자식노드의 값이 더 클경우
		 *  가장 큰 인덱스를 가리키는 largestIdx를 오른쪽 자식노드인덱스로 바꿔준다.
		 *  
		 */
		if(rightChildIdx <= lastIdx && a[largestIdx] < a[rightChildIdx]) {
			largestIdx = rightChildIdx;
		}
		
		/*
		 * largestIdx 와 부모노드가 같지 않다는 것은
		 * 위 자식노드 비교 과정에서 현재 부모노드보다 큰 노드가 존재한다는 뜻이다.
		 * 그럴 경우 해당 자식 노드와 부모노드를 교환해주고,
		 * 교환 된 자식노드를 부모노드로 삼은 서브트리를 검사하도록 재귀 호출 한다.
		 */
		if(parentIdx != largestIdx) {
			swap(a, largestIdx, parentIdx);
			heapify(a, largestIdx, lastIdx);
		}
	}

}

 

 

 

주석으로도 설명을 달아놓았다.

 

배열을 트리로 볼 때, 현재의 부모 노드(parentIdx)의 서브트리에서 양쪽의 자식노드와 비교한 후 가장 큰 값을 갖고있는 인덱스와 교환을 한다.

 

그리고 위의 이미지에서 3단계처럼 서브트리 깊이가 2 이상인 경우에는 교환 된 자식노드의 서브트리도 힙을 만족하도록 해야한다. 

즉, 재귀호출을 이용하여 교환된 자식노드의 인덱스(largestIdx)를 부모노드 파라미터로 넘겨준다.

 

 

 

 

 

 

 

 

 

위 처럼 힙을 만드는 알고리즘을 짰으면 이제 해당 함수를 호출을 해야한다.

다시 위의 이미지로 돌아가보자.

 

 

 

 

 

 

 

 

 

위에서 가장 첫 번째로 검사하는 노드는 '가장 마지막 노드의 부모 노드 서브트리다.'

(자식 노드가 없는 부모노드는 검사할 것이 없기 때문)

 

 

무슨 말이냐, 처음 배열 {3, 7, 5, 4, 2, 8} 에서 가장 마지막 노드는 8이고 인덱스는 배열의 사이에서 1을 뺀, 즉 size - 1 (=arr[5])이 마지막 노드다.

여기서 마지막 노드의 부모노드는 (size - 1) / 2 인 2(=arr[2]) 가 부모노드라는 것이다.

 

즉, 인덱스가 2부터 시작하여 그에 대한 서브트리에 대해 힙을 만족시킨다. 그리고서 서브트리가 힙을 만족하게 되면, 다음 검사할 노드인 인덱스 1의 노드에 대해 서브트리를 검사하면 된다.

 

즉, arr[2] 의 서브트리를 검사한 뒤, arr[1]의 서브트리를 검사하고, 마지막으로 arr[0]에 대한 서브트리(사실상 전체 트리)를 검사하는 것이다.

 

 

즉, 힙 상태로 만들기 위해 heapify를 호출할 때는 다음과 같이 해야한다는 점이다.

 

public class HeapSort {


	public static void heapsort(int[] arr) {
		int size = arr.length;

		/*
		 * 부모노드와 heaify과정에서 음수가 발생하면 잘못 된 참조가 발생하기 때문에
		 * 원소가 1개이거나 0개일 경우는 정렬 할 필요가 없으므로 바로 함수를 종료한다.
		 */
		if(size < 2) {
			return;
		}
		// 가장 마지막 노드의 부모 노드 인덱스 
		int parentIdx = getParent(size - 1);
		
		// max heap 만들기
		for(int i = parentIdx; i >= 0; i--) {

			// 부모노드(i값)을 1씩 줄이면서 heap 조건을 만족시키도록 재구성한다.
			heapify(a, i, size - 1);
		}

	}


	// 힙을 만드는 함수
	private static void heapify(int[] a, int parentIdx, int lastIdx) {
		
		/*
		  heapify 코드(생략)
		 */
	}

}

 

 

 

 

위와같이 하면 일단은 최대 힙(max heap)으로 arr 배열이 재구성 될 것이다.

참고로 주석으로도 써놓았지만, 원소가 0개이거나 1개일 경우 getParent 혹은 heapify 과정에서 음수가 발생하여 잘못 된 참조가 될 수 있다. 그렇기 때문에 해당 예외만 잘 처리해주도록 하자.

 

 

 

 

 

 

 

 

 

 

 

 

[과정 2] : 정렬하기

 

 

 

 

이제 위 과정1을 거치면 거의 끝난거나 마찬가지다. 다왔으니 좀만 더 힘내보자..

 

최대 힙을 만들었으면 이제 오름차순으로 정렬해야 한다. 저걸 어떻게 오름차순으로 정렬한다는 것이지? 심지어 내림차순으로도 완전 정렬상태가 아닌데...?

 

이렇게 생각이 들 수 있다.

 

하지만 조금만 생각해보자. 힙은 뭐라고 했더라? 바로 "최댓값 혹은 최솟값을 빠르게 찾기 위한 자료구조"였다.

이는 무슨말인가? 

 

우리가 구성한 힙은 최대 힙이었다. 즉, 항상 root노드(최상위 노드)는 최댓값을 갖고있다는 것이다. 그럼 이를 이용하여 그 최댓값을 하나씩 삭제하면서 배열의 맨 뒤부터 채워나가면 되지 않는가?

 

과정으로 보면 이렇게 된다.

 

root 원소를 배열의 뒤로 보냄 → 뒤에 채운 원소를 제외한 나머지 배열 원소들을 다시 최대 힙을 만족하도록 재구성한다.

 

 

역시 말로 하면 잘 이해가 안 갈 것 같다. 이미지를 보면서 이해해보도록 하자.

 

 

 

 

 

 

위와 같이 각 단계에서 root노드(최댓값)와 뒷 원소를 교환하고, 그 위치를 제외한 부분 트리에 대해 힙을 만족하도록 재구성하는 것이다.

 

 

즉, 따로 힙을 재구성하는 메소드를 작성할 필요 없이 앞서 작성한 heapify 메소드를 활용하면 된다.

 

public class HeapSort {


	public static void heapsort(int[] arr) {
		int size = arr.length;

		/*
		 * 부모노드와 heaify과정에서 음수가 발생하면 잘못 된 참조가 발생하기 때문에
		 * 원소가 1개이거나 0개일 경우는 정렬 할 필요가 없으므로 바로 함수를 종료한다.
		 */
		if(size < 2) {
			return;
		}

		// 가장 마지막 노드의 부모 노드 인덱스 
		int parentIdx = getParent(size - 1);
		
		// max heap 만들기
		for(int i = parentIdx; i >= 0; i--) {

			// 부모노드(i값)을 1씩 줄이면서 heap 조건을 만족시키도록 재구성한다.
			heapify(a, i, size - 1);
		}


		// 정렬 과정
		for(int i = size - 1; i > 0; i--) {
			
			/*
			 *  root인 0번째 인덱스와 i번째 인덱스의 값을 교환해준 뒤
			 *  0 ~ (i-1) 까지의 부분트리에 대해 max heap을 만족하도록
			 *  재구성한다.
			 */
			swap(a, 0, i);
			heapify(a, 0, i - 1);
		}
	}


	// 힙을 만드는 함수
	private static void heapify(int[] a, int parentIdx, int lastIdx) {
		
		/*
		  heapify 코드(생략)
		 */
	}

}

 

 

얼핏 보기에는 힙을 구성하는 단계에서 시간이 많이 소요 될 것 같지만 O(nlogn)의 시간복잡도를 갖는다. (자세한 것은 아래에서 증명하도록 하겠다.)

 

 

이 것으로 정렬 과정 자체는 끝난다.

 

 

 

 

 

 

 

 

 

 

 

개선하기 

 

 

 

 

 

이렇게 구현을 했지만 뭔가 찜찜하다. heapify 메소드는 재귀호출을 한다는 점이다. 다시 한 번 heapify 코드를 보자.

 

public class HeapSort {
	
	/*
	 * 중간 코드 생략
	 */

	private static void heapify(int[] a, int parentIdx, int lastIdx) {

		int leftChildIdx = 2 * parentIdx + 1;
		int rightChildIdx = 2 * parentIdx + 2;
		int largestIdx = parentIdx;

		if(leftChildIdx <= lastIdx && a[largestIdx] < a[leftChildIdx]) {
			largestIdx = leftChildIdx;
		}
		
		if(rightChildIdx <= lastIdx && a[largestIdx] < a[rightChildIdx]) {
			largestIdx = rightChildIdx;
		}

		if(parentIdx != largestIdx) {
			swap(a, largestIdx, parentIdx);
			heapify(a, largestIdx, lastIdx);	// 재귀 호출이 발생
		}
	}

}

 

 

위 코드에서 마지막 부분 heapify(a, largestIdx, lastIdx) 부분이 재귀 호출을 부른다.

 

만약에 재귀 호출을 할 경우 정렬해야 할 원소가 많아지고, 매 재귀마다 부모노드와 자식노드가 교환된다면 최악의 경우 트리의 높이(깊이)만큼 재귀 호출이 발생한다는 뜻이고, 이는 자칫 StackOverFlow 가 발생할 수 있으며 메모리도 많이 잡아먹는다는 말이다.

그러니 이 것을 재귀가 아닌 반복문 형식으로 구현 할 순 없을까?

 

물론 가능하다.

 

 

public class HeapSort {

	/*
	 * 중간 코드 생략
	 */
	
	private static void heapify(int[] a, int parentIdx, int lastIdx) {
		
	    int leftChildIdx;
	    int rightChildIdx;
	    int largestIdx;

	    /*
	     * 현재 부모 인덱스의 자식 노드 인덱스가 
	     * 마지막 인덱스를 넘지 않을 때 까지 반복한다.
	     * 
	     * 이 때 왼쪽 자식 노드를 기준으로 해야 한다.
	     * 오른쪽 자식 노드를 기준으로 범위를 검사하게 되면
	     * 마지막 부모 인덱스가 왼쪽 자식만 갖고 있을 경우
	     * 왼쪽 자식노드와는 비교 및 교환을 할 수 없기 때문이다. 
	     */
	    while((parentIdx * 2) + 1 <= lastIdx) {
	        leftChildIdx = (parentIdx * 2) + 1;
	        rightChildIdx = (parentIdx * 2) + 2;
	        largestIdx = parentIdx;

	        /*
	         * left child node와 비교 
	         * (범위는 while문에서 검사했으므로 별도 검사 필요 없음)
	         */
	        if (a[leftChildIdx] > a[largestIdx]) {
	            largestIdx = leftChildIdx;
	        }

	        /*
	         * right child node와 비교 
	         * right child node는 범위를 검사해주어야한다. 
	         */
	        if (rightChildIdx <= lastIdx && a[rightChildIdx] > a[largestIdx]) {
	            largestIdx = rightChildIdx;
	        }

	        /*
	         * 교환이 발생했을 경우 두 원소를 교체 한 후
	         * 교환이 된 자식노드를 부모 노드가 되도록 교체한다. 
	         */
	        if (largestIdx != parentIdx) {
	            swap(a, parentIdx, largestIdx);
	            parentIdx = largestIdx;
	        } 
	        else {
	            return;
	        }
	    }
	}
}

 

 

위와 같이 반복문으로 바꿔주면 성능 측면에서 좀 더 개선시킬 수 있다.

 

당장 이해하기에는 재귀적 방식이 훨씬 이해하기 편할 것이다. 그래서 먼저 전체적인 구조를 이해하고자 재귀 방식을 먼저 설명드렸던 것이다.

 

 

 

 

 

 

 

 

 

 

 

그리고 혹시 몰라 움직이는 이미지로 이해할 수 있도록 이미지를 첨부했다.

전체적인 흐름을 보자면 다음과 같은 형태로 정렬 한다.

 

 

https://en.wikipedia.org/wiki/Heapsort

 

 

https://en.wikipedia.org/wiki/Heapsort

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그 외에도 많은 참고 영상들이 있는데, 영상으로 보는 것이 더 쉬울 것 같아 같이 첨부하도록 하겠다.

 

https://www.youtube.com/watch?v=_bkow6IykGM

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 




  • Heap Sort 구현하기

 

 

 

 

그럼 그동안 구현했던 코드들을 합쳐서 한 번 보도록 하자.

 

 

[재귀 형식]

public class HeapSort {

	public static void sort(int[] a) {
		sort(a, a.length);
	}
	
	private static void sort(int[] a, int size) {

		/*
		 * 부모노드와 heaify과정에서 음수가 발생하면 잘못 된 참조가 발생하기 때문에
		 * 원소가 1개이거나 0개일 경우는 정렬 할 필요가 없으므로 바로 함수를 종료한다.
		 */
		if(size < 2) {
			return;
		}

		/*
		 * left child node = index * 2 + 1
		 * right child node = index * 2 + 2
		 * parent node = (index - 1) / 2
		 */
		
		// 가장 마지막 요소의 부모 인덱스 
		int parentIdx = getParent(size - 1);
		
		// max heap
		for(int i = parentIdx; i >= 0; i--) {
			heapify(a, i, size - 1);
		}

		
		for(int i = size - 1; i > 0; i--) {
			
			/*
			 *  root인 0번째 인덱스와 i번째 인덱스의 값을 교환해준 뒤
			 *  0 ~ (i-1) 까지의 부분트리에 대해 max heap을 만족하도록
			 *  재구성한다.
			 */
			swap(a, 0, i);
			heapify(a, 0, i - 1);
		}
		
	}
	
	
	// 부모 인덱스를 얻는 함수
	private static int getParent(int child) {
	    return (child - 1) / 2;
	}

	// 두 인덱스의 원소를 교환하는 함수
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	// 힙을 재구성 하는 함수
	private static void heapify(int[] a, int parentIdx, int lastIdx) {
		
		/*
		 * 현재 트리에서 부모 노드의 자식노드 인덱스를 각각 구해준다.
		 * 현재 부모 인덱스를 가장 큰 값을 갖고있다고 가정한다.
		 */
		int leftChildIdx = 2 * parentIdx + 1;
		int rightChildIdx = 2 * parentIdx + 2;
		int largestIdx = parentIdx;
		
		/*
		 *  left child node와 비교
		 *  
		 *  자식노드 인덱스가 트리의 크기를 넘어가지 않으면서
		 *  현재 가장 큰 인덱스보다 왼쪽 자식노드의 값이 더 클경우
		 *  가장 큰 인덱스를 가리키는 largestIdx를 왼쪽 자식노드인덱스로 바꿔준다.
		 *  
		 */
		if(leftChildIdx <= lastIdx && a[largestIdx] < a[leftChildIdx]) {
			largestIdx = leftChildIdx;
		}
		
		/*
		 *  left right node와 비교
		 *  
		 *  자식노드 인덱스가 트리의 크기를 넘어가지 않으면서
		 *  현재 가장 큰 인덱스보다 오른쪽 자식노드의 값이 더 클경우
		 *  가장 큰 인덱스를 가리키는 largestIdx를 오른쪽 자식노드인덱스로 바꿔준다.
		 *  
		 */
		if(rightChildIdx <= lastIdx && a[largestIdx] < a[rightChildIdx]) {
			largestIdx = rightChildIdx;
		}
		
		/*
		 * largestIdx 와 부모노드가 같지 않다는 것은
		 * 위 자식노드 비교 과정에서 현재 부모노드보다 큰 노드가 존재한다는 뜻이다.
		 * 그럴 경우 해당 자식 노드와 부모노드를 교환해주고,
		 * 교환 된 자식노드를 부모노드로 삼은 서브트리를 검사하도록 재귀 호출 한다.
		 */
		if(parentIdx != largestIdx) {
			swap(a, largestIdx, parentIdx);
			heapify(a, largestIdx, lastIdx);
		}
	}
}

 

 

 

 

 

[개선된 형식]

 

public class HeapSort {

	public static void sort(int[] a) {
		sort(a, a.length);
	}
	
	private static void sort(int[] a, int size) {

		/*
		 * 부모노드와 heaify과정에서 음수가 발생하면 잘못 된 참조가 발생하기 때문에
		 * 원소가 1개이거나 0개일 경우는 정렬 할 필요가 없으므로 바로 함수를 종료한다.
		 */
		if(size < 2) {
			return;
		}

		/*
		 * left child node = index * 2 + 1
		 * right child node = index * 2 + 2
		 * parent node = (index - 1) / 2
		 */
		
		// 가장 마지막 요소의 부모 인덱스 
		int parentIdx = getParent(size - 1);
		
		// max heap
		for(int i = parentIdx; i >= 0; i--) {
			heapify(a, i, size - 1);
		}

		
		for(int i = size - 1; i > 0; i--) {
			
			/*
			 *  root인 0번째 인덱스와 i번째 인덱스의 값을 교환해준 뒤
			 *  0 ~ (i-1) 까지의 부분트리에 대해 max heap을 만족하도록
			 *  재구성한다.
			 */
			swap(a, 0, i);
			heapify(a, 0, i - 1);
		}
		
	}
	
	
	// 부모 인덱스를 얻는 함수
	private static int getParent(int child) {
	    return (child - 1) / 2;
	}

	// 두 인덱스의 원소를 교환하는 함수
	private static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	
	private static void heapify(int[] a, int parentIdx, int lastIdx) {
		
	    int leftChildIdx;
	    int rightChildIdx;
	    int largestIdx;

	    /*
	     * 현재 부모 인덱스의 자식 노드 인덱스가 
	     * 마지막 인덱스를 넘지 않을 때 까지 반복한다.
	     * 
	     * 이 때 왼쪽 자식 노드를 기준으로 해야 한다.
	     * 오른쪽 자식 노드를 기준으로 범위를 검사하게 되면
	     * 마지막 부모 인덱스가 왼쪽 자식만 갖고 있을 경우
	     * 왼쪽 자식노드와는 비교 및 교환을 할 수 없기 때문이다. 
	     */
	    while((parentIdx * 2) + 1 <= lastIdx) {
	        leftChildIdx = (parentIdx * 2) + 1;
	        rightChildIdx = (parentIdx * 2) + 2;
	        largestIdx = parentIdx;

	        /*
	         * left child node와 비교 
	         * (범위는 while문에서 검사했으므로 별도 검사 필요 없음)
	         */
	        if (a[leftChildIdx] > a[largestIdx]) {
	            largestIdx = leftChildIdx;
	        }

	        /*
	         * right child node와 비교 
	         * right child node는 범위를 검사해주어야한다. 
	         */
	        if (rightChildIdx <= lastIdx && a[rightChildIdx] > a[largestIdx]) {
	            largestIdx = rightChildIdx;
	        }

	        /*
	         * 교환이 발생했을 경우 두 원소를 교체 한 후
	         * 교환이 된 자식노드를 부모 노드가 되도록 교체한다. 
	         */
	        if (largestIdx != parentIdx) {
	            swap(a, parentIdx, largestIdx);
	            parentIdx = largestIdx;
	        } 
	        else {
	            return;
	        }
	    }
	}
}

 

 

 

이렇게 두 가지로 나누어 구현 할 수 있다.

 

 

대부분의 경우 정렬 과정은 최대한 재귀는 피하여 구현하는게 일반적이기 때문에 반복문으로 구현하는 것이 좋다.

 

 

 

 

 

 

 

 

 

 




 

  • 힙 정렬의 장점 및 단점




[장점]

1. 최악의 경우에도 O(NlogN) 으로 유지가 된다.

2. 힙의 특징상 부분 정렬을 할 때 효과가 좋다.

 

 

 

[단점]

1. 일반적인 O(NlogN) 정렬 알고리즘에 비해 성능은 약간 떨어진다.

2. 한 번 최대 힙을 만들면서 불안정 정렬 상태에서 최댓값만 갖고 정렬을 하기 때문에 안정정렬이 아니다.

 

 

 

 

 

위에서 시간 복잡도에 대해 O(NlogN) 으로 유지가 된다고 했다.

 

왜 그러한 시간복잡도가 나오는지 한 번 같이 알아보도록 하자. 일단, 시간복잡도 구하는 과정은 조금 어려우니 이 점 유의하시길 바란다.

 

일단, 여러분이 기본적으로 알아야 할 것은 다음과 같다.

바로 노드의 개수와 트리의 높이 사이의 상관관계다.

 

우리가 포화이진트리라고 가정하고 볼 때 다음과 같은 과정을 거친다.

 

위의 과정을 보면 매 번 차수(h)가 증가할 때 마다 2의 배수 씩 추가 되는 것을 볼 수 있다.

즉,

d = 1 일 때, 노드의 개수는 1

d = 2 일 때, 노드의 개수는 (1 + 2)

d = 2 일 때, 노드의 개수는 (1 + 2 + 4)

             ⋯

d = n 일 때 노드의 개수는 (1 + 2 + 4 + ⋯ + 2n-1)

 

즉, N번째에 더해주는 수는 2n-1 이므로 이를 일반화하여 공식을 적용하면

 

즉, 트리의 차수(레벨) d 에 대하여 노드의 개수는 다음과 같이 표현할 수 있다.

N = 2d - 1

 

위를 거꾸로 노드의 개수에 대해 h(높이)를 구하고자 한다면 높이는 차수의 - 1 이므로 위에서 구한 식에서 다음과 같이 변형 할 수 있다.

 

위와 같이 구할 수 있다.

 

이 때 N의 가정은 포화이진트리를 조건으로 했기 때문에 항상 모든 노드가 꽉 차 있지만, 포화이진트리 뿐만 아니라 완전 이진트리에도 적용시키면 다음과 같이 나타내면 된다. 정수값만 갖고오면 되기 때문에 다음과 같이 나타낼 수 있다.

 

 

 

자 그럼 본격적으로 시간 복잡도를 구해보자.

 

우리는 크게 두 가지 과정을 거쳤다.

1. heapify를 통해 초기 배열을 max heap으로 만드는 과정

2. root노드를 뒤로 넘기고(삭제) 나머지 원소들을 heap으로 만드는 과정

 

 

일단, heapify 알고리즘 자체는 트리의 깊이만큼 비교 교환이 이루어지기 때문에 heapify 자체는 O(logN)의 시간복잡도를 갖고있다.

 

그러면 다들 이렇게 생각 할 수 있다.

"부모 인덱스부터 차례대로 줄여가면서 heapify를 해줬으니 ((N-1)/2)*logN, 즉 O(NlogN)의 시간복잡도를 갖겠네?"

int parentIdx = getParent(size - 1);

for(int i = parentIdx; i >= 0; i--) {
	heapify(a, i, size - 1);		// ((N-1)/2)*logN ???
}

 

 

물론 아주아주 틀린 말은 아니다. 어디까지나 상한선(최악의 경우)이기 때문에 맞는 대답일 수도 있다.

 

하지만, 실제로는 좀 복잡하다. 일단 결론부터 말하면 max heap을 만드는 과정은 O(N)이다.

한 번 좀 더 정밀하게, 타이트하게 시간복잡도를 구해보자.

 

 

 

예를 들어 다음과 같은 트리가 있다고 가정해보자.

 

 

 

이제 heapify를 통한 max heap 빌드 과정에서 비교 횟수를 구해야되지 않겠는가?

 

위 트리에서 리프노드(l=8부분)을 h(높이)가 0이라고 할 때 다음과 같이 공식이 나온다.

 

 

 

자, 그럼 각 레벨 별 노드 개수는 알겠다. 그럼 비교 교환 횟수가 어떻게 되는지를 봐야되지 않겠는가.

 

먼저 가장 이해하기 쉬운 단말(리프:leaf) 노드는 heapify를 하지 않는다. 조금 이해하기 쉽게 말하자면 자식노드가 없는 노드들은 heapify 를 호출하지 않는다. 즉, 최하단에 위치한 노드들은 서브트리가 없기 때문에 비교하지도 않고, 교환 되지도 않는다.

 

그러면 l=4일 때를 봐보자.

 

각 노드 하나당 두 개의 자식을 갖고있고 그런 노드가 총 4개가 있다.

그렇다면, 최대 교환 할 수 있는 횟수 = 트리의 높이였으므로 각 노드 별 교환 횟수를 구할 수 있다.

 

트리의 높이는 어떻게 구한다고 했던가. 

 

이 공식 아니였는가? 즉, 부모노드 1개, 자식노드 2개로 총 N=3일 때 하나의 서브트리에 대한 높이는 1이고, 그러한 노드가 총 4개가 있다.

즉, 아래와 같다.

 

 

 

그럼 그 다음 l=2일 때는 어떤가?

 

 

 

이렇게 채우면 다음과 같이 된다.

 

 

 

 

 

그렇게 각 구한 수식은

h에 대해 힙으로 만드는데 드는 총 비용은 다음과 같다. 

위 뜻은 결국 h높이에 대해서 각 가질 수 있는 부분트리의 개수와 h높이에서 heapify에 걸리는 시간 O(h)가 걸린 다는 것이다.

 

결과적으로 전체 배열에 대해 드는 총 비용은 힙의 높이만큼 비용이 발생하기 때문에 다음과 같이 나타낼 수 있다.

 

 

 

 

이렇게 배열을 max heap으로 만드는 과정은 O(N)의 시간 복잡도를 갖는다.

 

 

 

 

 

그러면 다음으로 구할 것은 무엇인가.

삭제하면서 힙을 유지해야 하는 것이다.

 

 

이 부분은 그리 어렵지 않다.

 

힙 원소를 맨 뒤로 보낸 뒤 나머지 원소들에 대해 힙을 재구성 해야 한다.

 

 

 

우리가 정렬 하는 과정에서 이런 과정이 있었다.

 

보면 맨 뒤의 원소로 root원소를 보내고 그 대신 그 자리에 있던 원소를 가져온다.

그리고나서 힙을 재구성하는데, 3 원소가 트리의 높이(h=2)까지 비교 및 교환을 한다. 이 말은 무엇이냐. 어떤 원소를 삭제하고 힙을 재구성 하는 과정은 최악의 경우 트리의 높이만큼 비용이 발생한다는 것이다.

 

즉, 단일 수행에서는 최악의 경우 트리의 높이만큼 발생한다. 

 

위 log(N) 단일 수행을 N개의 원소만큼 반복하기 때문에 최종적으로 삭제(정렬) 과정은 다음과 같은 시간 복잡도를 갖는다.

 

 

 

그럼 처음에 구했던 최대 힙을 만드는 과정과 삭제 과정을 합쳐보자. 그럼 다음과 같이 될 것이다.

 

 

즉, 정리하면 힙 정렬은 O(NlogN)의 시간복잡도를 갖는다고 할 수 있다.

 

 

 

 

 

 

 

 

 




 

  • 정리




 

 

힙 정렬의 경우 보통 퀵 정렬과 많이 비교되는데, 힙 정렬 자체가 어떤 상황에서도 n2 의 시간이 나오지는 않기 때문에 재귀가 아닌 반복문으로 충분히 최적화 하여 구현한 경우 좋은 정렬 알고리즘에 속한다. (quick sort는 매우 빠르지만 특정 조건하에서는 매우 느리다.)

 

 

각 정렬 알고리즘 별 시간 복잡도와 평균 정렬 속도는 다음과 같다.

 

 

 

충분히 heap정렬 또한 빠른 것을 볼 수 있다.

 

테스트는 필자가 깃허브에 올린 코드를 활용하면 된다.

 

 

 

 

 

이번 힙 정렬의 경우 힙 자료구조의 연장선이라서 힙 구조를 파악하고 있지 않다면 꽤 어려웠을 것이다.

혹여 부족한 부분이 있거나 궁금한 점, 모르거나 이해가 가지 않는 부분이 있다면 언제든 댓글 달아주시면 감사하겠다.

 

 

그 외에 필자가 여러 타입들에 대해 구현 한 정렬 알고리즘 소스 코드들을 자세히 보고싶다면 아래 깃허브 repo에 업로드되어있으니 이를 참고하시길 바란다.

 

 

https://github.com/kdgyun/Sorting_Algorithm.git

 

kdgyun/Sorting_Algorithm

Contribute to kdgyun/Sorting_Algorithm development by creating an account on GitHub.

github.com



 

 

 

 



저작자표시 비영리 변경금지

'알고리즘 > Java' 카테고리의 다른 글

자바 [JAVA] - 퀵 정렬 (Quick Sort)  (29) 2021.05.19
자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort)  (24) 2021.03.31
자바 [JAVA] - 셸 정렬 (Shell Sort)  (18) 2021.02.18
자바 [JAVA] - 거품 정렬 (Bubble Sort)  (2) 2021.01.18
자바 [JAVA] - 삽입 정렬 (Insertion Sort)  (8) 2020.11.30

티스토리툴바