[C/C++] BOJ #1015 Sorting Numbers

The problem BOJ #1015 - Sorting Numbers requires the following:

You are given an array  A  of size  N . Your task is to create a permutation  P  of length  N  such that:
1. Rearranged Order: When the elements of  A  are rearranged according to  P , they form a non-decreasing sequence. Specifically, if  B  is the rearranged array, then  B[i] = A[P[i]]  should hold, and  B  must be sorted in ascending order.
2. Stability in Indexing: If there are duplicate values in  A , their relative order in  P  must follow the stability of their positions in  A .  In other words, indices for equal values should be assigned in the order they appear in  A .

Input:
• An integer  N  (the size of the array  A ).
• A list of  N  integers  A .

Output:
• A list  P  of integers, where  P[i]  (0-indexed) represents the index of  A[i]  in the rearranged array  B, such that  B  is sorted in ascending order.

Constraints:
•. \( 1 \leq N \leq 50. )
•. The elements of  A  are integers.

 

This problem is about sorting, one of the most fundamental concepts in algorithms. While sorting is typically introduced early in learning algorithms, its nuances are not always fully explored.

Generally, we learn basic sorting algorithms such as selection sort, insertion sort, and bubble sort, as well as advanced algorithms like merge sort, quick sort, and heap sort. However, the focus is often on performance-related aspects rather than other considerations.

One additional aspect of sorting to consider is whether the original order of the input data is preserved. In the case of duplicate elements, some sorting algorithms maintain the relative order of these elements, while others do not. This property, known as stability, is usually overlooked in most programming scenarios. However, the fact that C++ includes a stable sort in its standard library suggests that it has its use cases and significance.

 

Since the task involves outputting indices rather than sorting the data itself, it requires index sorting. Additionally, when multiple valid solutions exist, the one that is lexicographically smallest must be output. Therefore, a stable sort is necessary. Among sorting algorithms, only the three basic sorting methods and merge sort from advanced algorithms preserve input order. This depends on whether the comparison uses a <= operator or not. As long as this is handled carefully, input order for duplicate data can be maintained.

Quick sort and heap sort, by their algorithmic nature, cannot preserve input order. In quick sort, pivot swapping disrupts the input order, and in heap sort, the position of identical data affects whether the input order is maintained.

Instead of using the standard library functions provided in C++, I chose to solve the problem using insertion sort.

 

sorting numbers

Here is the source code. Please note that it is for reference purposes only.

//----------------------------------------------------------
//    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');
}