第三の巻 バブルソート

初段 / 目安 20分

三つめの巻物です。師範が広げると、そこには売上の数字がばらばらの順で並んでいました。「売上を小さい順に並べよ。隣同士を比べ、逆なら入れ替える——古より伝わる泡の技で」

泡の技、つまりバブルソートです。名前の由来は、大きい値が水中の泡のように末尾へ浮かんでいく（あるいは沈んでいく）ように見えるところにあります。速い並べ替えではありません。それでも師範がこれを最初に指すのは、並べ替えという仕事の骨格が、この技にいちばん素直に出ているからです。

並べ替えの関数は、どの言語にも最初から入っています。第一の巻と同じく、ここではそれを使いません。

完成条件

売上高の配列を受け取り、小さい順に並べ替えた結果をカンマ区切りの文字列にして返す関数 bubbleSort を作ってください。どの言語で解く場合も、関数名は bubbleSort にしてください。

返す文字列の形は次のとおりです。

• 区切りは半角カンマ1つだけ。カンマの前後にスペースを入れないこと
• 末尾にカンマを付けないこと
• 同じ値が複数あってもかまいません。そのまま並べてください
• 配列には必ず1つ以上の要素が入っています

禁じ手

次の道具は使えません。隣同士の比較と入れ替えだけで並べてください。

• Python の sorted list.sort
• JavaScript / TypeScript の Array.prototype.sort
• Java の Arrays.sort

進め方

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

書き始める前に、紙の上で [3, 1, 2] を1周だけ回してみてください。1周が終わったとき、どの位置の値がもう動かないと言い切れるでしょうか。そこが分かると、外側のループを何回回せばよいかも自分で決められます。

1. 関数名は bubbleSort。どの言語で解く場合も同じ名前にすること
2. 隣り合う2つを比べ、逆順なら入れ替える方法で並べること
3. sorted / sort / Arrays.sort などの並べ替えの道具を使わないこと
4. 結果は半角カンマ区切りの文字列にすること。カンマの前後にスペースを入れない
5. 印字ではなく return で文字列を返すこと