선택 정렬 (Selection Sort)

선택 정렬(selection sort)이란, 다음과 같은 순서를 반복하며 정렬하는 알고리즘이다.

1. 주어진 데이터 중, 최솟값을 찾음
2. 해당 최솟값을 데이터 맨 앞에 위치한 값과 교체함
3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함

 

직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting

 

https://en.wikipedia.org/wiki/Selection_sort

 

즉, '최솟값을 선택한다'고 해서 선택 정렬이라고 이해하면 된다.

 

코드로 구현해보기 전에, 데이터가 두 개일 때, 세 개일 때, 네 개일 때 어떤 순서로 진행되는지 알아보겠다.

 

데이터가 두 개일 때

• ex) data_list = [9, 1]
  • data_list[0] > data_list[1] 이므로 data_list[0] 값과 data_list[1] 값을 교환

데이터가 세 개일 때

• ex) data_list = [9, 1, 7]
  • 처음 한 번 실행하면, 1, 9, 7이 됨
  • 두 번째 실행하면, 1, 7, 9가 됨

데이터가 네 개일 때

• ex) data_list = [9, 3, 2, 1]
  • 처음 한 번 실행하면, 1, 3, 2, 9가 됨
  • 두 번째 실행하면, 1, 2, 3, 9가 됨
  • 세 번째 실행하면, 변화 없음

 

이제 이 것을 알고리즘으로 구현해보면, 일단 순서대로 봤을 때 이렇게 작성해야 한다.

 

1. for stand in range(len(data_list) - 1) 로 반복
2. lowest = stand 로 놓고,
3. for num in range(stand, len(data_list)) -> stand 이후부터 반복
4. 내부 반복문 안에서 data_list[lowest] > data_list[num] 이면,
5. lowest = num
6. data_list[num], data_list[lowest] = data_list[lowest], data_list[num] 으로 스왑

 

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]
    return data

 

이 코드를 테스트 해보면,

 

import random

data_list = random.sample(range(100), 10)

print(selection_sort(data_list))

 

 

이렇게 잘 정렬되어 출력된다.

 

선택 정렬도 반복문 안에서 반복문을 쓰고 있기 때문에, 시간 복잡도는 O(n^2)이다. 실제로 상세하게 계산하면, n * (n - 1) / 2 이다.

 

 

 

 

 

[참고자료]

패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료