힙정렬 코드

자료구조와 알고리즘 입문  - 자바편에 힙정렬이 나왔다. 하노이의 탑도 이해가 잘안갔고, 특히 재귀적 호출이 너무 복잡했다. 그래서 일부는 직접 그림판에 그림을 그려서 영상으로 찍어서 내가 하는말을 들어가면서 이해했는데, 글쎄,,, 힙정렬이 좀 이해가 잘안간다. 이해가 안가는건 일단 외우라고 했으니... 일단은 외워야 겠지... 이게 안좋은 방법인건 알고 있다. 근데 일단은 머릿속에 집어넣고 그 다음에 이해해야겠다.

package algorithm;

public class heap {
private void solve() {
	int[] array = {230,10,60,550,40,220,20};
	heapSort(array);
	
	for(int v:array) {
		System.out.println(v);
	}
}
public static void heapify(int array[], int n, int i) {
	int p = i;
	int l = i*2+1;
	int r = i*2+2;
	
	if(l<n && array[p] < array[l]) {
		p = l;
	}
	if (r<n && array[p]< array[r]) {
		p = r;
	}
	if(i != p) {
		swap(array,p,i);
		heapify(array,n,p);
	}
}
public static void heapSort(int[] array) {
	int n = array.length;
	for(int i = n/2-1;i>=0;i--) {
		heapify(array,n,i);
	}
	for(int i = n-1;i>0;i--) {
		swap(array,0,i);
		heapify(array,i,0);
	}
}

public static void swap(int[] array, int a, int b) {
	int temp = array[a];
	array[a] = array[b];
	array[b] = temp;
}
	public static void main(String[] args) {
		heap h = new heap();
		
		h.solve();
	}

}

 

교재의 앞 내용에서 퀵정렬... 단순 삽입,, 단순 선택... 하노이의 탑... 이진 ... 등등 재밌는 내용들이 많았다. 특히 재귀가 어려웠다. 재귀는 꼬아서 낼려고 작정하고 문제내면 끝도 없을 것 같다. 

 

 

m.blog.naver.com/PostView.nhn?blogId=writer0713&logNo=221143233353&proxyReferer=https:%2F%2Fwww.google.com%2F

[알고리즘] 힙 정렬

 

이 블로그에 힙정렬이 정리되어 있는데, 그나마 여태 본 코드들 중에서 가장 이해하기 쉬운 것 같다. 

 

xmfpes.github.io/algorithm-study/daily-algorithm-11/

알고리즘 스터디 - 11(Sort - 힙 정렬(Heap Sort)

 

여기도 괜찮게 설명되어 있다.