선택 정렬 알고리즘(Selection Sort)

인프런 - 파이썬으로 배우는 알고리즘 기초 강의 이미지

✔ 선택 정렬(Selection Sort)

선택 정렬은 가장 원시적이고 기초적인 방법 중 하나입니다.

선택 정렬은 이름 그대로 선택한 값을 제일 앞으로 보내서 정렬하는 알고리즘이다.

선택한 값이란 오름 차순일 경우 최솟값을 얘기하고, 내림 차순일 경우 최댓값을 얘기한다.

 

✔ 선택 정렬 동작 과정

1. 리스트의 첫 번째 인덱스를 교환(Swap) 대상으로 선정하고,
   교환 대상과 교환 대상 이후의 리스트를 전체 비교하면서 최솟값을 찾은 후 교환 대상과 최솟값의 위치를 교환(Swap)
2. 첫 번째 인덱스는 정렬된 상태이기 때문에 고정. 두 번째 인덱스를 교환(Swap) 대상으로 선정하고,
   첫 번째 인덱스를 제외한 전체 리스트를 비교하면서 최솟값을 찾은 후 교환 대상과 최솟값의 위치를 교환(Swap)
3. 정렬이 완료될 때까지 위 동작 반복

 

✔ 선택 정렬 구현(C++)

#include <iostream>
using namespace std;

const int LEN = 7;
int arr[LEN] = {2, 9, 5, 6, 4, 1, 7};

void SelectionSort(int *arr, int len) {
    int temp=0, mn=0, idx=0;    
    /*
    	len-1하는 이유는 i가 마지막 전 일때
        마지막과 비교 후 같이 정렬이 되므로 마지막까지 반복할 필요 없다
    */
    for(int i=0; i<len-1; ++i) {
        mn = arr[i]; // 최솟값은 리스트의 Swap 대상 값으로 지정
      	for(int j=i+1; j<len; ++j) {
            if(mn > arr[j]) {
                mn = arr[j];
                idx = j;
            }
        }
        // Swap 부분(최솟값과 교환 대상 Swap)
        temp = arr[i];
        arr[i] = arr[idx];
        arr[idx] = temp;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    SelectionSort(arr, LEN);
    
    for(int i : arr)
        cout << i << " ";
    return 0;
}

 

✔ 선택 정렬 시간 복잡도

선택 정렬의 시간 복잡도는 아래와 같다.

$$ O(N^2) $$

 

(N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2 = N * N = O(N^2)

시간 복잡도에 대한 좀 더 자세한 내용은 아래의 내용에서 확인하세요.
시간 복잡도

 

 

 

🔗 Reference

• 정렬의 개요와 선택 정렬