第三の巻 バブルソート

初段 / 目安 20分

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

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

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

完成条件

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

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

180,290,340,410,520,760

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

禁じ手

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

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

進め方

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

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

1周と交換を追う

演習とは別の [4, 2, 3] で追います。最初の比較で [2, 4, 3]、次で [2, 3, 4] となり、末尾の 4 が確定します。次の周は先頭2つだけを比較します。外側の i が 0 のとき、内側の j は 0 から n - 2 までです。次の周は確定済みの末尾を除くので、条件は j < n - 1 - i です。Python は range(n - 1 - i) と書きます。二重ループは外側の1回ごとに内側の全体が動く仕組みです。

交換には元の値を一時変数で保存します。JavaScript と TypeScript の const は、再代入しない変数を宣言する書き方です。別の題材として、2枚のカードの位置を入れ替えます。最初に cards[0] = cards[1] だけを実行すると元の先頭の値が失われます。

Python

cards = [8, 2]
tmp = cards[0]
cards[0] = cards[1]
cards[1] = tmp

JavaScript

const cards = [8, 2];
const tmp = cards[0];
cards[0] = cards[1];
cards[1] = tmp;

TypeScript

const cards: number[] = [8, 2];
const tmp: number = cards[0];
cards[0] = cards[1];
cards[1] = tmp;

Java

int[] cards = {8, 2};
int tmp = cards[0];
cards[0] = cards[1];
cards[1] = tmp;

配列のコピー、長さ n、外側のループ、カンマ区切りの整形は完成済みです。内側のループと、隣同士が逆順のときの交換を書きます。同じ値では交換しません。

1. 関数名は bubbleSort。どの言語で解く場合も同じ名前にすること
2. 隣り合う2つを比べ、逆順なら入れ替える方法で並べること
3. sorted / sort / Arrays.sort などの並べ替えの道具を使わないこと
4. 結果は半角カンマ区切りの文字列にすること。カンマの前後にスペースを入れない
5. 印字ではなく return で文字列を返すこと
6. ひな形の補助処理と出力整形を使い、内側のループと隣同士の交換を書くこと
7. 入力配列は空ではないことが保証されます