# 알고리즘 - 선택정렬 : Selection Sort

선택 정렬(Selection Sort)은 가장 간단하고 직관적인 정렬 알고리즘 중 하나다.

보통 배열이나 리스트를 정렬하는 데에 사용됩니다.

## 언제 사용??

선택 정렬은 항상 동일한 시간 복잡도인 `O(n^2)`를 갖기 때문에, 효율적이라고 보기 어렵다.

선택 정렬의 시간 복잡도는 배열의 크기(n)에 따라서 제곱에 `비례`하므로 배열의 크기가 커질수록 성능이 급격하게 저하된다.


사실상 퀵정렬을 사용하는 것이 가장 효율적이다. 
퀵정렬의 시간복잡도는 평균적으로 `O(n log n)`이다.  

그리고 n이 커질수록 퀵정렬이 훨씬 빠르다.

iOS에서는 `sort()`함수를 통해 퀵정렬을 할수있다.


## 동작 원리
- 1. 주어진 배열에서 가장 작은 값을 찾는다.
- 2. 가장 작은 값과 배열의 첫 번째 요소를 교환한다.
- 3. 두 번째 요소부터 다시 가장 작은 값을 찾아 두 번째 요소와 교환한다.
- 4. 이와 같은 과정을 배열의 마지막 요소까지 반복한다.


## 세부설명
아래와 같은 값이 있다.
1, 10, 5, 8, 7, 6, 4, 3, 2, 9

- 1. 먼저 전체 숫자중 가장 작은 값을 찾는다 -> 1
- 2. 가장 작은 숫자 1을 배열의 첫번째 요소로 교환한다.

`1`, 10, 5, 8, 7, 6, 4, 3, 2, 9

- 1. 이제 첫번째는 제외하고, 나머지 숫자 중 가장 작은 값을 찾는다 -> 2
- 2. 가장 작은 숫자 2을 배열의 두번째 요소로 교환한다.

`1`, `2`, 5, 8, 7, 6, 4, 3, 10, 9

- 1. 이제 두번째도 제외하고, 나머지 숫자 중 가장 작은 값을 찾는다 -> 3
- 2. 가장 작은 숫자 3을 배열의 세번째 요소로 교환한다.

`1`, `2`, `3`, 8, 7, 6, 4, 5, 10, 9

> 0번부터 n번째까지 요소중 가장 작은 숫자를 찾는다.
> 가장 작은 숫자는 0번째와 자리를 바꾼다.
>> 이제 0번째는 가장 작은 숫자가 위치한다.

> 1번부터 n번째까지 요소중 가장 작은 숫자를 찾는다.
> 가장 작은 숫자는 1번째와 자리를 바꾼다.
>> 이제 1번째는 그다음 작은 숫자가 위치한다.



이걸 이제 코드로 만들어 볼꺼다. 

여기서 필요한 과정은 2가지다.

- 1. 어떻게 가장 작은 숫자를 찾을건지
- 2. 어떻게 n번째에 숫자를 저장할 건지

### 어떻게 가장 작은 숫자를 찾을 건지

- i를 0부터 n-1까지 증가시키면서 배열의 각 요소를 순회한다.
- i번째 요소를 기준으로 i 이후의 부분 배열에서 최솟값을 찾기 위해 j를 이용한다.
- 최솟값을 찾으면 i번째 요소와 최솟값을 교환하여 i번째 위치에 가장 작은 값을 옮긴다.
- i를 증가시키고 다시 위의 과정을 반복한다.


## 소스코드
```swift
func main() {
    var min, index, temp: Int
    var array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]

    for i in 0..<array.count {
        min = 9999
        index = i
        for j in i..<array.count {

            if min > array[j] {
                min = array[j]  // 발견되는 값 부여
                index = j       // 그값의 index 부여
            }
        }
        temp = array[i]
        array[i] = array[index]
        array[index] = temp
    }
}

main()
```

### 로그
i와 j가 헷갈려서.... 요란하게..


``` 

i:::::::::::::::::::::::::::::::0
j:::::::::::::::::::::::::0
 if min > array[0] {
    9999 > 1 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::1
 if min > array[1] {
    1 > 10 -> false
}
j:::::::::::::::::::::::::2
 if min > array[2] {
    1 > 5 -> false
}
j:::::::::::::::::::::::::3
 if min > array[3] {
    1 > 8 -> false
}
j:::::::::::::::::::::::::4
 if min > array[4] {
    1 > 7 -> false
}
j:::::::::::::::::::::::::5
 if min > array[5] {
    1 > 6 -> false
}
j:::::::::::::::::::::::::6
 if min > array[6] {
    1 > 4 -> false
}
j:::::::::::::::::::::::::7
 if min > array[7] {
    1 > 3 -> false
}
j:::::::::::::::::::::::::8
 if min > array[8] {
    1 > 2 -> false
}
j:::::::::::::::::::::::::9
 if min > array[9] {
    1 > 9 -> false
}
array[0] = 1 저장
i:::::::::::::::::::::::::::::::1
j:::::::::::::::::::::::::1
 if min > array[1] {
    9999 > 10 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::2
 if min > array[2] {
    10 > 5 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::3
 if min > array[3] {
    5 > 8 -> false
}
j:::::::::::::::::::::::::4
 if min > array[4] {
    5 > 7 -> false
}
j:::::::::::::::::::::::::5
 if min > array[5] {
    5 > 6 -> false
}
j:::::::::::::::::::::::::6
 if min > array[6] {
    5 > 4 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::7
 if min > array[7] {
    4 > 3 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::8
 if min > array[8] {
    3 > 2 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::9
 if min > array[9] {
    2 > 9 -> false
}
array[8] = 10 저장
i:::::::::::::::::::::::::::::::2
j:::::::::::::::::::::::::2
 if min > array[2] {
    9999 > 5 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::3
 if min > array[3] {
    5 > 8 -> false
}
j:::::::::::::::::::::::::4
 if min > array[4] {
    5 > 7 -> false
}
j:::::::::::::::::::::::::5
 if min > array[5] {
    5 > 6 -> false
}
j:::::::::::::::::::::::::6
 if min > array[6] {
    5 > 4 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::7
 if min > array[7] {
    4 > 3 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::8
 if min > array[8] {
    3 > 10 -> false
}
j:::::::::::::::::::::::::9
 if min > array[9] {
    3 > 9 -> false
}
array[7] = 5 저장
i:::::::::::::::::::::::::::::::3
j:::::::::::::::::::::::::3
 if min > array[3] {
    9999 > 8 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::4
 if min > array[4] {
    8 > 7 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::5
 if min > array[5] {
    7 > 6 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::6
 if min > array[6] {
    6 > 4 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::7
 if min > array[7] {
    4 > 5 -> false
}
j:::::::::::::::::::::::::8
 if min > array[8] {
    4 > 10 -> false
}
j:::::::::::::::::::::::::9
 if min > array[9] {
    4 > 9 -> false
}
array[6] = 8 저장
i:::::::::::::::::::::::::::::::4
j:::::::::::::::::::::::::4
 if min > array[4] {
    9999 > 7 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::5
 if min > array[5] {
    7 > 6 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::6
 if min > array[6] {
    6 > 8 -> false
}
j:::::::::::::::::::::::::7
 if min > array[7] {
    6 > 5 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::8
 if min > array[8] {
    5 > 10 -> false
}
j:::::::::::::::::::::::::9
 if min > array[9] {
    5 > 9 -> false
}
array[7] = 7 저장
i:::::::::::::::::::::::::::::::5
j:::::::::::::::::::::::::5
 if min > array[5] {
    9999 > 6 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::6
 if min > array[6] {
    6 > 8 -> false
}
j:::::::::::::::::::::::::7
 if min > array[7] {
    6 > 7 -> false
}
j:::::::::::::::::::::::::8
 if min > array[8] {
    6 > 10 -> false
}
j:::::::::::::::::::::::::9
 if min > array[9] {
    6 > 9 -> false
}
array[5] = 6 저장
i:::::::::::::::::::::::::::::::6
j:::::::::::::::::::::::::6
 if min > array[6] {
    9999 > 8 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::7
 if min > array[7] {
    8 > 7 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::8
 if min > array[8] {
    7 > 10 -> false
}
j:::::::::::::::::::::::::9
 if min > array[9] {
    7 > 9 -> false
}
array[7] = 8 저장
i:::::::::::::::::::::::::::::::7
j:::::::::::::::::::::::::7
 if min > array[7] {
    9999 > 8 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::8
 if min > array[8] {
    8 > 10 -> false
}
j:::::::::::::::::::::::::9
 if min > array[9] {
    8 > 9 -> false
}
array[7] = 8 저장
i:::::::::::::::::::::::::::::::8
j:::::::::::::::::::::::::8
 if min > array[8] {
    9999 > 10 -> true
-----현재값 저장------
}
j:::::::::::::::::::::::::9
 if min > array[9] {
    10 > 9 -> true
-----현재값 저장------
}
array[9] = 10 저장
i:::::::::::::::::::::::::::::::9
j:::::::::::::::::::::::::9
 if min > array[9] {
    9999 > 10 -> true
-----현재값 저장------
}
array[9] = 10 저장
array:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

```