JUNGOL 실력키우기 1146 : 선택정렬

선택 정렬(selection sort)이란 내부정렬 알고리즘의 하나로 다음 순서대로 실행하여 정렬을 한다.

1. 주어진 수열 중에 최소값(같은 값이 여러 개 있는 경우 처음 값)을 찾는다.
2. 찾은 최소값을 맨 앞의 값과 자리를 바꾼다.
3. 맨 앞의 값을 뺀 나머지 수열을 같은 방법으로 전체 개수-1번 반복 실행한다.

n개의 주어진 수열을 위와 같은 방법으로 정렬한다.

수열이 주어지면 선택정렬의 과정을 한 단계씩 출력한다.

 

첫줄에 수열의 길이 N(4≤N≤100)이 주어진다.
두 번째 줄에 N개의 0이상 100이하의 정수가 주어진다.

처음 상태를 제외하고 정렬과정의 각 단계별 결과를 "출력형식"과 같이 출력한다.

5 6 4 8 3 1

1 4 8 3 6 1 3 8 4 6 1 3 4 8 6 1 3 4 6 8

---

슬슬 자료구조 문제가 나오기 시작하는 것 같네요.

이 문제는 정렬에서 가장 기본적인 선택 정렬을 이용해 정렬하고 그 중간 결과를 포함한 결과를 출력하는 문제인데,

이 경우 입력되는 데이터의 순서도 제대로 맞춰야 하고 출력 결과의 개수가 정확해야 하는 이 두가지만 잘 기억하면 쉽게 해결할 수 있습니다.

저 같은 경우에는 출력 예를 잘못 읽어서 중간 출력 결과와 최종 출력 결과를 따로 출력했는데 그 덕에 한번 틀렸네요.

#include <iostream>
 
using namespace std;
 
void printArr(int *arr, int n);
 
int main()
{
    int n;
 
    cin >> n;
 
    // 데이터를 저장할 행렬 생성
    int *arr = new int[n];
 
    // 데이터 저장
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    // 마지막 인덱스는 마지막에 하나만 처리하게 되므로
    // 루프를 반복할 필요가 없다.
    for (int i = 0; i < n - 1; ++i)
    {
        // 최소값이 들어있는 인덱스 저장
        int min{ i };
 
        // 동일한 값을 계산할 필요가 없으므로
        // 최초 진행 인덱스에 1을 더해준다.
        for (int j = i + 1; j < n; ++j)
        {
            if (arr[min] > arr[j])
            {
                min = j;
            }
        }
 
        // 최소 인덱스의 값과 첫 인덱스의 값을 교환한다(오름차순).
        int temp{ arr[min] };
        arr[min] = arr[i];
        arr[i] = temp;
 
        // 결과를 출력한다.
        printArr(arr, n);
    }
 
    delete[] arr;
}
 
void printArr(int *arr, int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << arr[i] << ' ';
    }
    cout << endl;
}

JUNGOL) 문제은행) 실력키우기) 선택정렬