선택정렬

개념

선택정렬은 정렬되지 않은 구간에서 최소값(또는 최대값)을 선택하여, 그 값을 정해진 위치로 이동시키는 알고리즘입니다.

 

알고리즘의 동작과정

모든 위치 i(0 ~ n-2)에 대해 다음을 반복합니다.

1. 현재 위치 i부터 끝까지 순회
2. 그 구간에서 최소값과 그 인덱스를 찾음
3. 최소값의 위치와 현재 위치의 i의 원소를 교환

이때,

• 이미 정렬 된 왼쪽 구간은 다시 보지 않음
• 한 번 위치가 정해지면 다시 바뀌지 않음

 

의사코드

for i in range(0, n-1):
    min_idx = i
    for j in range(i+1, n):
        if arr[j] < arr[min_idx]:
            min_idx = j
    swap(arr[i], arr[min_idx])