선택 정렬(Selection Sort)
선택 정렬?
선택 정렬은 기준 항과 우측항 전체를 다 비교한 후 가장 작은수를 가장 앞으로 이동해서 정렬하는 방법입니다.
아래 위키백과의 애니메이션을 보면 쉽게 이해할 수 있습니다.
https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC
복잡도
선택정렬의 복잡도는 아래와 같습니다.
배열을 이용한 선택 정렬 예제
선택 정렬 함수
최소값(min)과 최소값의 인덱스(minIndex)를 구한 후 기준항(array[i])과 자리 교체
void selection_sort(int array[], int size){
int min, minIndex;
for(int i=0; i<size-1; i++){
int min = array[i];
int minIndex = i;
for(int j=i+1; j<size; j++){
if(min>array[j]){
min = array[j];
minIndex = j;
}
}
array[minIndex] = array[i];
array[i] = min;
}
}
실행 함수
정렬 전과 후 배열 출력
void main (){
int array[] = {11,10,33,22,55,9};
int size = sizeof(array)/sizeof(int);
printf("########### Sorting before ###########\n");
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
printf("\n########### Sorting after ###########\n");
selection_sort(array, size);
for(int i=0; i<size; i++){
printf("%-4d",array[i]);
}
}
실행 결과
참고 : C로 배우는 알고리즘 (이재규)
위키백과(선택정렬)
관련 포스팅
[DataStructure] 기수 정렬(Radix Sort)
[DataStructure] 퀵 정렬(Quick Sort)
[DataStructure] 셸 정렬(Shell Sort)
[DataStructure] 버블 정렬(Bubble Sort)
[DataStructure] 삽입 정렬(Insertion Sort)
[DataStructure] 선택 정렬(Selection Sort)
'언어 > Data Strcuture' 카테고리의 다른 글
| [C] 버블 정렬(Bubble Sort) (0) | 2019.04.20 |
|---|---|
| [C] 삽입 정렬(Insertion Sort) (0) | 2019.04.19 |
| [C] 트리(Tree) (0) | 2019.04.07 |
| [C] 큐(Queue) (2) | 2019.04.01 |
| [C] 스택(Stack) (1) | 2019.03.29 |