第五の巻 整列の途中経過

中段 / 目安 25分

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

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

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

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

完成条件

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

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

150,180,290,760,340,410,520,630

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

• 区切りは半角カンマ1つだけ。カンマの前後にスペースを入れないこと
• 入力の配列には必ず4つ以上の要素が入っています
• 3周の時点の配列を返し、その後の整列を追加してはいけません。3周で全体が並ぶ入力や、最初から整列済みの入力もあります

禁じ手

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

進め方

ひな形の「課題」と書かれた部分から始めてください。初期化や補助処理は完成済みです。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。ヒントは必要に応じて使い、書いた処理を自分で追えることを目標にします。

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

値ではなく位置を覚える

minIndex は最小値そのものではなく、その値が入っている位置です。a[minIndex] で今の最小値を読みます。比較は厳密な < にして、同じ最小値が複数あれば先に見つけた位置を保ちます。ここが違うと未確定部分の並びも変わります。

別の題材として、一番高い棚の位置を探します。高さ [4, 9, 7] では、位置を 0 から始め、9 を見ると 1 に変わり、7 を見ても 1 のままです。

Python

heights = [4, 9, 7]
tallest = 0
for j in range(1, len(heights)):
    if heights[j] > heights[tallest]:
        tallest = j

JavaScript

const heights = [4, 9, 7];
let tallest = 0;
for (let j = 1; j < heights.length; j++) {
  if (heights[j] > heights[tallest]) {
    tallest = j;
  }
}

TypeScript

const heights: number[] = [4, 9, 7];
let tallest: number = 0;
for (let j = 1; j < heights.length; j++) {
  if (heights[j] > heights[tallest]) {
    tallest = j;
  }
}

Java

int[] heights = {4, 9, 7};
int tallest = 0;
for (int j = 1; j < heights.length; j++) {
    if (heights[j] > heights[tallest]) {
        tallest = j;
    }
}

演習では3周の外側ループ、交換、整形を渡しています。各周の i を初期候補にし、i + 1 から末尾まで調べる最小位置の探索を書きます。ひな形の仮の初期候補の行も、その処理の一部として残してください。

1. 関数名は selectionAfterThree。どの言語で解く場合も同じ名前にすること
2. 選択ソート（未確定の範囲から最小を探し、その範囲の先頭と入れ替える）で書くこと
3. 外側のループは3周だけ回すこと。その後の整列を追加しないこと
4. sorted / sort / Arrays.sort などの並べ替えの道具を使わないこと
5. 結果は半角カンマ区切りの文字列にすること。印字ではなく return で返す
6. ひな形の補助処理と出力整形を使い、未確定範囲の最小位置を探す処理を書くこと
7. 入力配列は4要素以上です
8. 同じ最小値が複数あるときは先に見つけた位置を使うこと（厳密な小なりで更新する）