C++ 코딩테스트 강좌, 선택 정렬

문제 설명

주어진 정수 배열을 오름차순으로 정렬하는 함수를 작성하시오. 이때 사용할 정렬 알고리즘은 선택 정렬(Selection Sort)입니다.

입력

첫 번째 줄에 정수 N이 주어집니다. (1 ≤ N ≤ 1000)
두 번째 줄에 N개의 정수가 주어집니다. (정수 A[i]는 -10000 ≤ A[i] ≤ 10000)

출력

오름차순으로 정렬된 배열을 한 줄에 공백으로 구분하여 출력합니다.

선택 정렬(Selection Sort) 개념 정리

선택 정렬은 가장 간단한 정렬 알고리즘 중 하나로, 주어진 리스트에서 가장 작은 값을 찾아서 맨 앞의 값과 교환하는 방식으로 작동합니다. 이 과정을 리스트의 끝까지 반복하여 정렬된 리스트를 완성하게 됩니다.

선택 정렬의 동작 과정

현재 리스트에서 가장 작은 값을 찾습니다.
그 값을 현재 위치의 값과 교환합니다.
위의 1, 2 단계를 반복하여 리스트를 정렬합니다.

문제 풀이 과정

1. 문제 해결을 위한 이해

문제를 해결하기 위해 우선 배열에서 가장 작은 값을 찾아 맨 앞에 놓고, 그 다음 작은 값을 찾아 두 번째 위치에 놓는 방식으로 진행합니다. 이 과정은 배열의 길이만큼 반복되며, 각 단계에서 가장 작은 값을 찾기 위해 배열의 나머지 부분을 검색해야 합니다.

2. 선택 정렬 알고리즘 구현

이제 셀렉션 정렬 알고리즘을 C++로 구현해 보겠습니다. 먼저 배열을 입력받고, 그런 다음 선택 정렬 알고리즘을 적용하여 정렬한 후 출력을 진행합니다.


#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 현재 위치를 최소값의 인덱스로 설정
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 최소값이 발견된 경우
            }
        }
        // 현재 위치와 최소값의 위치를 교환
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    selectionSort(arr, n);

    for(int i = 0; i < n; i++) {
        cout << arr[i];
        if (i < n - 1) cout << " ";
    }
    cout << endl;

    return 0;
}

3. 코드 설명

각 부분의 코드를 설명하겠습니다.

void selectionSort(int arr[], int n): 선택 정렬을 수행하는 함수입니다. 매개변수로 배열과 배열의 크기를 받습니다.
for (int i = 0; i < n - 1; i++): 배열을 순회하면서 정렬을 진행합니다.
int minIndex = i;: 현재 인덱스에서 최소값의 인덱스를 초기화합니다.
if (arr[j] < arr[minIndex]): 현재 값이 최소값보다 작은 경우 새로운 최소값 인덱스를 업데이트합니다.
int temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp;: 현재 인덱스의 값과 최소값 인덱스의 값을 교환합니다.

4. 예시 실행

다음은 선택 정렬 알고리즘의 예시 실행입니다. 우선 N과 배열 값을 입력합니다.


입력:
5
64 25 12 22 11

출력:
11 12 22 25 64

시간 복잡도

선택 정렬의 시간 복잡도는 O(N²)입니다. 모든 요소를 순회하면서 최솟값을 찾아야 하기 때문에 두 개의 중첩 루프가 필요합니다. 따라서 데이터 양이 많으면 성능이 저하될 수 있습니다.

결론

이번 포스트에서는 C++을 사용하여 선택 정렬을 구현하고, 이를 통해 기본적인 정렬 알고리즘의 개념을 익혔습니다. 선택 정렬은 간단하지만 효율이 좋지 않은 알고리즘이므로, 더 큰 데이터에 대해서는 다른 정렬 알고리즘을 고려해야 합니다.

추가 자료

선택 정렬 외에도 많은 정렬 알고리즘이 존재합니다. 다음과 같은 알고리즘을 학습해보시길 권장합니다:

버블 정렬(Bubble Sort)
삽입 정렬(Insertion Sort)
머지 정렬(Merge Sort)
퀵 정렬(Quick Sort)

알고리즘과 데이터 구조에 대해 더 배우고 싶다면, 다음의 자료들을 참조해 보세요: