선택 정렬

선택정렬의 순서

1. 가장 작은 값을 탐색하고, 처음 값과 바꿔 준다.
2. 첫번째 수를 제외하고, 나머지 중 가장 작은 수와 위치를 바꿔준다.
3. 1 ~ 2 번 과정을 반복으로 수행한다.

이처럼 선택정렬을 위해 모든수를 탐색해야 하기 때문에, 단순하지만 비효율적인 방법이다.

만약 숫자가 5번까지 있다고 치면

처음 5개의 숫자

다음 4개의 숫자

...

다음 1개의 숫자

총 탐색횟수가 4+3+2+1 번을 탐색하게 되는데,

n개의 숫자가 있다면, 1+2+3+4+5....+n-2+n-1이 되게 되고,

이를 공식으로 표현하게 되면, n * (n - 1) /2 가 된다.

숫자가 10개, 20개 이 정도로 작다면 모든 수식을 다 표현해서 하는게 맞겠지만, 크기가 커짐에 따라

+1, /2 가 탐색 횟수에는 크게 작용하지 않아서, 간략하게 표기하는데

위의 식을 간단하게 표기하면 O(N*2)으로 표기할 수 있다.

이를 빅-오 표기법( Big-O notation) 이라고 한다.

---

구조

이러한 방법으로 구조가 짜여진다.

파이썬 코드

def sel_sort(a):
    n = len(a)
    for i in range(0, n - 1):
        min_num = i
        for j in range(i + 1, n):
            if a[j] < a[min_num]:
                min_num = j
        a[i], a[min_num] = a[min_idx], a[i]
    print(a)

num_list = [2, 4, 5, 1, 3]
sel_sort(num_list)
print(num_list)

결과

[2, 4, 5, 1, 3],
[1, 4, 5, 2, 3],
[1, 2, 3, 5, 4],
[1, 2, 3, 4, 5],
[1, 2, 3, 4, 5]

---

참고

선택정렬에 관해서 춤으로 보여주는 동영상인데,
이걸 보니까 이런식으로 복잡하게 일어나는구나 한번에 와닿았다 😁

https://www.youtube.com/watch?v=gARC8MApdcY

wiki-docs

https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC