Selection Sort (선택정렬)

정렬(Sort) 은 알고리즘 효율을 높일 수 있는 핵심이다. 

처음 기초적인 정렬인 선택정렬에 대해 알아보자.

 

 

Q . 오름차순으로 정렬하는 프로그램을 작성하시오. 

 

1, 10, 5, 8, 7, 6, 4, 3, 2, 9

 

A . 가장 작은 것을 선택해서 제일 앞으로 보내자. 

 

1, 10, 5, 8, 7, 6, 4, 3, 2, 9

1, 10, 5, 8, 7, 6, 4, 3, 2, 9

1, 2, 5, 8, 7, 6, 4, 3, 10, 9

1, 2, 3, 8, 7, 6, 4, 5, 10, 9

.

.

.

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

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

 

Python 구현 

def selection_sort(arr):
    for i in range(len(arr) - 1):
        min_idx = i #0~9
        for j in range(i + 1, len(arr)): #1~10까지 
            if arr[j] < arr[min_idx]: #a의 2번째 값이 a의 1번째값보다 작을때, 
                min_idx = j #1
        arr[i], arr[min_idx] = arr[min_idx], arr[i] #자리바꿈 

a = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]
selection_sort(a)
print(a)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

 

시간복잡도 계산

그러나 선택정렬은 시간을 너~~무 잡아먹는다. 

비교를 10번, 9번, 8번, 7번 ... 1번을 하게된다..

10 * (10+1) /2 = 55번을 하게 되는 것이다. 

Python 구현 

등차수열 n (n+1) /2  -> O(N*N) -> O(N^2) '빅오표기법'으로 이렇게 표현한다.

결국 선택정렬의 복잡도는  O(N^2)이다.

Y = X^2 을 생각하면 된다.

결론 : 

데이터 수가 늘어날수록 데이터 처리 또한 갈수록 높아져서 효율적인 알고리즘은 아님.