[Algorithm] Selection Sort (선택 정렬)

0. Selection sort란?

 

Selection sort는 n개의 원소가 있을 때

1. 전체 값 중 가장 작은 값을 찾고

2. 해당 값을 배열의 맨 첫 번째에 배치한 다음

3. 2번째부터 n번째까지의 최솟값을 찾아 2번째에 배치하고

4. 3의 과정을 n번째까지 반복한다.

 

처음 배열을 돌 때 n-1 번, 그 후의 과정에서 k번째 최소를 찾을 때 각각 k-1번의 비교가 일어나므로 비교 연산은 1+2+..+n-1 = n*(n-1)/2 만큼 일어난다. 따라서 시간복잡도는 O(n^2)이다.

 

1. 구현

 

1과 100 사이의 n개의 원소를 selection sort로 정렬하는 코드는 다음과 같다.

n = int(input())
nums = input()
num = nums.split()
min = 100
min_idx = 0

for i in range(n):
    num[i] = (int)(num[i])

for i in range(n):
    for j in range(i, n):
        if min > num[j]:
            min = num[j]
            min_idx = j
    num[min_idx], num[i] = num[i], num[min_idx]
    min = 100
    min_idx = 0

for i in range(n):
    print(num[i], end=' ')

i가 0부터 n-1까지 일 때, i부터 n번까지의 최솟값을 찾아 i에 배치하는 코드이다.