# 선택 정렬

---

## 선택 정렬(selection sort)

수열을 정렬하는 알고리즘 중 하나. 제자리 정렬 알고리즘. 
시간 복잡도: O(n2)

다음과 같이 정렬되지 않은 배열이 있다고 가정한다. 프로그램은 이 배열을 오름차순으로 정렬해야한다. 
[ 9, 6, 7, 3, 5 ] 
알고리즘은 선형 탐색해서 최소값을 찾는다. 최소값을 찾은 뒤 열의 왼쪽 끝에 있는 값과 교환한뒤 정렬을 완료한다. 
[ 3, 6, 7, 9, 5 ] - 한번 회전 
참고로 최소값이 이미 왼쪽 끝에 있다면 아무런 작업도 하지 않는다.

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

### 장단점

- 장점
 - 자료 이동 횟수가 미리 정의된다.
- 단점
 - 안정성을 만족하지 않는다. 즉, 같은 값의 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

> 버블정렬과 비슷하지만 가장 큰 값이 "버블링"되지 않고 가장 작은 값만 선택해 정렬한다.

### 선택정렬(selection sort) js 코드

```javascript
const selectionSort = (arr) => {
 for (let i = 0; i < arr.length; i++) {
 let lowest = arr[i];
 let lowestIndex = i;
 for (let j = i; j < arr.length; j++) {
 if (arr[j] < lowest) {
 lowest = arr[j];
 lowestIndex = j;
 }
 }
 let temp = arr[i];
 arr[i] = arr[lowestIndex];
 arr[lowestIndex] = temp;
 }
 return arr;
};
```

## ref

- [위키백과 - 선택 정렬](https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC)
- [Selection Sort with JavaScript](https://javascript.plainenglish.io/selection-sort-939850e195c8)
- [gmlwjd9405- [알고리즘] 선택 정렬(selection sort) 이란](https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-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)

선택 정렬(selection sort)

# 버블 정렬

---

## 버블 정렬(bubble sort)

수열을 정렬하는 알고리즘 중 하나. 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘. 
시간 복잡도: O(n2)

다음과 같이 정렬되지 않은 배열이 있다고 가정한다. 프로그램은 이 배열을 오름차순으로 정렬해야한다. 
[ 7, 2, 0, 1, 5, 6, 4 ] 
알고리즘은 배열의 첫 두글자(7, 2)를 비교한다. 7 > 2 로 정렬되지 않았으니 두 수를 바꾼다. 
[ 2, 7, 0, 1, 5, 6, 4 ] 
7은 다시 0과 자리를 바꾸고 이를 배열 끝까지 작업하면 다음과 같이 된다. 
[ 2, 0, 1, 5, 6, 4, 7 ] - 한번 회전

가장 큰 수인 7이 정렬되었다. 이를 여러번 반복한다면 다음과 같이 진행된다. 
[ 0, 1, 2, 5, 4, 6, 7 ] - 두번 회전 
[ 0, 1, 2, 4, 5, 6, 7 ] - 세번 회전 
[ 0, 1, 2, 4, 5, 6, 7 ] - 네번 회전 
세번째와 네번째의 차이가 없으므로 모두 정렬된 것으로 정의한다.

### 장단점

- 장점
 - 구현이 매우 간단하다.
- 단점
 - 순서에 맞지 않은 요소를 인접한 요소와 교환한다.
 - 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.

> 일반적으로 자료의 교환작업이 자료의 이동작업보다 더 복잡하기 때문에 버블정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

### 버블 정렬(bubble sort) js 코드

```javascript
// 기본 버블 정렬 함수
const bubbleSort = (arr) => {
 for (let i = 0; i < arr.length; i++) {
 for (let j = 0; j < arr.length - i - 1; j++) {
 if (arr[j] > arr[j + 1]) {
 let temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 }
 }
 }
 return arr;
};

// 최적화된 버블 정렬 함수
const optimizedBubbleSort = (arr) => {
 let i, j;
 let len = arr.length;

 let isSwapped = false;

 for (i = 0; i < len; i++) {
 isSwapped = false;

 for (j = 0; j < len; j++) {
 if (arr[j] > arr[j + 1]) {
 let temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 isSwapped = true;
 }
 }

 if (!isSwapped) {
 break;
 }
 }
 return arr;
};
```

## ref

- [위키백과 - 버블 정렬](https://ko.wikipedia.org/wiki/%EB%B2%84%EB%B8%94_%EC%A0%95%EB%A0%AC)
- [geeksforgeeks - Bubble Sort algorithm using Javascript](https://www.geeksforgeeks.org/bubble-sort-algorithms-by-using-javascript/)
- [gmlwjd9405 - [알고리즘] 버블 정렬(bubble sort) 이란](https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-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)

버블 정렬(bubble sort)

# 시간 복잡도

---

## 시간 복잡도란?

프로그램을 작성할 때 입력의 크기에 따라서 프로그램이 계산하는 횟수가 크게 달라진다. 시간복잡도는 알고리즘을 실행하는데 필요한 시간 척도이며, 알고리즘 효율성을 판단하는 중요 척도 중 하나다. 프로그램 수행에 걸리는 절대적인 시간이 아닌, 알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 상대적 지표로 나타낸 것이다.

## 시간 복잡도의 특징

### 1. 시간복잡도의 산정기준은 연산수이다.

소요되는 기본 연산 수에 의거한다. 주로 알고리즘이 사용한 기본 연산의 수에 따르며 기본 연산이란 데이터의 비교, 덧셈, 곰셈, 나눗셈 등이 있다.

### 2. 시간복잡도는 함수적으로 표현한다.

입력 크기에 대한 함수적 관계를 나타낸다. 기본 연산 수가 입력 크기와 어떤 함수 관계가 있는지를 이를 함수식처럼 표현한다.

### 3. 시간복잡도는 점근적 분석방법을 쓴다.

입력 크기가 무한히 증가할 때, 알고리즘이 어떻게 작동하는가에 대해서 따질 때, "점근적 분석 방법"을 사용한다. 여기서 점근적 분석방법이란 상계/상한(최악, 빅오), 하계/하한(최선, 빅 오메가), 평균(빅 세타)을 말한다. 평균적인 경우를 가장 많이 사용할 것 같지만, 알고리즘이 복잡해 질수록 평균적인 경우는 구하기가 너무 어려워지기 때문에 **최악의 경우**로 알고리즘의 성능을 파악합니다.

## 시간 복잡도의 분석 종류

### 1. big-O(빅 오 표기법)

최악의 경우를 나타낸다.(상한 접근)

### 2. big-Omega(빅 오메가 표기법)

최적의 경우를 나타낸다.(하한 접근)

### 3. big-Theta(빅 세타 표기법)

평균을 나타낸다. (big-O 와 big-Omega 값의 평균값)

## 시간 복잡도의 주요 표기

### 1. O(1) - 상수 시간(Constant time)

입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간 복잡도는 O(1)이다. 다음의 알고리즘은 n에 상관 없이 한번만 연산을 수행한다.

```js
function constantTime(n) {
 console.log(n);
}
```

때문에 다음과 같은 시간복잡도를 가진다.

> <center>T(n) = O(1)</center>

### 2. O(logN) - 로그 시간

입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 O(logN)이다. 다음의 알고리즘은 i값이 반복될 때마다 2배씩 증가한다.

```js
for (let i = 1; i <= n; i *= 2) {
 console.log(i);
}
```

위의 알고리즘을 k번 반복했을 때, 2k = N이 되고 반복문이 종료된다. 양쪽에 로그를 취하면 다음과 같다.

> <center>log2(2k) = log2N</center>
> <center>k = log2N</center>

k는 수행 횟수이기 때문에 다음과 같은 시간복잡도를 가진다.

> <center>T(n) = logN</center>

### 3. O(n) - 선형 시간

입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간복잡도는 O(n) 이다. 다음의 알고리즘은 n만큼 반복문을 수행한다.

```js
for (let i = 1; i < n; i++) {
 console.log(i);
}
```

n의 값에 비례해서 연산수가 선형적으로 증가하기 때문에 다음과 같은 시간복잡도를 가진다.

> <center>T(n) = O(n)</center>

### 4. O(n2) - 2차 시간

입력 크기(n)가 커질 때 연산 횟수가 n2에 비례해서 증가하면 시간복잡도는 O(2)이다.

```js
for (let i = 0; i < n; i++) {
 for (let j = 0; j < n + 1; j++) {
 console.log(i, j);
 }
}
```

위 알고리즘은 for문이 중첩되어 있기 때문에 n2에 비례해서 연산수가 증가한다. 시간복잡도는 다음과 같다.

> <center>T(n) = O(n2)</center>

### 5. O(2n) - 지수 시간

입력 크기(n)가 커질 때 연산수가 2n에 비례해서 증가하면 시간 복잡도는 O(2n)이다. 다음의 알고리즘은 피보나치 수를 구하는 알고리즘이다.

```js
function fibonacci(n) {
 if (n <= 1) {
 return n;
 }
 return fibonacci(n - 1) + fibonacci(n - 2);
}
```

한번 함수를 호출할 때 마다 두번씩 재귀로 함수를 호출하기 때문에 2n에 비례해서 연산수가 증가한다. 시간복잡도는 다음과 같다.

> <center>T(n) = O(2n)</center>

## 시간복잡도 성능 지표

![big-o image](big-o.png)

<center>O(1) < O(logN) < O(n) < O(nlogn) < O(n2) < O(2n) < O(n!)</center>

오른쪽으로 갈수록 시간복잡도가 큰 알고리즘이다. n의 값이 작을 때는 알고리즘 사이에 큰 차이는 없지만 n의 값이 커지면 커질수록 복잡한 알고리즘은 수행시간이 급격히 떨어진다.

## ref

- [Big-O Cheat Sheet](https://www.bigocheatsheet.com/)
- [yoongrammer 블로그](https://yoongrammer.tistory.com/79)
- [bangu4 블로그](https://bangu4.tistory.com/202)