# 병합 정렬

---

## 병합 정렬(merge sort)

수열을 정렬하는 알고리즘 중 하나. 분할 정복 일고리즘의 하나. 
시간 복잡도: O(nlogn)

처음에는 수열을 반씩 분할한다.(분할, Divide) 
[ 6, 4, 3, 7, 5, 1, 2 ] 
![divide_array](divide_array.png)
분할을 완료한 뒤 다시 분할한 각 그룹을 병합해간다.(결합, Combine) 
병합할 때에는 병합 후의 그룹 내에서 숫자가 작은 순으로 나열되도록 한다.(정복, Conquer) 
여러 숫자를 포함하고 있는 그룹들을 서로 병합할 때는 선두의 숫자를 비교해서 작은 숫자를 이동한다. 
그룹 병합 작업은 모든 숫자가 하나의 그룹이 될 때까지 재귀적으로 반복한다. 
![conquer_and_combine](conquer_and_combine.png)

### 장단점

- 장점
 - 안정적인 데이터 정렬 방법
 - 데이터의 분포에 영향을 덜 받는다. 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다.
- 단점
 - 제자리 정렬(in-place sorting)이 아니다.
 - 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적인 낭비를 초래할 수 있다.

### 병합 정렬(merge sort) js 코드

```js
const merge = (left, right) => {
 // 정렬된 항목들을 담을 배열
 let sortedArr = [];

 while (left.length && right.length) {
 // 가장 작은 값을 sortedArr에 push
 if (left[0] < right[0]) {
 sortedArr.push(left.shift());
 } else {
 sortedArr.push(right.shift());
 }
 }
 return [...sortedArr, ...left, ...right];
};

const mergeSort = (arr) => {
 // return 조건문
 if (arr.length <= 1) return arr;

 let mid = Math.floor(arr.length / 2);

 // 재귀적으로 left와 right를 호출
 let left = mergeSort(arr.slice(0, mid));
 let right = mergeSort(arr.slice(mid));

 return merge(left, right);
};
```

## ref

- [gmlwjd9405- [알고리즘] 합병 정렬(merge sort) 이란](https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html)
- [Doable Danny - Merge Sort Javascript](https://www.doabledanny.com/merge-sort-javascript)
- [알고리즘 도감](https://apps.apple.com/kr/app/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8F%84%EA%B0%90/id1047532631)

병합 정렬(merge sort)

# 힙 정렬

---

## 힙 정렬(heap sort)

수열을 정렬하는 알고리즘 중 하나. 힙이라는 자료구조를 사용하는것이 특징. 
시간 복잡도: O(nlogn)

처음에는 힙에 모든 숫자를 저장한다. 힙은 내림차순으로 구축한다. 

[ 5, 2, 7, 3, 6, 1, 4 ] 
힙에 내림차순으로 구축하면 다음과 같은 모양이 된다.
![heap head](heap_head.png)

힙에 저장된 숫자를 하나씩 꺼낸다. 
내림차순 힙은 큰것부터 순서대로 데이터를 추출하는 성질이 있으므로 꺼낸 숫자를 역순으로 나열하면 정렬이 완료됩니다.
![heap sort](heap_sort.png)

### 장단점

- 장점
 - 시간 복잡도가 좋은 편(항상 nlogn을 보장)
 - 힙 정렬이 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때이다.
- 단점
 - 일반적으로 속도만 비교하자면 퀵정렬이 평균적으로 더 빠르다. 그래서 잘 사용하지 않는다.

### 힙 정렬(heap sort) js 코드

```javascript
const buildHeap = (arr) => {
 // build heap: 임의의 숫자들을 최대 힙으로 구성하는 연산과정

 // 중간 값의 index 구하기
 let i = Math.floor(arr.length / 2 - 1);

 // 전달된 모든 배열 요소에서 최대 힙 구축
 while (i >= 0) {
 heapify(arr, i, arr.length);
 i -= 1;
 }
};

const heapify = (heap, i, max) => {
 // heapify: 주어진 자료구조에서 힙 성질을 만족하도록 하는 연산
 let index;
 let leftChild;
 let rightChild;

 while (i < max) {
 index = i;

 // left child index 가져오기
 leftChild = 2 * i + 1;

 // right child index 가져오기
 rightChild = leftChild + 1;

 // left child가 last element가 아니거나, 값이 더 클 경우
 if (leftChild < max && heap[leftChild] > heap[index]) {
 index = leftChild;
 }

 // right child가 last element가 아니거나, 값이 더 클경우
 if (rightChild < max && heap[rightChild] > heap[index]) {
 index = rightChild;
 }

 // 위 조건 중 어느것도 해당하지 않을 경우 return
 if (index === i) {
 return;
 }

 // else swap
 swap(heap, i, index);

 // 스왑된 인덱스를 사용
 i = index;
 }
};

const swap = (arr, firstItemIndex, lastItemIndex) => {
 const temp = arr[firstItemIndex];

 // 배열의 첫번째 항목과 마지막 항목을 바꾼다.
 arr[firstItemIndex] = arr[lastItemIndex];
 arr[lastItemIndex] = temp;
};

const heapSort = (arr) => {
 // 최대 힙을 구성
 buildHeap(arr);

 // last element의 index를 가져옴
 lastElement = arr.length - 1;

 while (lastElement > 0) {
 swap(arr, 0, lastElement);
 heapify(arr, 0, lastElement);
 lastElement -= 1;
 }

 return arr;
};
```

## ref

- [ratsgo's blog - 힙정렬(Heap Sort)](https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/)
- [gmlwjd9405- [알고리즘] 힙 정렬(heap sort) 이란](https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html)
- [알고리즘 도감](https://apps.apple.com/kr/app/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8F%84%EA%B0%90/id1047532631)

힙 정렬(heap sort)

# 삽입 정렬

---

## 삽입 정렬(insertion sort)

수열을 정렬하는 알고리즘 중 하나. 손 안의 카드를 정렬하는 방식과 유사. 
시간 복잡도:

- Best: O(n)
- Worst: O(n2)

다음과 같이 정렬되지 않은 배열이 있다고 가정한다. 프로그램은 이 배열을 오름차순으로 정렬해야한다. 
[ 8, 5, 6, 2, 4 ] 
처음에는 왼쪽 끝의 숫자를 정렬이 끝났다고 가정한다. 
계속해서 아직 작업이 끝나지 않은 숫자들 중에서 가장 왼쪽에 있는 숫자를 꺼내서 왼쪽에 있는 작업이 끝난 숫자과 비교한다. 
왼쪽의 숫자가 크면 두개의 숫자 위치를 바꾼다. 
이 작업을 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도착할 때까지 반복한다. 
다음의 예에서는 8 > 5 이므로 위치를 교환한다. 
5가 왼쪽 끝에 도착했으므로 작업을 멈추고 완료한다. 
[ 5, 8, 6, 2, 4 ] - 한번 회전

동일한 작업을 모든 숫자가 정렬을 마칠 때까지 반복한다. 
[ 5, 6, 8, 2, 4 ] - 두번 회전 
[ 2, 5, 6, 8, 4 ] - 세번 회전 
[ 2, 4, 5, 6, 8 ] - 네번 회전 

### 장단점

- 장점
 - 안정적인 정렬방법
 - 레코드 수가 적을경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬방법보다 유리할 수 있다.
 - 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.
- 단점
 - 비교적 많은 레코드들의 이동을 포함한다.
 - 레코드 수가 많고 레코드 크기가 클 경우 적합하지 않다.

### 삽입정렬(insertion sort) js 코드

```javascript
const insertionSort = (arr) => {
 for (let i = 1; i < arr.length; i++) {
 let curValue = arr[i];
 let j;

 for (j = i - 1; j >= 0 && arr[j] > curValue; j--) {
 arr[j + 1] = arr[j];
 }
 arr[j + 1] = curValue;
 }
 return arr;
};
```

## ref

- [위키백과 - 삽입정렬](https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC)
- [Insertion Sort in Javascript](https://www.doabledanny.com/insertion-sort-in-javascript)
- [gmlwjd9405- [알고리즘] 삽입 정렬(insertion sort) 이란](https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html)
- [알고리즘 도감](https://apps.apple.com/kr/app/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8F%84%EA%B0%90/id1047532631)