O(n^2) 정렬 - 선택정렬(SelectionSort)

오름차순으로 정렬하기 위해 2중 for문을 이용합니다.

 

행렬의 i 위치보다 작은 값중에 가장 작은 값을 (i+1)~(size-1)위치에서 찾아, i위치와 교환(Swap) 합니다.

 

시간복잡도는 삽입정렬이나 버블정렬과 같이 빅오 n제곱을 갖습니다.

 

#include<iostream>
#include<cstring>
using namespace std;
 
#define MAX 500
int ar[MAX];
 
void Swap(int idx1, int idx2)
{
    int tmp = ar[idx1];
    ar[idx1] = ar[idx2];
    ar[idx2] = tmp;
}
 
void SelectionSort(int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int idx = i, min = ar[i];
        for (int j = i + 1; j < size; j++)
        {
            if (min > ar[j])
            {
                min = ar[j];
                idx = j;
            }
        }
        if (i != idx)
            Swap(i, idx);
    }
}
 
int main()
{
    int n; cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> ar[i];
    }
    SelectionSort(n);
    for (int i = 0; i < n; i++)
    {
        cout << ar[i] << ' ';
    }
    cout << endl;
    return 0;
}