0380 - クイックソート

時間制限 1 秒 / メモリ制限 64 MB / 得点 5 / Writer ei1417 / x 25 / 統計 /


TLE
1sec
MLE
64MB
得点
5

問題

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

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以下の領域ができた場合、その領域は確定とする。

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

入力

まず1行目にデータの数n(1≦n≦100)が与えられる。
2行目から整数ai(-1000≦ai≦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