Select Sort - 선택 정렬과 코드

선택정렬은 거품정렬과 비슷하다. 둘다 반복문을 완전히 2번 돈다는 점에서

최선/평균/최악의 시간복잡도가 n^2로 같다. 

다른 점은 선택정렬이 거품정렬보다는 swap 횟수(메모리 이동)이 적을 수 있다는 것이다.

 

예를 들어 2 3 5 1 과 같은 배열을 오름차순으로 정렬한다고 하면

선택 정렬로 정렬하는 과정은 다음과 같다. 

선택 정렬은 각 반복마다 가장 끝에 최대값을 찾아 넣는다.

그래서 N길이의 배열의 경우 첫 반복에는 arr[N-1] = MAX(arr[0] ~ arr[N-1]) 이 들어가고

다음 반복에는 arr[N-2] = Max(arr[0] ~ arr[N-2]) 가 들어가게 된다.

 

의사코드를 작성해보면 아래 같은 느낌이다.

for ( i = 0 ~ N-1 ){
	for( j = 1 ~ N-1-i ){
    	maxIdx = arr를 돌며 최대값의 인덱스 저장
    }
    swap(arr[N-i-1], arr[maxIdx])
}

 

간단한 예제를 C언어로 작성해보면 다음과 같다.

#include <stdio.h>
#include <string.h>

void swap(int* a, int* b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

//오름차순 order 1, 내림차순 order -1
void select_sort(int n, int order, int arr[]){
    int i,j, idx;
    for(i = 0; i < n-1; ++i){
        idx = 0;
        for(j = 1; j < n-i; ++j){
            if(order*arr[j] > order*arr[idx]){
                idx = j;
            }
        }
        swap(&arr[idx], &arr[n-1-i]);
    }
}

int main(void)
{
    int i;
    int arr[10];
    for(i = 0; i < 10; ++i){
        scanf("%d", arr + i);
    }
    select_sort(10, 1, arr);

    for(i = 0; i < 10; ++i){
        printf("%d ", arr[i]);
    }
}

 

반복/비교 횟수도 그렇고 거품정렬과 크게 다르지 않은 것 같다.