/**
 * Program name:Stable Sort
 * author:Xin Peng
 * date:2020/1/5
 * Pragram problem source: AOJ
*/
#include <iostream>
using namespace std;

#define MAX 36

typedef struct poker
{
    int value;
    char color;
} Poker;

/**
 * @brief Bubble Sort
 * @param data Original data
 * @param length Length of the data
*/
void BubbleSort(Poker data[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = length - 1; j > i; j--)
        {
            if (data[j].value < data[j - 1].value)
            {
                Poker tmp;
                tmp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = tmp;
            }
        }
    }
}

/**
 * @brief Bubble Sort
 * @param data Original data
 * @param length Length of the data
*/
void SelectionSort(Poker data[], int length)
{
    for (int i = 0; i < length; i++)
    {
        int position = i;
        for (int j = i + 1; j < length; j++)
        {
            if (data[j].value < data[position].value)
            {
                position = j;
            }
        }
        if (position != i)
        {
            Poker tmp = data[position];
            data[position] = data[i];
            data[i] = tmp;
        }
    }
}

/**
 * @brief Show the Poker array.
 * @param data Original data
 * @param length Length of the array
*/
void show(Poker data[], int length)
{
    for (int i = 0; i < length; i++)
    {
        cout << data[i].color << data[i].value;
        if (i != length - 1)
        {
            cout << " ";
        }
    }
    cout << endl;
}

/**
 * @brief Judge Stabality.
 * @param Ori Original data.
 * @param Res Resultful data
 * @param length Length of data
*/
bool judgeStable(Poker Ori[], Poker Res[], int length)
{
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = i + 1; j < length; j++)
        {
            if (Ori[i].value == Ori[j].value)
            {
                int priPosition = -1;
                int nextPosition = -1;

                for (int a = 0; a < 2; a++)
                {
                    for (int m = 0; m < length; m++)
                    {
                        if (a == 0 && (Res[m].value == Ori[i].value && Res[m].color == Ori[i].color))
                        {
                            priPosition = m;
                        }
                        else if (a != 0 && (Res[m].value == Ori[j].value && Res[m].color == Ori[j].color))
                        {
                            nextPosition = m;
                        }
                    }
                }
                if ((i - j) * (priPosition - nextPosition) < 0)
                {
                    return false;
                }
            }
        }
    }

    return true;
}

int main()
{
    int n;
    Poker R[MAX], N1[MAX], N2[MAX];

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        char tmp[2];
        cin >> tmp;
        R[i].color = tmp[0];
        R[i].value = tmp[1] - '0';

        N1[i].color = tmp[0];
        N1[i].value = tmp[1] - '0';

        N2[i].color = tmp[0];
        N2[i].value = tmp[1] - '0';
    }

    BubbleSort(N1, n);
    show(N1, n);
    cout << (judgeStable(R, N1, n) ? "Stable" : "Not stable") << endl;

    SelectionSort(N2, n);
    show(N2, n);
    cout << (judgeStable(R, N2, n) ? "Stable" : "Not stable") << endl;

    return 0;
}


Measured memory_bytes: 3092