第五の巻 整列の途中経過

中段 / 目安 25分

五つめの巻物を開きながら、師範が言います。「今度は、動かした結果だけを見せてもらっても困る。整列の途中で何が起きておるのか——1周ごとに何が確定するのかを、お前が説明できるかどうかじゃ」

題材は選択ソートです。第三の巻の泡の技とは、確定していく場所が違います。

選択ソートの1周は、こうです。まだ確定していない範囲の中から最小の値を探し、その範囲の先頭と入れ替える。 1周終えると先頭の1つが確定します。2周終えると先頭から2つ。3周終えると先頭から3つです。

師範が求めているのは、その3周目が終わった瞬間の並びです。並べ終えた姿ではありません。途中で止まった姿です。

完成条件

売上高の配列を受け取り、選択ソートを3周だけ回した時点の並びをカンマ区切りの文字列にして返す関数 selectionAfterThree を作ってください。どの言語で解く場合も、関数名は selectionAfterThree にしてください。

例えば 520,180,340,760,290,410,150,630 を受け取ったときの答えは、次のようになります。

先頭の3つ 150,180,290 は確定した最小の3つです。4つめより後ろは、入れ替えの跳ね返りで元の順序が崩れています。そこを「まだ並んでいない」ときちんと言えるかどうかが、この巻物の要です。

• 区切りは半角カンマ1つだけ。カンマの前後にスペースを入れないこと
• 入力の配列には必ず4つ以上の要素が入っています
• 3周より多く回してはいけません。並べ終えた結果を返すと不合格です

禁じ手

第三の巻と同じく、sorted sort Arrays.sort などの並べ替えの道具は使えません。

進め方

白紙から書いてください。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。1つも開けずに通せたら、その問題は自分のものです。

書き始める前に、例の並びを紙の上で3周ぶん手で追ってください。1周目に 150 がどこから来て、520 がどこへ行ったか。それが追えていれば、コードは短く済みます。

1. 関数名は selectionAfterThree。どの言語で解く場合も同じ名前にすること
2. 選択ソート（未確定の範囲から最小を探し、その範囲の先頭と入れ替える）で書くこと
3. 外側のループは3周だけ回すこと。最後まで並べ終えないこと
4. sorted / sort / Arrays.sort などの並べ替えの道具を使わないこと
5. 結果は半角カンマ区切りの文字列にすること。印字ではなく return で返す