008 - クイックソート

問題

データをある一定の法則に並び替えることをソートといい、データの小さい順に並び替えることを昇順ソートという。
昇順ソートを行うアルゴリズムはいろいろあるのだが、今回はその中の一つのクイックソートを実装する。
クイックソートは簡単に言うと以下のようにソートしていく。

1 適当な数（ピボットという）を選択する （この場合はデータの総数の中央値が望ましい）
2 ピボットより小さい数を前方、大きい数を後方に移動させる （分割）
3 二分割された各々のデータを、それぞれソートする

これを実現するためのアルゴリズムの一例が

1 ピボットとしてデータの位置が最も中央にある場所の値をPとする。最も中央にある場所の番地を求めるには(データの最も左の場所の番地+データの最も右の番地)/2で求まる。
2 左から順に値を調べ、P以上のものを見つけたらその位置をiとする。
3 右から順に値を調べ、P以下のものを見つけたらその位置をjとする。
4 iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う。
5 2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が1以下の領域ができた場合、その領域は確定とする。

整数のデータが与えられるので、これらを昇順クイックソートしてソートした結果を出力するプログラムを作ってほしい。

入力

まず１行目にデータの数n(1≦n≦100)が与えられる。
２行目から整数a_i(-1000≦a_i≦1000)が与えられる。

CHECK POINT

本番では以下の項目が採点基準となる。（うろ覚え)

• ・データの読み込みが出来ているか
• ・データがソートされているか
• ・クイックソートを用いてソートされているか
• ・再帰を用いて実装されているか
• ・結果を出力しているか

---

入出力例

入力例1

10
9
4
6
2
10
5
1
8
7
3

出力例1

1
2
3
4
5
6
7
8
9
10