1.-(1) 기본 정렬 알고리즘 - Selection Sort(선택정렬)

이번 시간에는 기본적인 정렬 알고리즘을 배울겁니다.

 

정렬 알고리즘은 정말 여러가지 있지만 오늘 다뤄볼 정렬은

 

Selection Sort (선택정렬)

 

입니다.

 

첫 시간이기에 쉬운 정렬 알고리즘을 다룹니다.

 

정수를 오름차순으로 정렬하므로 내림차순이나 다른 특정한 순서로 정렬하고 싶으면 조건을 바꾸시면 됩니다.

 

 

 

먼저 Selection Sort 입니다.

 

Selection Sort 는 \( n \) 개의 수 중에 가장 작은 수를 찾아(혹은 가장 큰 수를 찾아) 아직 정렬되지 않은 부분의 맨 앞자리에 위치시키는 방법으로 정렬을 수행합니다.

위와 같이 정렬을 하고자 할 때,

 

1.  5, 1, 3, 4, 2 를 모두 확인하면서 가장 작은 수를 찾습니다. -> 이 때 가장 작은 수는 1 입니다.

2. 그럼 이 1과, 현재까지 정렬되지 않은 맨 앞자리인 5와 자리를 바꿉니다.

 

그리고 이제 아까 했던 1번 과정을 정렬되지 않은 구간인 5부터 다시 수행합니다.

5 3 4 2 로 확인하고 가장 작은 수인 2를 찾습니다.

 그런 이 2와 현재까지 정렬되지 않은 맨 앞자리인 5와 자리를 바꿉니다.

어느정도 감이 오죠?

이런 과정을 맨 마지막까지 하면 결국 모든 수가 정렬됨을 할 수 있습니다.

 

이 알고리즘의 시간복잡도는 어떻게 될까요?

 

우리는 \( n \)개의 수에 대해 한개씩 정렬하게 됩니다. 게다가 현재까지의 가장 작은 수를 찾아야 합니다.

\( n, n-1, n-2, n-3 .... 1 \) 번 탐색하여 현재까지의 가장 작은 수를 찾을 수 있습니다.

그럼 이 나열된 수의 총 합이 시간복잡도가 되는데, 총 합은 \( \frac{n\times(n+1)}{2} \) 이므로

시간복잡도가 \( O(n^{2}) \) 임을 알 수 있습니다.

 

공간복잡도는 \( n \) 크기의 배열이 필요하므로 \( O(n) \) 임을 알 수 있습니다.

 

이 알고리즘을 사용하여 아래 문제를 해결할 수 있습니다.

www.acmicpc.net/problem/2750

2750번: 수 정렬하기

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 문제입니다.

입력의 첫째 줄에 수의 갯수가 주어지고, 둘째 줄부터 N개의 줄에는 숫자가 주어집니다.

 

아래는 문제를 해결할 수 있는 selection sort 코드입니다.

#include <bits/stdc++.h>
using namespace std;
 
int numbers[1001];
 
int main()
{
    int n;
    scanf("%d", &n);
 
    for(int i=0;i<n;i++)
        scanf("%d", &numbers[i]);
 
    int idx = 0; // 현재까지의 가장 작은 수의 index를 저장하는 변수.
    for(int i=0;i<n;i++)
    {
        idx = i;
        for(int j=i+1;j<n;j++)
        {
            if(numbers[idx] > numbers[j]) // 현재까지의 가장 작은 수보다 지금 보고있는 수가 더 작을 때
            {
                idx = j; // idx 변수에 지금 보고있는 수의 index를 저장한다.
            }
        }
        // 현재까지 정렬되지 않은 자리 : i
        // i번째 숫자와 idx번째 숫자와 자리를 바꾼다.
        int tmp = numbers[idx];
        numbers[idx] = numbers[i];
        numbers[i] = tmp;
    }
 
    for(int i=0;i<n;i++)
        printf("%d\n", numbers[i]);
    return 0;
}