[자료구조] Select sort (선택 정렬)

Select sort는 개념이 무척 간단하다.

오름차순의 경우 각 step마다 가장 큰 값을 찾아 제일 끝 요소와 자리를 바꾼다.

내림차순의 경우 각 step마다 가장 큰 값을 찾아 제일 첫 요소와 자리를 바꾸면 된다.

그림으로 설명하자면 아래와 같다.

STEP 1) 모든 요소를 검사하여 가장 큰 값을 array[max-1]에 저장한다.

STEP 2) max-1 요소 전까지 검사하여 가장 큰 값을 array[max-2]에 저장한다.

STEP 3) max-2 요소 전까지 검사하여 가장 큰 값을 array[max-3]에 저장한다.

선택 정렬의 경우 시간 복잡도는 O(n^2)이며, 알고리즘이 매우 단순하다.

또한 메모리 이동이 적을 수 있어서 메모리가 제한적인 환경에서 사용하면 성능 상 유리하다.

코드는 아래와 같이 구현 가능하다.

#include <stdio.h>
 
#define MAX_NUM (10)
#define SORT_UP (1)
#define SORT_DOWN (-1)
 
typedef struct _score
{
    int id;
    char name[10];
}SCORE;
 
void print_data(SCORE *d);
void sort_select(SCORE *d, int order);
 
int main(void)
{
    SCORE list[MAX_NUM] = { { 2, "kim" },{ 5, "lee" },{ 1, "park" },{ 7, "kang" },{ 4, "jung" },
    { 10, "su" },{ 9, "won" },{ 6, "ring" },{ 3, "son" },{ 8, "feng" } };
 
    printf("UP sort\n");
    sort_select(list, SORT_UP);
    print_data(list);
 
    printf("\nDOWN sort\n");
    sort_select(list, SORT_DOWN);
    print_data(list);
 
    return 0;
}
 
void sort_select(SCORE *d, int order)
{
    int i, j, k;
    SCORE temp;
 
    for (i = 0; i < MAX_NUM - 1; i++) {
        for (k = 0, j = 1; j < MAX_NUM - i; j++) {
            if ((d[k].id - d[j].id) * order < 0) {
                k = j;
            }
        }
        j--;
 
        if (j != k) {
            temp = d[j];
            d[j] = d[k];
            d[k] = temp;
        }
    }
}
 
void print_data(SCORE *d)
{
    int i = 0;
 
    for (i = 0; i < MAX_NUM; i++) {
        printf("ID(%d) NAME(%s)\n", d[i].id, d[i].name);
    }
}
 

이전에 포스팅하였던 bubble sort에서 함수 안에 내용만 위에 설명한대로 수정하였다.

오름차순 및 내림차순에 대한 코드를 작성하였으며, id 기준으로 정렬을 수행한다.

코드 실행 결과는 아래와 같다.

역시 오름차순과 내림차순 모두 잘 정렬된 것을 확인할 수 있다.

위보다 더 효율적인 코드도 구현 가능하지만 기본이 되는 코드이기 때문에 참고하면 좋을 것 같다.