선택 정렬(Selection Sort)은 가장 간단하고 직관적인 정렬 알고리즘 중 하나다.
보통 배열이나 리스트를 정렬하는 데에 사용됩니다.
선택 정렬은 항상 동일한 시간 복잡도인 O(n^2)를 갖기 때문에, 효율적이라고 보기 어렵다.
선택 정렬의 시간 복잡도는 배열의 크기(n)에 따라서 제곱에 비례하므로 배열의 크기가 커질수록 성능이 급격하게 저하된다.
사실상 퀵정렬을 사용하는 것이 가장 효율적이다.
퀵정렬의 시간복잡도는 평균적으로 O(n log n)이다.
그리고 n이 커질수록 퀵정렬이 훨씬 빠르다.
iOS에서는 sort()함수를 통해 퀵정렬을 할수있다.
-
- 주어진 배열에서 가장 작은 값을 찾는다.
-
- 가장 작은 값과 배열의 첫 번째 요소를 교환한다.
-
- 두 번째 요소부터 다시 가장 작은 값을 찾아 두 번째 요소와 교환한다.
-
- 이와 같은 과정을 배열의 마지막 요소까지 반복한다.
아래와 같은 값이 있다. 1, 10, 5, 8, 7, 6, 4, 3, 2, 9
-
- 먼저 전체 숫자중 가장 작은 값을 찾는다 -> 1
-
- 가장 작은 숫자 1을 배열의 첫번째 요소로 교환한다.
1, 10, 5, 8, 7, 6, 4, 3, 2, 9
-
- 이제 첫번째는 제외하고, 나머지 숫자 중 가장 작은 값을 찾는다 -> 2
-
- 가장 작은 숫자 2을 배열의 두번째 요소로 교환한다.
1, 2, 5, 8, 7, 6, 4, 3, 10, 9
-
- 이제 두번째도 제외하고, 나머지 숫자 중 가장 작은 값을 찾는다 -> 3
-
- 가장 작은 숫자 3을 배열의 세번째 요소로 교환한다.
1, 2, 3, 8, 7, 6, 4, 5, 10, 9
0번부터 n번째까지 요소중 가장 작은 숫자를 찾는다. 가장 작은 숫자는 0번째와 자리를 바꾼다.
이제 0번째는 가장 작은 숫자가 위치한다.
1번부터 n번째까지 요소중 가장 작은 숫자를 찾는다. 가장 작은 숫자는 1번째와 자리를 바꾼다.
이제 1번째는 그다음 작은 숫자가 위치한다.
이걸 이제 코드로 만들어 볼꺼다.
여기서 필요한 과정은 2가지다.
-
- 어떻게 가장 작은 숫자를 찾을건지
-
- 어떻게 n번째에 숫자를 저장할 건지
- i를 0부터 n-1까지 증가시키면서 배열의 각 요소를 순회한다.
- i번째 요소를 기준으로 i 이후의 부분 배열에서 최솟값을 찾기 위해 j를 이용한다.
- 최솟값을 찾으면 i번째 요소와 최솟값을 교환하여 i번째 위치에 가장 작은 값을 옮긴다.
- i를 증가시키고 다시 위의 과정을 반복한다.
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]