void SelectionSort(int A[], int n) // input Array, index size
{
int i, j, MinIndex;
for(i = 0; i<n-1;i++){
MinIndex = i;
for(j = MinIndex + 1; j<n;j++){
if(A[MinIndex] > A[j])
MinIndex = j;
}
if(MinIndex != i) swap(A[i], A[Minindex]);
}
}
알고리즘 설명
1. MinIndex 로 배열의 비교 기준을 변화시켜 비교
2. A[MinIndex] > A[j] 이면 기준 인덱스와 비교 인덱스와 비교 후 MinIndex 변경
3. 두번째 포문이 끝나고 MinIndex 값이 바뀌었다면 스왑
i번째 단계에서 항상 n-i회 비교수행
평균시간복잡도 = O(n2)
최악시간복잡도 = O(n2)
제자리성 : 제자리 정렬
- i,j,MinIndex 상수크기 메모리
불안정한 정렬
- B b a c > a b B c
'Lecture > Algorithm' 카테고리의 다른 글
[정렬] 삽입정렬 ( Insertion Sort ) (0) | 2021.05.09 |
---|---|
[정렬] 버블정렬 ( Bubble Sort ) (0) | 2021.05.09 |
[백준 1708번] 컨벡스헐 (0) | 2021.05.03 |
[기하] 단순 폐쇄 경로 찾기 (0) | 2021.04.30 |
[기하] 두 선분 교차 (Intersection) (0) | 2021.04.30 |