[C++] [정렬 알고리즘] 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort)

선택 정렬 (출처: 위키백과)

 

선택 정렬은 정렬 알고리즘 중 하나이다. 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.

 

선택 정렬은 정렬 되어있지 않은 데이터 중 최소값을 찾아 맨 앞 값과 자리를 바꾼다. 정렬이 완료된 나머지 데이터를 똑같은 방식으로 정렬하는 것이다.

 

• 최악 시간복잡도: O(n^2)
• 최선 시간복잡도: O(n^2)
• 평균 시간복잡도: O(n^2)
• 공간복잡도: O(1)

 

---

예시

다음의 배열을 오름차순으로 정렬한다.

• [ 11, 8, 1, 5, 20, 0 ]

배열에서 최솟값을 찾는다. 최솟값: 0

그리고 정렬되지 않은 배열의 첫 번째 값인 11과 위치를 바꾼다.

• [ 0, 8, 1, 5, 20, 11 ]

정렬되지 않은 나머지 데이터 중 최솟값을 찾는다. 최솟값: 1

정렬되지 않은 배열의 첫 번째 값인 8과 위치를 바꾼다.

• [ 0, 1, 8, 5, 20, 11 ]

위 작업을 배열의 끝까지 진행하면 정렬이 완료된다.

 

선택 정렬의 단계 (정렬을 완료한 데이터는 Bold)

• [ 0, 8, 1, 5, 20, 11 ] - 최솟값: 0
• [ 0, 1, 8, 5, 20, 11 ] - 최솟값: 1
• [ 0, 1, 5, 8, 20, 11 ] - 최솟값: 5
• [ 0, 1, 5, 8, 20, 11 ] - 최솟값: 8
• [ 0, 1, 5, 8, 11, 20 ] - 최솟값: 11 (정렬 완료)

+) 배열의 크기가 6이기 때문에 5개의 수만 정렬하면 나머지 1개의 수는 정렬할 필요가 없기 때문에 (배열의 크기 - 1) 만큼 회차를 진행하면 정렬이 완료된다.

 

---

코드

#include <iostream> 
using namespace std;

int a[10001];
int n, temp;
 
int main() 
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < n - 1; i++) 
    {
        int min = i;

        // 최솟값을 찾는 과정
        for (int j = i + 1; j < n; j++) 
        {
            if (a[min] > a[j])
            {
                min = j;
            }
        }

        // 최솟값을 정렬되지 않은 데이터의 첫 번째 위치의 데이터와 교체
        temp = a[i];
        a[i] = a[min];
        a[min] = temp;

        // 회차마다 배열을 출력
        cout << i + 1 << "회차: [ ";
        for (int k = 0; k < n; k++)
            cout << a[k] << " ";

        cout << "], 최솟값: " << a[i] << endl << endl;
    }

    cout << "정렬 후: [ ";
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";

    cout << "]" << endl;

    return 0;
}

 

+) 실행 결과