[기초] C++ 알고리즘 : 선택 정렬 (Selection Sort)

---

 

가장 작은 (혹은 가장 큰) 원소를 선택해 앞으로 옮기는 방식입니다.

시간 복잡도는 O(n^2)으로 비효율적입니다.

 

---

 

#include <iostream>

// 배열을 출력하는 함수
void printArray(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

// 선택 정렬 함수
void selectionSort(int arr[], int size) {
    for (int i = 0; i < size - 1; ++i) {
        // 최솟값의 인덱스를 저장할 변수
        int minIndex = i;
        
        // 최솟값 탐색
        for (int j = i + 1; j < size; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 최솟값을 현재 위치로 이동
        if (minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    std::cout << "정렬 전 배열: ";
    printArray(arr, size);
    
    selectionSort(arr, size);
    
    std::cout << "정렬 후 배열: ";
    printArray(arr, size);
    
    return 0;
}

 

이 코드는 선택 정렬 알고리즘을 구현하고, 주어진 배열을 정렬한 뒤 결과를 출력합니다.

코드를 실행하면 정렬되지 않은 배열이 정렬된 상태로 출력됩니다.

 

정렬 전 배열: 64 25 12 22 11 
정렬 후 배열: 11 12 22 25 64

 

이 출력은 배열이 선택 정렬을 통해 어떻게 오름차순으로 정렬되는지 보여줍니다.

코드의 'selectionSort' 함수에서 배열의 각 위치를 순회하면서 그 위치 이후의 최솟값을 찾고,

그 최솟값을 현재 위치로 이동시키는 과정을 반복합니다.

이렇게 하면 배열의 앞부분부터 차례대로 최솟값이 정렬되어 배열이 오름차순으로 정리됩니다.

 

마무리

 

선택 정렬은 매우 직관적이지만, 데이터의 양이 많을 때는 효율적이지 않습니다.

각 단계마다 전체 배열을 다시 검사하기 때문에 시간 복잡도는 'O(n^2)'으로,

데이터가 많아질수록 성능이 크게 저하됩니다.

그럼에도 불구하고 구현이 간단해서 정렬 알고리즘을 배울 때 자주 사용됩니다.