백준 #1015 수열 정렬

이번 문제는 정렬 문제입니다.  정렬은 알고리즘에서 가장 기초로 배우고 있지만, 속속들이 다 배우지는 않고 있습니다.

일반적으로 기본정렬에 속하는 선택정렬, 삽입정렬, 버블정렬과 고급정렬에 속하는 병합정렬, 퀵정렬, 힙정렬들을 배우고 있지만, 성능과 관련된 항목을 주로 가르치죠.

 

정렬에는 또 한가지 고려사항이 있는데, 입력된 데이터의 순서를 지켜주느냐 아니냐도 있습니다.  동일한 데이터가 있는 경우 순서를 지켜주는 정렬과 아닌 정렬이 있다는 것이죠.  사실 실제 프로그램 작성할 때에는 거의 무시할 수 있는 내용입니다만, C++ 기본 라이브러리에 stable sort가 있는 것으로 보아서 필요성은 있을거라고 봅니다.

 

문제는 다음 링크와 같습니다.

https://www.acmicpc.net/problem/1015

1015번: 수열 정렬

 

인덱스를 출력하는 것이라서 데이터 정렬을 하는 것이 아니고 인덱스 정렬을 해주어야 합니다.  그리고 여러개의 답이 있는 경우 사전순으로 앞서는 것을 출력해야 하므로, stable sort가 필요합니다.  정렬 방식 중 입력순서를 지켜주는 것은 기본정렬 3가지와 고급정렬에서는 병합정렬뿐입니다.  구현할 때 부등호에 = 가 들어가냐 아니냐에 따라서 달라질 수 있는데, 그것만 조심하면 동일 데이터의 입력순서를 지켜줍니다.

 

퀵정렬과 힙정렬은 알고리즘상 입력순서를 지켜줄 수가 없습니다.  퀵정렬에서는 피봇대치에 의해서 입력순서가 파괴되고요, 힙정렬은 말그대로 동일데이터의 위치가 어떻게 되냐에 따라서 입력순서가 지켜질 수 없습니다.

 

전, C++에서 기본 제공하는 것으로 구현하지 않고 삽입정렬을 이용해서 문제를 풀어보았습니다.

 

소스는 아래와 같습니다.  소스는 참고용으로만 봐주세요.

 

//----------------------------------------------------------------------------------------
//  baekjoon #1015 - Sorting numbers
//    - by Aubrey Choi
//    - created at 2019-05-23
//----------------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
    int p[50], a[50], n;
    scanf("%d", &n);
    for(int i=0; i<n; i++) scanf("%d", &a[i]), p[i] = i;
    for(int i = 1; i < n; i++)
    {
        int j = i;
        int v = p[i];
        while(j > 0 && a[p[j-1]] > a[v])
        {
            p[j] = p[j-1];
            j--;
        }
        p[j] = v;
    }
    for(int i = 0; i < n; i++) a[p[i]] = i;
    for(int i = 0; i < n; i++) printf("%d ", a[i]); putchar('\n');
}