선택 정렬 (Selection Sort) 알고리즘

이번에는 비교정렬 알고리즘인 선택 정렬 (Selection Sort) 알고리즘에 대해 알아보겠습니다!

 

# 동작과정 

선택정렬은 매우매우매우 간단합니다

매번 비교마다 최솟값(오름차순 정렬) 혹은 최댓값(내림차순 정렬)을 제일 앞으로 보내주면 되는데요 간단한 만큼 직관적이지만 시간복잡도가 꽝입니다...

 

# Python 코드

오름차순으로 정렬하는 코드입니다!
인덱스를 처음부터 순회하며 매번 최솟값 인덱스를 찾아 해당 위치의 값과 최솟값 인덱스의 값을 교환해줍니다  

def selection_sort(A):

    n = len(A)

    for i in range(n):

        least = i # 현재 위치를 최솟값 위치로 가정

        for j in range(i+1, n):

            if A[j] < A[least]: # 더 작은 값이 있으면

                least = j  # 최솟값 인덱스 위치 갱신

        A[i], A[least] = A[least], A[i] # 현재 위치와 최솟값 위치 교환

    return A

# 성능분석 - 시간복잡도

 

선택정렬의 시간복잡도는 매번 비교마다 최선, 최악, 평균적인 경우 모두 최솟값 혹은 최대값을 찾으며 끝까지 동작해야 하기 때문에  최선인 경우(Best), 최악의 경우(Worst), 평균적인 경우(Average) 모두 동일하게 O(n²)으로 동작합니다!

# 관련 문제

백준  1427번 소트인사이드

https://www.acmicpc.net/problem/1427

 

# reference

Do it! 알고리즘 코딩 테스트 - 파이썬 편(김종관 저/이지스퍼블리싱 (주))