선택 정렬 (Selection Sort) (C++)

선택 정렬 (Selection Sort)

선택 정렬은 정렬되지 않은 데이터 중에서 가장 작은 값(또는 큰 값)을 선택하여 정렬된 부분의 맨 뒤에 추가하는 방식으로 동작하는 정렬 알고리즘. 간단하지만 비효율적이기 때문에 작은 데이터셋에서 주로 사용.

---

동작 원리

1. 배열의 첫 번째 요소부터 마지막 요소까지 순차적으로 접근.
2. 현재 범위에서 가장 작은 값(또는 큰 값)의 인덱스를 찾는다.
3. 해당 값을 현재 범위의 첫 번째 요소와 교환.
4. 위 과정을 배열 전체에 대해 반복.

---

특징

• 시간 복잡도:
  • 최악/평균/최선: O(n^2)
• 공간 복잡도: O(1) (추가 메모리 사용 없음)
• 비교 횟수: 항상 n(n−1)/2번의 비교가 발생.
• 비교 기반 정렬: 데이터의 크기를 비교하여 정렬.
• 비안정적 정렬: 동일한 값의 상대적인 순서가 바뀔 수 있다.

---

예제 코드 (C++)

오름차순 선택 정렬

#include <iostream>
#include <vector>
using namespace std;

void selectionSort(vector<int>& arr) {
    int n = arr.size();

    for (int i = 0; i < n - 1; ++i) {
        int minIdx = i;  // 현재 정렬되지 않은 부분에서 가장 작은 값의 인덱스
        for (int j = i + 1; j < n; ++j) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        // 가장 작은 값과 현재 위치의 값을 교환
        swap(arr[i], arr[minIdx]);
    }
}

int main() {
    vector<int> arr = {64, 25, 12, 22, 11};
    cout << "정렬 전 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    selectionSort(arr);

    cout << "정렬 후 배열: ";
    for (int num : arr) cout << num << " ";
    cout << endl;

    return 0;
}

---

코드 설명

1. for 루프:
   • 첫 번째 루프: 정렬되지 않은 부분의 첫 번째 요소를 기준으로 동작.
   • 두 번째 루프: 현재 정렬되지 않은 부분에서 가장 작은 값을 찾는다.
2. swap 함수:
   • 가장 작은 값과 현재 기준 값의 위치를 교환.
3. 정렬 과정:
   • 첫 번째 루프에서 배열의 첫 번째 요소를 가장 작은 값으로 바꾸고, 두 번째 루프에서 계속 진행하며 정렬.

---

예제 동작 과정

입력 배열: [64, 25, 12, 22, 11]

1. 첫 번째 패스 (i = 0):
   • 비교: 64 vs 25 → 25가 더 작음.
   • 비교: 25 vs 12 → 12가 더 작음.
   • 비교: 12 vs 22 → 그대로.
   • 비교: 12 vs 11 → 11이 가장 작음.
   • 교환: 64와 11 → [11, 25, 12, 22, 64]
2. 두 번째 패스 (i = 1):
   • 비교: 25 vs 12 → 12가 더 작음.
   • 비교: 12 vs 22 → 그대로.
   • 비교: 12 vs 64 → 그대로.
   • 교환: 25와 12 → [11, 12, 25, 22, 64]
3. 세 번째 패스 (i = 2):
   • 비교: 25 vs 22 → 22가 더 작음.
   • 비교: 22 vs 64 → 그대로.
   • 교환: 25와 22 → [11, 12, 22, 25, 64]
4. 네 번째 패스 (i = 3):
   • 비교: 25 vs 64 → 그대로.
   • 교환 없음: [11, 12, 22, 25, 64]
5. 최종 정렬된 배열: [11, 12, 22, 25, 64]

---

장점과 단점

장점

• 구현이 간단하며, 코드 작성이 쉬움.
• 추가 메모리를 사용하지 않음 (O(1) 공간 복잡도).

단점

• 시간 복잡도가 O(n^2)로, 데이터가 많을수록 비효율적.
• 교환 횟수는 적지만 비교 횟수가 많음.
• 안정적이지 않아 같은 값의 순서가 바뀔 수 있음.

---

활용 사례

선택 정렬은 정렬 알고리즘의 기초를 학습할 때 사용되며, 데이터가 적고 메모리 사용이 제한된 환경에서 활용할 수 있다.

---