선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

선택 정렬은 원소들 중 가장 작은(큰) 값을 정렬되지 않은 부분의 가장 왼쪽(오른쪽)과 swap 하는 정렬 알고리즘입니다.

과정

길이가 6인 정렬되지 않은 정수형 배열({1, 2, 4, 6, 3, 5})를 정렬한다고 해봅시다.

1과 2는 이미 작은 순으로 정렬되어있으므로 여기에 대해서는 swap이 일어나지 않습니다.

선택 정렬 1

다음에는 정렬되지 않은 부분에서 가장 작은 값은 3입니다. 3을 제 위치에 놓기 위해 4와 자리를 swap 합니다.

나머지 4, 5 원소도 위와 같은 단계를 거쳐 배열 정렬을 마무리합니다.

선택 정렬 3

선택 정렬 코드(C++)

#include <iostream>
using namespace std;

void selectionSort(int[], int);

int main()
{
    int myArray[6] = {1, 2, 4, 6, 3, 5};
    selectionSort(copiedArray, size);
    
    return 0;
}

void selectionSort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int minVal = arr[i];
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
        {
            if (minVal > arr[j])
            {
                minVal = arr[j];
                minIdx = j;
            }
        }

        if (minIdx != i)
        {
            swap(arr[i], arr[minIdx]);
        }
    }
}

(2022.10.11.화요일에 수정)선택 정렬을 하는 동안 진행된 비교 연산 횟수는 최대 n(n - 1) / 2회이므로 최악의 경우 O(n**2) 만큼 걸리고 만약 이미 정렬된 배열이 온다고 해도 비교는 똑같이 진행되므로 best case에서도 O(n**2)으로 해결됩니다.

 

선택 정렬에서 i, j, minVal, minIdx, swap에 사용될 temp 등의 몇 개의 변수만 사용되므로 공간 복잡도는 O(1)이라 할 수 있습니다. 배열 내에서 정렬되므로 In-place 알고리즘이고 정렬 간 같은 원소들의 위치는 바뀔 수 있으므로 Non-stable sorting 알고리즘입니다.