Arrays.sort

---

• 3장에서 이진검색에 사용했던 binarySearch 메서드는 java.util.Arrays 클래스의 클래스 메서드로 제공한다.
• 이 클래스는 배열을 정렬하는 클래스 메서드 sort도 제공한다.
• sort 메서드는 퀵 정렬 알고리즘을 개선한 것으로 안정적이지 않다.

자연 정렬이 필요한 배열

• 자연정렬 : 컴퓨터에게는 문자열의 대소 비교를 하면 "a1" -> "a10" -> "a2"으로 정렬을 마친다. 하지만 사람에게는 "a1" -> "a2" -> "a10"의 방식이 자연스러우며, 이 정렬을 자연 정렬이라고 한다.

static void sort(Object[] a)
static void sort(Object[] a, int fromIndex, int toIndex)

• 요소의 대소 관계를 비교하여 정렬

자연 정렬이 필요하지 않은 배열

static <T> void sort(T[] a, Comparator<? super T> c)
static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c)

• 요소의 대소 관계를 비교할 때 comparator c를 사용하여 정렬

힙 정렬

---

힙

• 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전이진트리이다.
  • 완전이란 부모는 자식을 왼쪽부터 추가하는 모양을 유지하는 것이다.
  • 이진이란 부모가 가질 수 있는 자식의 개수는 최대 2개이다.
    
• 부모와 자식의 인덱스 사이에 다음과 같은 관계가 성립한다.
  1. 부모는 a[(i-1) / 2]
  2. 왼쪽 자식은 a[i * 2 + 1]
  3. 오른쪽 자식은 a[i * 2 + 2]

힙 정렬

• 힙을 사용하여 정렬하는 알고리즘이다.
• 선택 정렬을 응용한 알고리즘으로, 시간 복잡도는 O(n log n)이다.
• 먼저, 최대 힙에서 오름차순으로 정렬한다는 것을 전제로 한다.
• 과정
  1. 힙의 루트(정렬 안된 요소 중 제일 큰 수)를 힙의 마지막 요소와 바꾼다.
     1.1) 이때, 힙의 루트는 정렬된다.
  2. 힙의 마지막 요소가 루트에 왔기 때문에 힙이 아니다. 다시 힙으로 만들어준다.
  3. 이를 총 n - 1회 실행한다.

코드

// a[left] ~ a[right]를 힙으로 만들기
static void downHeap(int[] a, int left, int right) {
  int temp = a[left]; // 루트
  int child; // 큰 값을 가진 노드
  int parent; // 부모
  
  // parent < (right + 1) / 2의 의미는 parent < (i - 1) / 2 + 1이다. 
  // 그 이후의 값은 부모 요소가 아니기 때문이다.
  for (parent = left; parent < (right + 1) / 2; parent = child) {
    int cl = parent * 2 + 1; // 왼쪽 자식
    int cl + 1; // 오른쪽 자식
    child = (cr <= right && a[cr] > a[cl]) ? cr : cl; // 큰 값을 가진 노드를 자식에 대입
    if (temp >= a[child])
      break;
    a[parent] = a[child];
  }
  a[parent] = temp;
}

// 힙 정렬
static void heapSort(int[] a, int n) {
  // a를 힙으로 만들기
  // downHeap의 두 번째 인자는 부모이기 때문에 배열 a의 전체 요소가 입력될 필요가 없다.
  // 자식이 있는 부모요소인지 판단하는 것은 downHeap에 있다.
  for (int i = (n - 1) / 2; i >= 0; i--)
    downHeap(a, i, n - 1);
    
  for (int i = n - 1; i > 0; i--) {
    swap(a, 0, i); // 가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소(힙의 마지막 요소)와 교환
    downHeap(a, 0, i - 1); // 정렬된 요소를 제외하고 다시 힙으로 만들어주기
  }
}