선택 정렬
선택 정렬이란, 선택되지 않은 값들 중 가장 작은 값을 계속해서 선택해서 정렬하는 것이 선택 정렬 알고리즘입니다.
선택 정렬 나무 위키
1.
주어진 리스트 중에서 최소값을 찾는다.
2.
그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3.
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
선택 정렬 장단점
장점
•
삽입 정렬보다 더욱 빠른 속도를 가집니다.
•
최악의 경우에도 O(n^2)의 시간 복잡도를 가지는 삽입 정렬보다 더 좋은 시간 복잡도를 가집니다.
•
구현이 간단하고, 코드가 직관적입니다.
단점
•
다른 정렬 알고리즘과 비교하면 성능이 떨어질 수 있습니다.
•
정렬할 배열의 크기가 클 경우에는 다른 정렬 알고리즘보다 느릴 수 있습니다.
선택 정렬의 정확한 순서
아래는 선택 정렬의 정확한 순서를 파악하기 위한 참고 그림입니다.
1.
최솟값 찾기
•
5,2,4,6,1,3 의 숫자 중 가장 작은 숫자를 찾습니다.
2.
바꾸기
•
가장 작은 숫자는 1이므로 가장 앞의 숫자인 5와 교체합니다.
1.
다음 최솟값 찾기
•
1,2,4,6,5,3 의 숫자 중 정렬된 1을 제외한 다음 숫자를 찾습니다.
2.
바꾸기
•
가장 작은 숫자는 2이므로 두 번째 인덱스인 2(자신 과) 교체합니다.
위 과정을 마지막 인덱스까지 반복합니다.
선택 정렬 코드 구현
아래는 선택 정렬 코드를 C#으로 구현한 코드입니다.
for (int i = 0; i < n - 1; i++)
{
int minIndex = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[minIndex])
{
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
C#
복사
•
첫 번째 for 문에서는 i = 0부터 배열의 길이인 n-1까지, 즉, 마지막 인덱스 전까지 반복합니다.
•
minIndex는 가장 작은 값을 가리키는 인덱스를 저장합니다.
•
두 번째 for 문에서는 i의 다음 인덱스부터 끝까지 검사하여 가장 작은 인덱스를 찾습니다.
•
교체 과정에서는 가장 작은 인덱스 번호와 현재 인덱스인 i를 교환합니다.
