Selection Sort (선택 정렬)

알고리즘

정렬은 Array를 기반으로 이야기 하도록 하겠다.

정렬에는 상당히 여러가지 방법이 있는데, 선택 정렬은 가장 기초적인 방법이라고 할 수 있다.

첫번째 패스에서는 Array 전체를 검사한 다음, 가장 작은 숫자를 첫번째 Index와 맞바꿔준다.

두번째 패스에서는 첫번째 Index를 제외한 나머지에 대해서 같은 방식으로 

가장 작은 숫자를 두번째 Index와 맞바꿔준다.

이런 식으로 배열의 끝까지 검사하게 되면 오름차순의 선택정렬이 완성된다.

내림차순의 정렬을 하고 싶다면, 작은 숫자 대신 큰 숫자를 선택하는 방법을 택하면 된다.

아마도 부등호의 방향만 바꿔주면 될 것으로 본다.

효율성을 조금 더 증가시키기 위해서 몇 가지를 생각해 보자면

각각의 패스에서 자기 자신은 생각할 필요가 없을것이다.

그리고 배열의 길이를 N이라고 잡았을 때, N번째 패스를 검사하는 것은 아무런 의미가 없을 것이다.

(N-1번째 패스에서 모든 정렬이 이미 끝난다.)

이제 이러한 알고리즘을 가지고 이중 for문을 사용하여 간단히 코딩을 해보자.

코드

#include <stdio.h>

void selection_sort(int num[],int len); // 선택 정렬 함수
void tracer(int num[],int len); // 출력 함수

int main(void){
    int testArr[] = {485,241,454,325,452,685,498,890,281}; // 정렬할 Array
    int len = sizeof(testArr)/sizeof(int); // Array 길이 구하기
    selection_sort(testArr,len); // 정렬 함수 호출
}

void selection_sort(int num[],int len){
    int i,j,minIndex,tempINT;
    // for문에 사용할 인덱스 두개, 최소값을 저장할 인덱스, 숫자 임시저장공간

    for(i=0;i<len-1;i++){
        minIndex = i; // 최소값 저장 인덱스에 최초값 설정
        for(j=i+1;j<len;j++){
            if (num[minIndex] > num[j]) minIndex = j; 
            // 숫자 크기 비교해 더 작은 숫자의 인덱스 저장
        }
        if(minIndex != i){ // 현재 값과 최소값이 다르면 
            tempINT = num[minIndex];
            num[minIndex] = num[i];
            num[i] = tempINT; // 현재 값과 최소 값 스왑
        }
        tracer(num,len); // Array 출력
    }
}

void tracer(int num[],int len){
    int i;
    for(i=0;i<len;i++){
        printf("%d\t",num[i]); // 길이만큼 Array 출력
    }
    printf("\n");
}

결과