[알고리즘] 선택 정렬

학습 목표

선택 정렬의 원리와 실행 시간을 설명하고 구현할 수 있다.

1. 정렬 알고리즘

• 정렬 알고리즘 중 하나인 선택 정렬은 배열 안에 나열된 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬이다.
• 선택 정렬은 교환 횟수를 최소화하지만 각 자료를 비교하는 횟수는 증가한다.

2. 예시

정렬되지 않은 숫자 8개가 있다. 이 숫자들을 오름차순으로 정렬해보자.

6 3 8 5 2 7 4 1

• 숫자들을 끝까지 탐색하면서 제일 작은 수를 찾는다.
• 6 3 8 5 2 7 4 1
• 가장 작은 값과 현재 리스트의 첫 번째 값을 교환한다.
• 1 3 8 5 2 7 4 6
• 1은 이제 정렬이 되어 있으니 제외하고, 두 번째 숫자부터 탐색하면서 또 제일 작은 수를 찾는다.
• 1 3 8 5 2 7 4 6
• 1 2 8 5 3 7 4 6
• 교환이 일어나지 않을 때까지 반복한다.
• 1 2 3 4 5 6 7 8