[1] 선택 정렬(selection sort)

selection sort란?

정렬 되지 않은 배열에서 최솟값을 찾은 후 

-> 찾은 최솟값과 맨앞에 있는 수를 swap 한다

-> 첫번째 원소를 제외한 배열에 대해 동일한 과정을 반복한다.

 

예시를 보면 더 쉽게 이해할 수 있습니다!

 

다음과 같은 배열이 있다고 합시다.

 

1. 최솟값을 찾는다

다음과 같이 찾을 수 있죠!

 

2. 최솟값과 가장 앞의 수를 swap 한다

 

3. 맨 앞의 원소는 제외한다

 

4. 최솟값을 찾는다

-> 다음의 경우 최솟값과 가장 앞의 원소가 동일하므로 swap은 안해도 되겠네요!

 

 

5. swap한 앞의 원소들은 제외한다.

 

6. 최솟값을 찾는다.

 

7. 최솟값과 가장 앞의 원소를 swap 한다.

 

8. 계속해서 반복하면...

의 정렬된 배열을 얻을 수 있습니다.

 

위에서 설명한 것을 C언어로 구현해볼까요?

 

void selection_sort(int list[], int n) {
    int i, j;
    int min, temp;
 
    for (i = 0;i < n;i++) {
        min = i;
 
        // 최솟값을 찾는다.
        for (j = i + 1;j < n;j++)
            if (list[j] < list[min])
                min = j;
       
        // 찾은 최솟값과 swap 한다
        temp = list[i];
        list[i] = list[min];
        list[min] = temp;
    }
}
 

다음과 같이 구현할 수 있습니다.

 

swap 은 위와 같이 구현해도 되고,

swap 함수를 새롭게 정의해도 괜찮습니다.

(하지만 함수를 사용하면 시간이 더 드니까ㅠㅠ)

 

void selection_sort(int list[], int n) {
    int i, j;
    int min;
 
    for (i = 0;i < n;i++) {
        min = i;
 
        // 최솟값을 찾는다.
        for (j = i + 1;j < n;j++)
            if (list[j] < list[min])
                min = j;
       
        // 찾은 최솟값과 맨 앞의 원소를 swap 한다
        swap(&list[min], &list[i]);
    }
}
 
void swap(int *x, int *y){
    int temp = *x;
    *x = *y;
    *y = temp;
}

위처럼 swap 함수 따로 빼도 괜춘!

 

매크로로 swap을 정의해도 괜찮아요!

 

 

#define SWAP(x, y, t)((t)=(x), (x)=(y), (y)=(t))
void selection_sort(int list[], int n) {
    int i, j;
    int min, temp;
    for (i = 0; i < n; i++) {
        min = i;
        // 최솟값을 찾는다.
        for (j = i + 1; j < n; j++)
            if (list[j] < list[min])
                min = j;
 
        // 찾은 최솟값과 맨 앞의 원소를 swap 한다
        SWAP(list[min], list[i], temp);
    }
}

 

실제 main 함수까지 작성해볼까요

위에서 본 예시로 작성해보면 다음과 같습니다.

#include <stdio.h>
 
#define SWAP(x, y, t)((t)=(x), (x)=(y), (y)=(t))
 
void selection_sort(int[], int);
 
 
int main() {
    int list[6] = { 5, 2, 1, 6, 3, 4 };
    printf("unsorted list\n");
    for (int i = 0; i < 6; i++) 
        printf("%d ", list[i]);
    
 
    selection_sort(list, 6);
    printf("\n\nsorted list\n");
    for (int i = 0; i < 6; i++) {
        printf("%d ", list[i]);
    }
 
    return 0;
}
 
void selection_sort(int list[], int n) {
    int i, j;
    int min, temp;
    for (i = 0; i < n; i++) {
        min = i;
        // 최솟값을 찾는다.
        for (j = i + 1; j < n; j++)
            if (list[j] < list[min])
                min = j;
 
        // 찾은 최솟값과 맨 앞의 원소를 swap 한다
        SWAP(list[min], list[i], temp);
    }
}
 

실행 결과