Java Heap 정렬

 

#0. 힙 정렬을 위한 개념 준비 ────────
자바(Java)를 통해서 빠르고 훌륭한 힙정렬(Heap sort)에 대해서 정리 해 보겠습니다.
예전 공부를 할 때는 의사코드(pseudo code)로만 보고 "아~ 저런 개념이구나~" 하고 넘어갔었는데, 실제 구현하려 해 보니 어렵고 시간이 꽤 걸렸던 것 같습니다.
알고리즘은 역시 실제 타이핑을 해 보아야 하는 것을 다시한번 깨달았습니다.

힙정렬에서의 데이터 정렬을 위한 구조는 배열을 이진트리(binary tree)형태로 구분하는 것 입니다.
이진트리는 배열의 관계를 부모 - 자식간의 형태로 데이터를 정렬하는 것을 의미 합니다.
부모는 0~2개의 자식을 가질 수 있으며 2개 이후의 자식은 다음 세대의 부모가 됩니다.
아래와 같이 숫자형태의 배열이 존재합니다.

 

int number[] = {10, 15, 6, 23, 4};

 

맨 처음 보이는 숫자 10은 가장 최상위의 부모가 되며, 다음 숫자인 15는 최 상의 부모의 왼쪽, 6은 오른쪽 자식으로 표현 합니다.
다음 숫자인 23은 15를 부모로 가지며 15의 왼쪽에, 마지막 숫자 4는 15의 오른쪽에 위치하게 됩니다.
이를 그림으로 표현하면 아래와 같습니다.

왼쪽부터 채워집니다.

 

힙 구조에서는 오름 또는 내림차순으로 데이터를 정렬 할 수 있습니다.
부모, 왼쪽자식, 오른쪽 자식들을 비교해서 정렬 기준을 바탕으로 위치를 교환하여 정렬을 합니다.

서로 비교 후 교체합니다.

 

이러한 방법을 반복하여 데이터를 정렬하는 방법이 힙 정렬 입니다.
그러면 이제 정렬방법을 위한 선행조건을 정리 해 보겠습니다.

 

#1. 부모의 왼쪽, 오른쪽 자식 인덱스 구하기 ────────
그러면 부모가 자식의 인덱스를 알기 위해서는 어떠한 방법이 존재하는 것 인지 알아보았습니다.

각 데이터의 숫자는 인덱스(순서) 입니다.

 

데이터 10은 순서가 1번 입니다.
데이터 10의 왼쪽 자식은 2번인 15이며, 오른쪽 자식은 3번인 6 입니다.
이때 유추할 수 있는 공식은,

n번 * 2 = 왼쪽 자식의 번호
n번 * 2+1 = 오른쪽 자식의 번호

 

해당 공식이 맞는지 2번인 숫자 15를 위 유추한 공식을 토대로 순서를 집어넣어 보겠습니다.

2번 * 2 = 4번(숫자 23)
2번 * 2 + 1 = 5번(숫자 4)

 

위 공식이 성립하는 것을 볼 수 있습니다!
데이터를 몇개 넣어보아도 동일한 결과를 받을 수 있습니다.
이제 배열에서의 자신의 자식 값을 우리는 위 공식을 토대로 알아낼 수 있게 되었습니다.

 

 

#2. 자식이 없는 배열의 순서 구하기 ────────
위 데이터에서 반복문을 통해서 부모 - 자식간의 관계를 출력하여 보겠습니다.

int number[] = {10,15,6,23,4};

for(int i=0;i < number.length;i++){
	System.out.println(" ------ ");
	System.out.println("저는 본인 입니다 : "+number[i]);
	int left = i*2+1;
	int right = i*2+1+1;
	if(left <= number.length-1){  
		System.out.printf(" - 저는 %d의 왼쪽 자식인 %d 입니다\n",number[i],number[left]);	
	}
	if(right <= number.length-1){
		System.out.printf(" - 저는 %d의 오른쪽 자식인 %d 입니다\n",number[i],number[right]);	
	}
}

위 코드를 실행하면 정상적인 출력을 볼 수 있습니다.

잘 나옵니다!

코드상으로는 문제는 없으나 반복문이 처음부터 끝까지 동작 하였습니다. 
3번인 데이터 6과 4번인 23, 5번인 4는 자식이 없기 때문에 본인 값만 출력 되었습니다.
3번 ~ 5번까지는 자식이 없기 때문에 굳이 반복 할 필요가 없습니다. 왜냐하면 바꿀 대상이 없기 때문 입니다.

이미 3번 ~ 5번까지는 첫번째, 두번째 반복문에서 동작을 완료 하였기 때문 입니다.

그러므로 이를 수정하여 보겠습니다.

int number[] = {10,15,6,23,4};

for(int i=0;i < number.length/2;i++){   //2로 나누었습니다. 5를 2로 나누면 숫자 2 입니다.
	System.out.println(" ------ ");
	System.out.println("저는 본인 입니다 : "+number[i]);
	int left = i*2+1;
	int right = i*2+1+1;
	if(left <= number.length-1){  
		System.out.printf(" - 저는 %d의 왼쪽 자식인 %d 입니다\n",number[i],number[left]);	
	}
	if(right <= number.length-1){
		System.out.printf(" - 저는 %d의 오른쪽 자식인 %d 입니다\n",number[i],number[right]);	
	}
}

 

이를 실행하면 관계있는 영역의 데이터만 나오게 됩니다.

부모 - 자식간의 영역만 나옵니다.

 

2번의 반복문에 모든 데이터의 노드가 출력된 것을 볼 수 있습니다.

#0번에서 살펴본 개념에 의하면 부모, 왼쪽 및 오른쪽의 자식 값을 비교해서 기준값에 의해 자리를 바꾸어야 합니다.
그러므로 배열의 크기 만큼 반복문이 동작하는 것이 아니라, 부모 - 자식간의 관계만큼 동작 해야 합니다.

나누기 2가 답이군요!

 

위 사진처럼 배열의 절반 크기 만큼만 비교하면 부모 - 자식간의 관계 까지만 살펴보는 멋진 반복문이 완성되게 됩니다.

 

 

#3. 1차 내용 정리 ────────
 1) 힙정렬을 위해서는 데이터는 2진트리 형태가 되어야 합니다.
 2) 이진트리는 본인, 왼쪽 및 오른쪽 자식 구조로 되어 있습니다.
 3) 이진트리에서 본인 이외의 자식을 구할 때는 아래의 규칙이 존재 합니다.
   - n은 본인의 순서
   - 왼쪽 순서 = 2 * n
   - 오른쪽 순서 = 2 * n + 1
 4) 본인과 비교할 왼쪽, 오른쪽 자식을 탐색하는 반복문은 배열의 길이만큼 동작하는 것이 아니라 배열의 절반만큼 동작 합니다.
 5) 배열의 절반 크기 만큼 반복문을 실행 하면 부모 - 자식 간의 관계를 전부 확인 할 수 있습니다.

 

 

#4. 힙 정렬을 위한 반복문의 동작 방향 ────────
정렬을 위해서는 가장 먼저 #2번에서 살펴본 "배열의 절만 크기만큼 반복문 동작" 방법을 사용하여야 합니다.
그리고 #1에서 나온 왼쪽, 오른쪽 자식을 토대로 왼쪽, 오른쪽 값을 가져오게 합니다.
그리고 비교한 뒤에 정렬 기준에 따라 교체를 실시 합니다.
여기서는 내림차순으로 정렬하여 보겠습니다.
이를 코드로 나타 내면,

int number[] = {10,15,6,23,4};

for(int i=0;i < number.length/2;i++){   //2로 나누었습니다. 5를 2로 나누면 숫자 2 입니다.

	int me = number[i];
	int left = number[i*2+1];
	int right = number[i*2+1+1];
	if(left < right){  //오른쪽이 왼쪽보다 크면 바꾸어 줍니다.
		int tmp = left;
		left = right;
		right = tmp;
	}
	if(me < left){  //부모보다 왼쪽이  크면 바꾸어줍니다.
		int tmp = me;
		me = left;
		left = tmp;
	}
	
	//교체하여 줍니다.
	number[i] = me;
	number[i*2+1] = left;
	number[i*2+1+1] = right;
		
}
System.out.println(Arrays.toString(number));

 

뭔가 이상하네요..

 

개념대로 하였는데 가장 큰 숫자인 23이 두번째에 있는 것을 알 수 있습니다.
이러한 이유는 위에서 아래로 반복문이 동작하다 보니 한번 비교가 되지 않는 구간이 존재하는 현상 때문 입니다.
그러므로 위에서 아래가 아니라 아래에서 위로 반복문을 동작하게 해야 합니다.

int number2[] = {10,15,6,23,4};

for(int i=number2.length/2-1;i >= 0 ;i--){   //2로 나누었습니다. 5를 2로 나누면 숫자 2 입니다.
	int me = number2[i];
	int left = number2[i*2+1]; 
	int right = number2[i*2+1+1];
	if(left < right){  //오른쪽이 왼쪽보다 크면 바꾸어 줍니다.
		int tmp = left;
		left = right;
		right = tmp;
	}
	if(me < left){  //부모보다 왼쪽이  크면 바꾸어줍니다.
		int tmp = me;
		me = left;
		left = tmp;
	}
	number2[i] = me;
	number2[i*2+1] = left;
	number2[i*2+1+1] = right;
}
System.out.println("위에서 아래로 입니다 : "+Arrays.toString(number2));	

 

일단 큰수 23은 잘 있습니다.

사진처럼 가장 큰 숫자인 23이 출력된 것을 볼 수 있습니다.
그런데 위코드에는 조금 문제가 존재합니다.
자식이 0개 이거나 2개인 경우에는 문제가 없으나 홀수개인 경우에 오른쪽 자식을 찾게되면 오류가 발생하게 됩니다.
그러므로 조건문을 하나 추가하여 주도록 합니다.

int number2[] = {10,15,6,23,4};

for(int i=number2.length/2-1;i >= 0 ;i--){   //2로 나누었습니다. 5를 2로 나누면 숫자 2 입니다.
	int me = number2[i];
	int left = number2[i*2+1]; 
	
	if(i*2+1+1 < number2.length){   //오른쪽 값이 존재하는 경우만 바꿉니다.
		int right = number2[i*2+1+1];
		if(left < right){  //오른쪽이 왼쪽보다 크면 바꾸어 줍니다.
			int tmp = left;
			left = right;
			right = tmp;
		}	
		number2[i*2+1+1] = right;
	}

	if(me < left){  //부모보다 왼쪽이  크면 바꾸어줍니다.
		int tmp = me;
		me = left;
		left = tmp;
	}
	number2[i] = me;
	number2[i*2+1] = left;
}
System.out.println("위에서 아래로 입니다 : "+Arrays.toString(number2));	

 

#5. 정렬이 완료된 값은 제외하고 다시 정렬하기 ────────
가장 큰 값인 23은 정렬이 되었습니다.
그런데 문제는 15라는 값은 아직 정렬되지 않았다는 점 입니다.
이를 위해서 생각 해 볼 것은 가장 큰 값은 빼고 그 다음 값부터 위 정의된 패턴을 동작하게 하는 것 입니다.
정렬된 값을 빼고, 위부터 줄여나가는 것은 배열의 크기 만큼을 줄이면 될 것 입니다.

for(int cursor = number2.length ; cursor > 0 ; cursor--){  //0부터 증가하여 상~ 하단을 표기합니다.

    if(cursor != number2.length){  //교체를 해 줍니다(정렬된 값을 뒤로 보냅니다)
        int tmp = number2[0];
        number2[0] = number2[cursor];
        number2[cursor] = tmp;
    }	
	
    for(int i=cursor/2-1;i >= 0 ;i--){  //커서 사이즈가 줄어드므로 점검이 완료된 대상은 제외가 됩니다.   
        int left = i*2+1;
        int right = i*2+1+1;
        if(right < cursor){  //오른쪽 오버 방지(이미 끝난 마지막 값을 참조하는 경우를 방지합니다)
            if(number2[left] < number2[right]){
                int tmp = number2[left];
                number2[left] = number2[right];
                number2[right] = tmp;
            }					
        }
        if(number2[i] < number2[left]){
            int tmp = number2[i];
            number2[i] = number2[left];
            number2[left] = tmp;
        }
    }			
}

 

이제 실행하여보면 데이터가 정렬되는 것을 볼 수 있습니다.

됬다!

 

#5번 내용이 사실 가장 복잡하고 어렵습니다.

저도 여러번 반복하고 살펴보았던 부분 입니다.

구글링을 하면 재귀호출 방법, 멋지게 메소드로 분리한 방법등을 통해서 구현해 놓은 예제가 많이 있습니다!

여기까지 힙정렬에 대한 내용 정리 였습니다.

내용이 정리 위주의 목적이다보니 빈약하고 틀린부분이 있을 수 있습니다.. ;ㅁ;

부족한 부분이나 틀린부분은 언제든 연락주세요!