Selection Sort

선택 정렬(selection sort)은 정렬되지 않은 데이터들에 대해 가장 작은 데이터를 찾아 가장 앞의 데이터와 교환해나가는 방식이다.

1. 주어진 배열 중에서 최솟값을 찾는다.

2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복한다.

* 성능

* Average

- 비교 연산 : (N * (N-1) ) / 2 번
- 교환 연산 : N 번
- 총 연산 : O (N^2)

* 특징

- 역순일 때 최악이지만, 기본적으로 Best, Worst 관계 없이 비교 연산 때문에 속도가 비슷하다
- 교환횟수가 적고, 비교횟수가 많다​
- 안정성이 없다

 

 

#include <stdio.h>
#include <malloc.h>

#define MAX 10

void selection_sort(int arr[], int n) {
    int min_idx = 0, min = 0;

    for (int i = 0; i < n - 1; ++i) {
        min_idx = i;
        min = arr[i];

        for (int j = i + 1; j < n; ++j) {
            if (min > arr[j]) {
                min = arr[j];
                min_idx = j;
            }
        }

        arr[min_idx] = arr[i];
        arr[i] = min;
    }
}

void print(int arr[], int n) {
    printf("Result :");
    for (int i = 0; i < n; ++i) {
        printf(" %d", arr[i]);
    }
    printf("\n");
}
   
int main()
{
    int arr[MAX] = { 10, 5, 1, 4, 9, 2, 6, 8, 7, 3 };

    selection_sort(arr, MAX);

    print(arr, MAX);

    return 0;
}

 

* 출처 : https://java2blog.com/selection-sort-in-java/