# 이진 탐색

---

## 이진 탐색(Binary Search)

이진 탐색은 **정렬된 배열**에서 데이터를 탐색하는 알고리즘 
시간 복잡도: O(logN) 
배열의 중앙에 있는 임의값을 찾은 뒤, 탐색할 수와 비교를 한다. 
만약 임의의 중간값보다 탐색하고자 하는 수가 크면 배열의 우측을 대상으로 다시 탐색하고, 중간값보다 탐색하고자 하는 수가 작으면 배열의 좌측을 대상으로 탐색한다. 
배열이 정렬되어 있다는 것을 활용해서 탐색할 범위를 매번 반씩 줄여나갈 수 있다. 

### 장단점

- 장점
 - 탐색이 반복될 때마다 목표값을 찾을 확률은 두배가 되므로 속도가 빠름
- 단점
 - 정렬된 리스트에서만 사용할 수 있음

### 이진 탐색(Binary Search) js 코드

```js
const binarySearch = (array, number) => {
	let start = 0,
		end = array.length - 1;

	while (start <= end) {
		let mid = Math.floor((start + end) / 2);

		if (array[mid] === number) return mid;

		if (array[mid] < number) {
			start = mid + 1;
		} else {
			end = mid - 1;
		}
	}
	return -1;
};
```

## ref

- [geeksforgeeks - Binary Search In JavaScript](https://www.geeksforgeeks.org/binary-search-in-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)

이진 탐색(Binary Search)

# 선형 탐색

---

## 선형 탐색(Linear Search)

배열에서 데이터를 탐색하는 알고리즘. 
단방향으로 탐색을 시작하여 원하는 데이터를 찾아내는 매우 단순한 알고리즘 

배열 [1, 2, 3, 4, 5]에서 4를 탐색한다고 가정하자. 

**첫번째 탐색** 
![linear_search_first_index](linear_search_first_index.png)
index가 0인 요소와 찾고자 하는 수(4)를 비교한다. 
일치하지 않기 때문에 넘어간다. 

**두번째 탐색** 
![linear_search_second_index](linear_search_second_index.png)
index가 1인 요소와 찾고자 하는 수(4)를 비교한다. 
일치하지 않기 때문에 넘어간다. 

**세번째 탐색** 
![linear_search_third_index](linear_search_third_index.png)
index가 2인 요소와 찾고자 하는 수(4)를 비교한다. 
일치하지 않기 때문에 넘어간다. 

**네번째 탐색** 
![linear_search_fourth_index](linear_search_fourth_index.png)
index가 3인 요소와 찾고자 하는 수(4)를 비교한다. 
일치하기 때문에 4의 위치 3을 반환한다. 
만약 끝까지 탐색했는데 원하는 수가 존재하지 않는다면 -1을 반환한다.

### 장단점

- 장점
 - 구현이 아주 쉽다.
 - 정렬되지 않은 리스트에도 사용이 가능하다.
- 단점
 - 모든 데이터를 탐색해야 하기에 데이터가 많아질수록 효율이 떨어진다.

### 선형 탐색(Linear Search) js 코드

```js
const linearSearch = (array, number) => {
 for (let i = 0; i < array.length; i++) {
 if (array[i] === number) {
 // return index value;
 return i;
 }
 }
 return -1;
};

const betterLinearSerach = (array, number) => {
 let length = array.length;
 let left = 0;
 let right = length - 1;

 let position = -1;

 while (left <= right) {
 if (array[left] === number) {
 position = left;
 // return index value;
 return position;
 }

 if (array[right] === number) {
 position = right;
 // return index value;
 return position;
 }
 left++;
 right--;
 }
};
```

## ref

- [novDev - [알고리즘] 선형 탐색 알고리즘(Linear Search Algorithm)](https://novlog.tistory.com/25)
- [Linear Search Algorithm | JavaScript](https://dev.to/mdqayyumshareef/linear-search-algorithm-javascript-mb4)
- [알고리즘 도감](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)

선형 탐색(Linear Search)

# 퀵 정렬

---

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