알고리즘 이론 - 선택 정렬

선택 정렬(select sort)

• 선택 정렬은 리스트를 순회하며 최솟값을 찾아 해당 인덱스의 값을 현재 인덱스의 값과 바꿔주는 정렬이다.

위 사진을 보면 순서대로 현재 수와 다른 수들을 전부 비교해서 자리를 바꿔주는 것을 확인할 수 있다. 알기 쉽도록 아래의 코드를 확인하자.

#선택 정렬
def select_sort(list_num):

    for i in range(0, len(list_num) - 1): # 마지막 index는 비교할 대상이 없음.
        min_idx = i # 탐색 과정에서 가장 작은 값을 찾아 현재 인덱스와 바꿔줄 변수를 초기화.
        for j in range(i + 1, len(list_num)): #두 번째 인덱스부터 끝까지 탐색.
            if list_num[j] < list_num[min_idx]: # 현재 인덱스의 값과 다음 인덱스들인 list_num[j]의 값을 비교해 최소값을 찾아 min_idx에 저장한다.
                min_idx = j

        list_num[i], list_num[min_idx] = list_num[min_idx], list_num[i] # 순회 후에 가장 작은 인덱스의 값과 현재 인덱스를 바꿔준다.
    return list_num
 
print(select_sort([2, 4, 5, 1, 3, 4, 7, 30]))

*선택 정렬은 순회를 하지만 매번 리스트안의 위치를 바꾸진 않아 버블정렬보다는 효율이 좋은 편이지만 이중 반복문을 순회하므로 시간 복잡도는 O(N^2)이다.