# 선택 정렬

---

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