[정렬] 선택정렬

연속된데이터를기준에따라서정렬하기위한알고리즘

 

정렬 이란 데이터를 특정한 기준에 따라서 순서대로 나열 하는것이다.

정렬을 통해 이진탐색이 가능해진다.

수많은 정렬 알고리즘이 있지만 선택정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 정도만 학습하자.

면접에도 자주 나오는 알고리즘이니 빠삭하게 알아 두고 가자 !

선택정렬

-  처리되지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞의 뎅터와 바꾸는 것을 반복

- '가장 작은것을 선택' 한다는 점에서 선택 정렬이라고 불린다.

STEP 0) 초기단계에서는모든데이터가정렬되어있지않으므로, 전체중에서가장작은데이터를선택한다.

따라서 0 을선택해 맨 앞에 있는 데이터7과 바꾼다.

 

 

STEP 1) 이제 정렬된 첫번쨰 데이터는 제외하고 그 뒤의 데이터 중에서 가장 작은 데이터인 1을 선택하여 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 5와 자리를 바꾼다

 

 

 

 

STEP 2) 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 2를 선택하고, 처리되지 않은 데이터 중 가장 앞에 있는 데이터 9와 자리를 바꾼다

 

 

STEP 8) 같은 과정을 쭉 반복 해서 위와 같은 결과가 나왔다. 

 

STEP 9) 마지막 남은 데이터는 위 과정을 수행해도 자리는 바뀌지 않으므로 이 단계에서는 정렬을 수행하지 않고 끝내면 된다.

 

파이썬으로 구현한 선택정렬

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i # 가장 작은 원소의 인덱스
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i] # 스와프

print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

파이썬의 스와프를 사용.

 

시간 복잡도

선택 정렬은 N-1번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다

N + (N-1) + (N-2) + ... + 2  ==> Nx (N+1)/ 2번의연산   ==> O(N^2)

 

위와 같이 선택정렬은 다른 정렬 알고리즘과 비교하여 매우 비효율 적이다.

다만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 잦으므로 선택 정렬 소스코드에 익숙해질 필요는 있다