/**
*AOJ_ALDS1_2_C Stable Sort
*ソートを行ったときに同じ値の要素間で入力順序が保存されていればStableSort
*/

#include <iostream>
#include <cstdlib>

#define ELEMENT_NUM_MAX 10
#define MAX 36
#define BUFSIZE 128
#define CARD_VAL_STR_SIZE 4

/**
*カードの情報を格納する構造体
*カードは一文字のアルファベットと1~9の数字からなる
*例)D5
*/
typedef struct Card
{
    char cCardType;     /*カードの種類(1文字):H,S,C,D*/
    int iCardVal;       /*カードの値(1~9)*/
    int iInputOrder;    /*入力順序*/
}Card;


/*関数のプロトタイプ宣言*/
int IntegerInputByGetline(void);
void CardReader(Card* ptCard);
void BubbleSort(Card* ptCard, int iEleNum);
void SelectionSort(Card* ptCard, int iEleNum);
void SwapCards(Card* ptCardX, Card* ptCardY);
void StabilityCheck(Card* ptCard, int iEleNum);
void DisplayCards(Card* ptCard, int iEleNum);
void CopyCards(Card* ptCard, Card* ptCopy, int EleNum);

/**
*関数名:Main
*機能:
*/

int main( void )
{
    Card atBufCard[MAX] = { {0} };
    Card atBufCardCopy[MAX] = { {0} };

    /*次のCardReaderでもgetlineを使用するので、改行、空白の取り扱いのためstd::cinではなくgetlineを使用*/
    int iEleNum = IntegerInputByGetline(); 
    
    CardReader(atBufCard);

    CopyCards(atBufCard, atBufCardCopy, iEleNum);

    BubbleSort(atBufCardCopy, iEleNum);

    CopyCards(atBufCard, atBufCardCopy, iEleNum);

    SelectionSort(atBufCardCopy, iEleNum);

    return 0;
}

/**
*関数名:IntegerInputByGetline
*機能:入力された文字列を整数に変換する
*/

int IntegerInputByGetline(void)
{
    char strNumBuffer[ELEMENT_NUM_MAX];
    std::cin.getline(strNumBuffer, ELEMENT_NUM_MAX);

    return std::atoi(strNumBuffer);
}

/**
*関数名:CardReader
*機能:入力された文字列をCard構造体配列に格納する
*入力例)C4 H5 D7(改行)
*/


void CardReader(Card* ptCard)
{
    char cBuffer[BUFSIZE] = { 0 };                      /*入力用バッファ*/
    char cBufCardVal[CARD_VAL_STR_SIZE] = { 0 };        /*数字用バッファ*/

    int i = 0, iBufPosition = 0, iInputOrder = 0;       /*各種カウンタ forループ用,数字列用,入力順序*/

    /*アルファベット、数字、半角スペースが連続するので、１文字ずつ処理するためにgetline()を使用*/
    std::cin.getline(cBuffer, BUFSIZE);            

    for (i = 0; i < BUFSIZE; i++)
    {
        if (cBuffer[i] == ' ' || cBuffer[i] == '\0')                    /*区切りまたは終端文字に到達したとき*/
        {
            cBufCardVal[iBufPosition] = '\0';                           /*数字列に終端文字付加*/
            (ptCard[iInputOrder]).iCardVal = std::atoi(cBufCardVal);    /*数字列を整数に変換してカードの値を格納*/
            (ptCard[iInputOrder]).iInputOrder = iInputOrder;            /*カードの入力順序格納*/

            if (cBuffer[i] == '\0')                                     /*終端文字だったら格納し終わった時点で終了*/
            {
                break;
            }

            iBufPosition = 0;                                           /*数字列バッファ再利用のためカウンタリセット*/
            iInputOrder++;
        }
        else if ('0' <= cBuffer[i] && cBuffer[i] <= '9')                /*数字列を文字列->整数変換用バッファに格納*/
        {
            cBufCardVal[iBufPosition] = cBuffer[i];
            iBufPosition++;
        }
        else
        {
            (ptCard[iInputOrder]).cCardType = cBuffer[i];                 /*アルファベットを格納*/
        }
    }
    return;
}

/**
*関数名:BubbleSort
*機能:Card構造体配列を要素iCardValに基づいてバブルソートする
*/


void BubbleSort(Card *ptCard, int iEleNum)                                        /*ptCardはSelectionSortでも使用するので念のためconst*/
{


    for (int i = 0; i < iEleNum; i++)
    {
        for (int j = iEleNum - 1; j > i; j--)                   /*配列の一番最後から*/
        {
            if ((ptCard[j]).iCardVal < (ptCard[j - 1]).iCardVal) /*昇順でなければ交換*/
            {
                SwapCards(&(ptCard[j]), &(ptCard[j - 1]));
            }
        }
    }

    DisplayCards(ptCard, iEleNum);

    StabilityCheck(ptCard, iEleNum);

    return;
}

/**
*関数名:SelectionSort
*機能:Card構造体配列を要素iCardValに基づいて選択ソートする
*/

void SelectionSort(Card* ptCard, int iEleNum)                           /*もうptCardは再ソートしないので、この関数内では直接ptCardを操作、保護しない*/
{
    for (int i = 0; i < iEleNum; i++)
    {
        int iMinSuffix = i;                                             /*最小値を示す添え字*/

        for (int j = i; j < iEleNum; j++)
        {
            if ((ptCard[j]).iCardVal < (ptCard[iMinSuffix]).iCardVal)   /*最小値を探す*/
            {
                iMinSuffix = j;
            }
        }

        SwapCards(&(ptCard[i]), &(ptCard[iMinSuffix]));                 /*i番目をi番目以降の最小値と交換*/
    }

    DisplayCards(ptCard, iEleNum);

    StabilityCheck(ptCard, iEleNum);

    return;
}

/**
*関数名:SwapCards
*機能:二つのCard構造体を交換する
*/

void SwapCards(Card* ptCardX, Card* ptCardY)
{
    Card tBuf;

    tBuf = *ptCardX;
    *ptCardX = *ptCardY;
    *ptCardY = tBuf;

    return;
}

/**
*関数名:StabilityCheck
*機能:ソートされた配列がStableかどうか判定する
*/

void StabilityCheck(Card* ptCard, int iEleNum)
{
    for (int i = 1; i < iEleNum; i++)
    {
        /*隣接する要素の値が等しいとき、入力順序を見てNot Stableか判定する*/
        if (!((ptCard[i]).iCardVal != (ptCard[i - 1]).iCardVal || (ptCard[i]).iInputOrder >= (ptCard[i - 1]).iInputOrder))
        {
            std::cout << "Not stable" << std::endl;
            return;
        }
    }
    std::cout << "Stable" << std::endl;     /*全要素を調べてNot StableでなければStable*/
    return;
}

/**
*関数名:DisplayCards
*機能:配列のType要素と値要素を一覧表示する
*/

void DisplayCards(Card* ptCard, int iEleNum)
{
    for (int i = 0; i < iEleNum; i++)
    {
        std::cout << (ptCard[i]).cCardType << (ptCard[i]).iCardVal; /*各要素表示*/

        if (i == iEleNum - 1)
        {
            std::cout << std::endl;
        }
        else
        {
            std::cout << ' ';  
        }
    }
    return;
}

/**
*関数名:CopyCards
*機能:構造体配列のコピー
*/

void CopyCards(Card* ptOrigin, Card* ptCopy, int iEleNum)
{
    for (int i = 0; i < iEleNum; i++)
    {
        ptCopy[i] = ptOrigin[i];
    }

    return;
}



Measured memory_bytes: 3136