[알고리즘/Algorithm] 파이썬으로 선택 정렬(Selection Sort) 알아보기

Selection Sort (선택 정렬)

다음과 같은 순서를 반복하며 정렬하는 알고리즘

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

 

선택 정렬 흐름

그림과 같이 한 루프마다 제일 작은 값을 찾아 왼쪽부터 차례차례 스왑하며 정렬해준다.

개인적으로 기본 정렬 3개(버블 정렬, 선택 정렬, 삽입 정렬)중 제일 직관적인 정렬 알고리즘이라고 생각이 들었다.

 

 

선택 정렬을 파이썬으로 구현하며 아래와 같이 구현할 수 있다.

def selection_sort(target):
    # 10개의 데이터가 있는 리스트는 최대 9번의 정렬이면 정렬됨
    # 따라서 i는 range는 len - 1
    for i in range(len(target) - 1):
        # 제일 작은 값을 갖는 데이터의 index를 나타냄
        min_index = i
  
        # min_index의 값보다 작은 것이 있으면 반복하면서 할당해줌
        for j in range(i+1, len(target)):
            if target[min_index] > target[j]:
                min_index = j
        target[min_index], target[i] = target[i], target[min_index]

바깥 for문은 마지막 값을 비교할 필요는 없으니 타겟 리스트의 -1 까지만 반복해주고

안쪽 for문을 통해 작은 값이 나올 때마다 재차 min_index에 index를 할당해주어 바깥 for문이 끝나면

target[min_index]와 target[i]를 스왑해주면서 정렬을 하였다.

 

시간 복잡도

• 정렬의 여부와 상관없이 안쪽 for문을 통해 항상 값을 비교하기 때문에 O(N^2)이 된다.