자료구조 - 선택 정렬

[선택 정렬(Selection Sort)]

선택 정렬(Selection Sort)은 정렬 알고리즘 중 하나로, 리스트를 순차적으로 탐색하면서 가장 작은(혹은 큰) 값을 선택해 정렬된 부분의 뒤에 위치시키는 방식입니다.

선택 정렬은 간단하지만 효율성 면에서는 다른 정렬 알고리즘보다 떨어집니다.

시간 복잡도는 O(n^2)입니다.

 

선택 정렬 과정

1. 리스트의 첫 번째 요소부터 시작하여, 남아있는 요소들 중에서 가장 작은 요소를 찾아 첫 번째 요소와 교환합니다.
2. 두 번째 요소부터 시작하여 남아있는 요소들 중에서 가장 작은 요소를 찾아 두 번째 요소와 교환합니다.
3. 이 과정을 리스트의 마지막까지 반복합니다.

 

 

선택 정렬 의사코드

함수 selectionSort(arr):
    n = 배열의 길이(arr)

    for i = 0부터 n-1까지:
        최소 인덱스(min_idx) = i

        for j = i+1부터 n까지:
            if arr[j] < arr[min_idx]:
                min_idx = j  // 가장 작은 값을 찾음

        // 찾은 최소 값을 현재 위치로 교환
        arr[i]와 arr[min_idx] 교환

    반환 arr

 

 

선택 정렬 예제

예시 리스트: [64, 25, 12, 22, 11]

첫 번째 반복:
    전체 리스트에서 가장 작은 값(11)을 찾아 첫 번째 요소(64)와 교환.
    결과: [11, 25, 12, 22, 64]
두 번째 반복:
    나머지 리스트(25, 12, 22, 64)에서 가장 작은 값(12)을 찾아 두 번째 요소(25)와 교환.
    결과: [11, 12, 25, 22, 64]
세 번째 반복:
    나머지 리스트(25, 22, 64)에서 가장 작은 값(22)을 찾아 세 번째 요소(25)와 교환.
    결과: [11, 12, 22, 25, 64]
네 번째 반복:
    나머지 리스트(25, 64)에서 가장 작은 값(25)을 찾아 네 번째 요소(25)와 교환(자기 자신과 교환).
    결과: [11, 12, 22, 25, 64]
다섯 번째 반복:
    마지막 요소는 이미 정렬된 상태.
    결과: [11, 12, 22, 25, 64]

 

 

선택 정렬 코드

#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 min_idx = i;  // 최소값의 인덱스를 현재 인덱스로 초기화

        // 현재 인덱스 i 이후의 모든 요소들을 탐색
        for (int j = i + 1; j < n; j++) 
        {
            if (arr[j] < arr[min_idx])
            {
                min_idx = j;  // 최소값의 인덱스를 업데이트
            }
        }

        // 현재 인덱스 i와 최소값의 인덱스 min_idx의 값을 교환
        swap(arr[i], arr[min_idx]);
    }
}

int main() 
{
    vector<int> arr = {64, 25, 12, 22, 11};  // 예제 리스트

    cout << "정렬 전: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    selectionSort(arr);  // 선택 정렬 수행

    cout << "정렬 후: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}