[자료구조 및 알고리즘] 선택정렬 (Selection Sort)

선택정렬

 

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 정렬.

 

즉, 가장 작은 것을 선택해 앞으로 보내는 과정을 반복 수행하는 정렬방법이다. 이중 for문을 이용해 구현할 수 있다.

 

코드

# 선택정렬

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^2)

최악의 경우: O(N^2)