#include<iostream>
#include<array>

const int items = 25;

int selection=0; //位置が確定している要素は0
int s=0; //サンプルを配列の0番目にする
int l=1; //レフトポインタを配列の1番目にする
int r=items-1; //itemsは配列の要素数(25に設定)　ライトポインタは、配列の一番最後―要素数-1番目にする

std::array<bool, items> checker;
std::array<int, items> number = {1,2,3,4,5,6,7,18,9,10,11,12,13,14,15,16,17,8,19,20,21,22,23,24,25};

void Sort();

int main()
{
        checker.fill(false);
	while (selection < items) {
		Sort();
		std::cout << "l:" << l << " r:" << r << " s:" << s << std::endl;
	}
	for (int i = 0; i < items; i++) {
		std::cout << number[i] << std::endl;
	}
	return 0;
}

void Sort(void)
{
    while(number[l]<number[s]){ //サンプルの値よりレフトポインタの値が小さいなら
        if(l!=r){ //もしライトポインタ場所が一致していないなら
            l++; //レフトポインタを右へ移動する
        }
        else{
            break; //もしぶつかってしまったら抜ける
        }
    }
    while(number[r]>number[s]){ //サンプルの値よりライトポインタの値が大きいなら
        if(r!=l){ //もしライトポインタと場所が一致していないなら
            r--; //ライトポインタを左へ移動する
        }
        else{
            break; //もしぶつかってしまったら抜ける
        }
    }
    if(l!=r){ //もしレフトポインタの場所とライトポインタの場所が一致していなかったら
        int tmp=number[l]; //レフトポインタの値とライトポインタの値を入れ替える
        number[l]=number[r];
        number[r]=tmp;
    }
    else{ //もし一致していたら
        if(number[s]<number[l]){ //大小関係を比較して、サンプルの値の方が小さいなら
            int tmp=number[s]; //サンプルの値と一致していた前の値とを入れ替える
            number[s]=number[l-1];
            number[l-1]=tmp;
            checker[l-1]=true;//サンプルの値を入れたところは場所確定
            selection++; //確定した場所が1つ増えた
        }
        else{ //もしサンプルの値の方が大きいなら
            int tmp=number[s];  //サンプルの値と一致したところの値とを入れ替える
            number[s]=number[l];
            number[l]=tmp;
            checker[l]=true;//サンプルの値を入れたところは場所確定
            selection++; //確定した場所が1つ増えた
        }
        bool check=true; //サンプルの場所を設定しているかどうかを記憶
        if(s==l || s==l-1){ //サンプルの場所とライトポインタの場所が一致しているか、サンプルの場所がライトポインタの手前なら
            check=false; //これから設定しに行く
            for(int n=s+1;n<items;n++){
                if(checker[n]==false){ //まだ場所が確定していない場所があったら
                    s=n; //サンプルの場所をそこに設定
                    check=true; //サンプルの場所を設定
                    break;
                }
            }
        }
        if(check==true){ //サンプルの場所が設定できていれば
            if(checker[s+1]==false){ //サンプルのとなりが空いていれば
                l=s+1; //レフトポインタをサンプルのとなりにする
            }
            else{ //空いていなければ
                l=s; //レフトポインタをサンプルのところにする
            }
            for(int n=items-1;n>=l;n--){ //ライトポインタの場所を設定しに行く
                if(checker[n]==false){ //配列の最後から確定していないところが見つかり次第
                    r=n; //ライトポインタをそこにする
                    break;
                }
            }
        }
    }
}