선택 정렬(Selection Sort)

선택 정렬(Selection Sort) - O(N2)

배열의 위치에 맞는 적절한 원소를 선택해서 배치하는 것입니다.

- 첫번째 순서에 배열에서 가장 작은 최솟값

- 두번째 순서에 배열에서 두번째로 작은 최솟값

- 세번째 순서에 배열에서 세번째로 작은 최솟값

- ...

▷ 배열 인덱스 1...N까지 순회하며 해당 인덱스에 맞는 최솟값을 찾습니다.

 

# include <stdio.h>

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

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int min = i;
        // 최솟값을 탐색한다.
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min])
                min = j;
        }

        // 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
        if (min != i)        
            swap(&arr[i], &arr[min]);
    }
}
void main() {
    int n = 5;
    int arr[5] = { 9, 6, 7, 3, 5 };
    // 선택 정렬 수행
    selectionSort(arr, n);
    // 정렬 결과 출력
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
}

 

▶  N * (N +1) / 2 정도의 연산이 일어나서 → O(N2)

 

Reference

- 정렬 알고리즘 비교 

- [BOJ] 2750 수 정렬하기