선택 정렬

비교식>교환 방식>선택 정렬

선택 정렬

• 선택 정렬 Selection Sort : 기준 위치에 맞는 원소를 선택해 자리를 교환하는 방식

 

밑에는 가장 작은 원소부터 기준 위치로 설정하고 가장 작은 값과 계속 교환하여 자리를 찾는 방식이다.

이후 정렬된 자리를 제외하고 다시 자리를 교환하여 자리를 찾는다.

시간 복잡도: O(n2)

전체 비교 횟수: (n-1) + (n-2) + ``` + 2 + 1 = n(n-1) / 2

 

선택 정렬 알고리즘

selectionSort(a[], n)
	for(i<-1;i<n;i<-i+1) do{
    	a[i], ```, a[n-1] 중에서 가장 작은 원소 a[k]를 선택해 a[i]와 교환한다.
    }
end selectionSort()

 

선택 정렬 프로그램

[selectSort.c]
#include <stdio.h>
void SelectionSort(int a[], int size){
	int i, j, t, min, temp;
    
    for(i=0;i<size-1;i++){
    	min = i;
        for(j=i+1;j<size;j++){
        	if(a[j]<a[min]) min = j;
        }
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;
        printf("\n");
        for(t=0;t<size;t++) printf("%3d ", a[t]);
    }
}

int main(void){
	int i, list[8] = { 69, 10, 30, 2, 16, 8, 31, 22 };
    int size = sizeof(list)/sizeof(list[0]);
    SelectionSort(list, size);
    
    getchar(); return 0;
}

 

• 예시

기존	69	10	30	2	16	8	31	22
1	2	10	30	69	16	8	31	22
2	2	8	30	69	16	10	31	22
3	2	8	10	69	16	30	31	22
4	2	8	10	16	69	30	31	22
5	2	8	10	16	22	30	31	69
6	2	8	10	16	22	30	31	69
7	2	8	10	16	22	30	31	69
8	2	8	10	16	22	30	31	69