선택정렬

서재환·2021년 10월 22일
0

CT

목록 보기
4/8

선택정렬

선택정렬의 개념은 나를 제외한 다른 사람들 중에 가장 작은 사람을 찾아서
내가 서있는 자리와 가장 작은 사람의 위치를 바꾸는 것에 있다. 그리고 여
기서 키포인트는 한번 싸이클이 돌면 가장 작은 사람이 가장 앞의 위치에 
위치하게 된다는 것이다.

input = [4, 6, 2, 9, 1]

def selection_sort(array):
    n = len(array)
    for i in range(n-1):
        current_min = array[i]
        for j in range(i+1, n):
            if current_min > array[j]:
                current_min = array[j]
                store_index = j
        array[i], array[store_index] = array[store_index], array[i]

    return array

배열이 [4, 6, 2, 9, 1]와 같을 때 for문 i의 사이클이 한번 돌게 되면 배열
은 [1, 6, 2, 9, 4]의 순서로 가장 작은 원소가 맨 앞에 위치하게 되고 내가 
있었던 위치(index=0)은 가장 작은 원소가 있던 자리와 스위치 된다.

따라서 한텀을 돌았을 때 가장 작은 위치에 있는 index를 기억해야 하고 최종
적으로 가장 작은 index가 도출되기 이전 기준값보다 작은 값이 있어 해당 자리
의 index를 기억해야 하는 변수가 필요함을 알 수 있고 또한 비교대상의 기준점
이 본래의 기준점보다 작은 수를 발견했을 때 기준점이 변경되어야 하므로 해당 기
준점에 대한 변수가 필요함을 알 수 있다.

기준점에 대한 변수 current_min가 필요한 것이 그런 이유이고 그 때의 index를
기억해야 하므로 store_index 변수가 필요한 것이 위에서 설명한 이유이다.

0번째가 기준이되어 나머지 원소를 기준으로 선택정렬을 수행한 후에는 index가
1번째가 기준이되어 나머지원소 (index=2 ~ index=len(array)-1)부분까지 순
차적으로 돌면서 위의 사이클을 index가 len(array)-2가 될때까지 수행하여 순차
적으로 배열을 정렬하게 되는 것이다.

0개의 댓글