[알고리즘] 1) 선택 정렬 알고리즘

항상 알고리즘을 공부해야지 맘잡고 책과 영상을 시작하게 되면 맞이하는 과목(?)이 있다. 

바로 정렬이다. 이번 기회에 블로그에 정리하면서 복습하려고 한다. 

주로 Google 선생과 Youtube 선생의 소스에서 자료를 얻지만 대표적으로는 [동빈나] 선생님, https://www.daleseo.com/ 블로그 자료를 주로 참고하였다는 것을 미리 밝힌다. 

 

'정렬'의 개념은 우리가 흔히 말하는 '오름차순' 이나 '내림차순'으로 데이터를 정리하는 방법들을 정의한다. 

선택 정렬 알고리즘

배열 내 여러 인자 값이나 데이터가 있다고 가정해보자.

 

1. 첫번째 값을 '기준'으로 두고 두번째, 세번째 값과 비교를 진행한다.
2. 이때 뒤(N번째)의 값이 '기준'되는 값보다 작다면, 기준값과 자리를 바꾼다. 

이 개념을 도입하여 코드를 짜야 한다면, 그것은 바로 '선택' 정렬 알고리즘을 사용한다고 할 수 있다.

해당 시간 복잡도는 O(N^2)

설명

1. 0번째 값을 기준으로 두고 1번째 값부터 차례차례 비교하다 보니 3번째 값이 더 작은 것을 확인, 자리를 바꾼다. (스와핑)

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

2. 이번에는 1번째 값을 기준으로 두고 2번째 값부터 차례차례 비교하다 보니 4번째 값이 더 작은 것을 확인, 자리를 바꾼다. 

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

이런식으로 하나씩 최소 값 비교를 통해 문제를 해결해나가는 방식을 '선택 정렬 알고리즘'이라 한다. 

파이썬 구현

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]