Selection Sort

Selection Sort는 이름 상에서도 알 수 있듯이 무언가(?)를 선택해서 정렬하는 방식이다.

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64

글로는 이해하기 어려울 수 있으니, 하나의 Flow을 살펴보도록 하자.

위의 정렬 과정을 보면 공통 부분은 배열에서 가장 작은 값을 찾는 것이다. 그리고 가장 작은 값을 차례차례 정리한다.

(처음에 언급했던 무엇가는 바로 가장 작은 값이다.)

간단히 코드를 확인해보자.

for i in range(len(A)):

    # Find the minimum element in remaining  
    # unsorted array 
    min_idx = i
    for j in range(i + 1, len(A)):
        if A[min_idx] > A[j]:
            min_idx = j

            # Swap the found minimum element with  
    # the first element
    A[i], A[min_idx] = A[min_idx], A[i]