# 퀵 정렬

---

## 퀵 정렬(quick sort)

수열을 정렬하는 알고리즘 중 하나. 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행속도를 자랑하는 정렬 방법. 
시간 복잡도: Worst - O(n2) / Best - O(nlog₂n)

처음 작업 대상은 모든 숫자다. 
정렬 기준이 되는 숫자를 하나 선택한다. 이를 피봇(pivot)이라 한다. 
피봇은 보통 하나의 숫자를 랜덤으로 선택한 것이다. 
여기서는 편의상 가장 오른쪽에 있는 수를 피봇으로 선택한다. 
알기 쉽게 피봇에 마커를 표시한다. 
계속해서 가장 왼쪽 수에 왼쪽 마커, 오른쪽 수에 오른쪽 마커를 표시한다. 
![pivot_and_left_right_marker](pivot_and_left_right_marker.png)
퀵 정렬은 이 마커들을 사용해서 일련의 작업을 재귀적으로 반복하는 알고리즘이다. 

왼쪽 마커를 오른쪽으로 이동한다. 왼쪽 마커가 피봇 수 이상인 수에 도착하면 멈춘다. 
오른쪽 마커를 왼쪽으로 이동한다. 오른쪽 마커는 피봇보다 작은 숫자에 도달하면 멈춘다. 
![marker_move](marker_move.png)
좌우 마커가 멈춘 시점에 마커의 숫자를 교체한다. 
![number_change](number_change.png)
이와 같이 왼쪽 마커의 역할은 피봇 이상인 수를 발견하는 것이고, 오른쪽 마커의 역할은 피봇보다 작은 수를 발견하는 것이다. 

숫자를 바꾸므로 수열의 왼쪽에 피봇보다 작은 수, 오른쪽에 피봇 이상인 수를 모을 수 있다. 
교체한 후에는 다시 왼쪽 마커를 오른쪽으로 이동한다. 
![marker_break](marker_break.png)
마커들을 이동하는 중 오른쪽 마커가 왼쪽 마커와 만날 때도 동작을 멈춘다. 
좌우 마커가 정지했을 때 동일한 위치인 경우 해당 수롤 피봇수와 교체한다. 
![pivot_change](pivot_change.png)
죄우 마커가 있는 수(**6**)를 정렬 완료 상태로 둔다. 
이로써 첫 작업이 완료된다. 

둘로 나누어진 수열에 대해 앞서 했던 작업을 재귀적으로 반복한다. 
다음은 왼쪽에 있는 수열([3, 5, 4, 1, 2])을 작업 대상으로 한다. 
대상 수열의 수가 하나인 경우에는 정렬이 완료된다. 
**왼쪽 마커가 오른쪽 마커와 만나도 멈추지 않는다. 오른쪽 마커의 움직임과는 다르다.** 
이때에는 작업 대상 범위 내에서 피봇인 수가 가장 큰 수가 된다. 
다음은 오른쪽 마커를 이동하지만 왼쪽 마커에 추월당한 경우에는 움직이지 않고 종료한다. 
이후로는 동일한 작업을 모든 수가 정렬 완료 상태가 될 때까지 반복한다. 

### 장단점

- 장점
 - 속도가 빠르다.
 - 추가 메모리 공간을 필요로 하지 않는다.
- 단점
 - 정렬된 리스트에 대해서는 퀵정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
 - 때문에, 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.

### 퀵 정렬(quick sort) js 코드

```js
// stable한 Quick Sort
// 별도의 메모리 공간이 필요해 실제로는 잘 사용하지 않는 방법
const quickSort = (arr) => {
	if (arr.length < 2) {
		return arr;
	}
	const pivot = [arr[0]];
	const left = [];
	const right = [];

	for (let i = 1; i < arr.length; i++) {
		if (arr[i] < pivot) {
			left.push(arr[i]);
		} else if (arr[i] > pivot) {
			right.push(arr[i]);
		} else {
			pivot.push(arr[i]);
		}
	}
	return quickSort(left).concat(pivot, quickSort(right));
};

// in-place Quick Sort
// 가운데 요소를 pivot으로 설정하고 가장 왼쪽 요소와 가장 오른쪽 요소가 시작점
// unstable 하지만 메모리 공간이 절약할 수 있어서 대부분 사용하는 방법
const inPlaceQuickSort = (arr, left = 0, right = arr.length - 1) => {
	if (left >= right) {
		return;
	}
	const mid = Math.floor((left + right) / 2);
	const pivot = arr[mid];

	const divide = (arr, left, right, pivot) => {
		while (left <= right) {
			while (arr[left] < pivot) {
				left++;
			}

			while (arr[right] > pivot) {
				right--;
			}

			if (left <= right) {
				let swap = arr[left];
				arr[left] = arr[right];
				arr[right] = swap;
				left++;
				right--;
			}
		}
		return left;
	};

	const partition = divide(arr, left, right, pivot);

	inPlaceQuickSort(arr, left, partition - 1);
	inPlaceQuickSort(arr, partition, right);

	return arr;
};
```

## ref

- [gmlwjd9405- [알고리즘] 퀵 정렬(quick sort) 이란](https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html)
- [[JS/Sorting] 퀵 정렬, 자바스크립트로 구현하기(Quick Sort in JavaScript)](https://im-developer.tistory.com/135)
- [알고리즘 도감](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)

퀵 정렬(quick sort)

# 병합 정렬

---

## 병합 정렬(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)