힙 정렬 (Heap Sort)
힙 정렬이란? 완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다. *힙 이란? - 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리 형태인 완전 이진 트리의 일종으로 최솟값이나 최댓값을 빠르게 찾아내도록 만들어진 자료구조 - 부모의 키 값이 자식의 키 값보다 항상 크거나(작거나) 같은 이진트리 시간 복잡도 O(NlogN) 진행 과정 1. 최대힙을 구성한다. 2. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄인다. 3. 힙의 사이즈가 1보다 크면 위 과정을 반복한다. 코드 public class HeapSort { public static void main(String[] args) { int[] arr = {5, 8, 4, 7, 10, 9, 2, 1, 6, 3..
병합 정렬 (Merge Sort)
병합 정렬이란? 병합 정렬(Merge Sort)은 요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식의 정렬 알고리즘이다. 시간 복잡도 O(nlogn) *성능은 좋지만 메모리 자원 측면에선 비효율적 진행 과정 1. 초기 상태의 리스트 하나를 두 개의 리스트가 되도록 분할해 나가면서, 최종적으로 길이가 1이 될때까지 분할한다. 2. 분할된 리스트끼리 비교를 하여 하나의 리스트에 병합(merge)하며 정렬한다. 코드 private void solve() { int[] array = { 230, 10, 60, 550, 40, 220, 20 }; mergeSort(array, 0, array.length - 1); for (int v : array) { System.out.println(v); } } publ..
