こんにちは。paizaラーニングでコンテンツ制作をしている学生スタッフの工藤です。
みなさん、ソートアルゴリズムは知っていますか？
ソートアルゴリズムは、もっとも基本的なアルゴリズムのひとつで、順序付け可能なデータの列を昇順または降順に並び替えるアルゴリズムです。
身近なところでは、氏名を五十音順に並べ替えたり、ファイルを新しい順に並び替える際などに活用されます。
今回は、paizaラーニングのレベルアップ問題集に追加された「素朴なソートアルゴリズムメニュー」を使ったソートアルゴリズムの学習法を紹介します。
「素朴なソートアルゴリズムメニュー」では、比較的シンプルで理解しやすい「選択ソート」「挿入ソート」「バブルソート」を取り扱っています。それらはソートアルゴリズムの基本となりますのでぜひマスターしましょう！
なぜソートアルゴリズムを学ぶのか
そもそも「ソート」とは
冒頭でも少し触れましたが、ソート（sort）とは、昇順・降順・アルファベット順・日付順などのルールにのっとって、数値や単語といったデータを並べることを言います。
たとえば、本棚の漫画がこんなふうになっていたら…
1巻 3巻 7巻 4巻 9巻 8巻 2巻 6巻 5巻
普通は1巻から順に数字が大きくなるよう並べ替えたくなりますよね。
1巻 2巻 3巻 4巻 5巻 6巻 7巻 8巻 9巻
何をしたかというと、1、2、3……と数字を見て入れ替えただけです。ものすごく単純な例ですが、これもソートのひとつです。
人間がソートされたデータを見たり扱ったりしやすいのと同様、コンピュータもバラバラのままのデータに対して何か処理をするよりは、ソートされたデータに対してのほうが効率よく処理ができます。
プログラミングに限らず、私たちは普段からいろいろなデータをソートして扱っています。
ソートアルゴリズムを学ぶメリット
次にプログラミングにおいて、ソートアルゴリズムを使うメリットは何かを少し考えてみましょう。
さきほどのように1～9巻までの漫画であれば、パッと見て判断できますし、ひとつひとつ並べ替えていってもそう大変ではありません。
しかし、膨大なデータ量を扱う場合はそういはいきません。
Wikipediaにはソートアルゴリズムごとの平均計算時間・最悪計算時間が記載されているのですが、採用するアルゴリズムによって並べ替えにかかる時間にかなり差があることが分かります。
（参考）ソート - Wikipedia
今回、問題集で扱うソートアルゴリズムはいずれも単純なもので、実はそれぞれもっと効率よく改良された別のソートアルゴリズムがあります。
ただ、それらを使いこなすためにもソートの基本を理解し、実装できるようになっておいて損はありません。これから問題を解きながらソートを理解していきましょう！
レベルアップ問題集とは
「素朴なソートアルゴリズムメニュー」は、レベルアップ問題集にて公開しています。
レベルアップ問題集とは、プログラミング学習における計算ドリルや漢字ドリルのようなものだと思ってください。
ドリルのようにプログラミング問題を解き進めながら、解答例となるコード（一部言語）や解説文も参照できる*1ため分からないことを理解したり、苦手なポイントを克服したりできるように作られています。
paizaが提供しているスキルチェックとは異なり時間制限がなく、問題文や自分の解答コードを公開することが認められていますので、誰かと協力して取り組むことも可能です。
練習問題集「素朴なソートアルゴリズムメニュー」
今回追加された素朴なソートアルゴリズムメニューでは、冒頭でも述べたとおりソートアルゴリズムのうち「選択ソート」「挿入ソート」「バブルソート」について学習することができます。
素朴なソートアルゴリズムメニューは、ソートアルゴリズムを知らない方や、ソートアルゴリズムは知っているけれど具体的にどのように実装すればよいか分からない方に取り組んでいただくことを想定して作成しています。
前提として、標準入出力や配列、if文やfor文などの基礎的な文法についてはひと通り理解している必要があります。
標準入力については、言語別で学習講座を公開していますのでこちらの一覧から取り組みたい言語を選択して受講してみてください。合わせてレベルアップ問題集の「標準入力メニュー」「標準出力メニュー」も解いておくとよいでしょう。
基礎文法が理解できているかどうかは、同じく問題集の「配列メニュー」「条件分岐メニュー」を解いて確認してみてください。
出題される問題の特徴
素朴なソートアルゴリズムメニューには以下の3つのプログラミング問題が用意されています。
なお、現在Python3、C++、Javaの解答コード例を用意しています。
前提知識：計算量とは
さきほども少し扱いましたが、以降でもソートアルゴリズムの計算量の話がところどころ出てきます。
計算量とは、簡単に言うと計算にかかるコストの指標です。計算量には空間計算量と時間計算量があります。時間計算量は、プログラムの処理時間を指します。処理が終了するまでに必要とする命令数はどのくらいかで見積もることができます。
時間計算量を表現する方法としてO記法（オーダー記法）というものがよく使われます。
計算量についてより詳しくは、以下の記事も参考にしてみてください。
1：挿入ソート
1つめの問題は「挿入ソート」です。
挿入ソートは、データ列を「整列済み」と「未整列」の2つに分け、「未整列な配列」からデータを1つ取り出し、「整列済み配列」の適切な位置に挿入することを繰り返す手法です。「未整列な配列」が空になるまで処理を繰り返すと、1つの「整列済み配列」が得られます。
この手法は、手持ちのトランプを並び替える際などによく用いられる比較的直感的なものです。
計算量で見るとそんなに効率のよい方法ではないのですが、単純かつ実装が容易なため利用されることも多いソートアルゴリズムです。
実際に挿入ソートの問題を少し見てみましょう。
問題文：
挿入ソート (昇順) は以下のようなアルゴリズムです。初期状態では A[0] ~ A[0] を「整列済み」、A[1] ~ A[n-1] を「未整列」とします。
insertion_sort(A : 配列, n : Aの要素数)
for i = 1 to n-1
// A[i] を、整列済みの A[0] ~ A[i-1] の適切な位置に挿入する
// 実装の都合上、A[i] の値が上書きされてしまうことがあるので、予め A[i] の値をコピーしておく
x <- A[i]
// A[i] の適切な挿入位置を表す変数 j を用意
j <- i-1
// A[i] の適切な挿入位置が見つかるまで、A[i] より大きい要素を1つずつ後ろにずらしていく
while j >= 0 AND A[j] > x
A[j+1] = A[j]
j--
// A[i] を挿入
A[j+1] <- x
// A[0] ~ A[i] が整列済みになった
挿入ソートの計算量を考えます。最も多くの計算ステップがかかるのは、while ループ中で値をずらす処理です。よって、この処理が最大で何回行われるかに注目し、計算量を導きます。各 i について、while ループ中で値をずらす処理は最大で i 回行われます。
つまり、最悪の場合この処理は全体で 1 + 2 + ... + n-1 = (n-1)*n/2 = (n^2-n)/2 回行われます。よって、挿入ソートは O(n^2) のアルゴリズムとなります。
挿入ソートは、入力される配列によって効率が変わるアルゴリズムです。例えば、入力される配列が予め昇順にソートされている場合は値をずらす処理が全く行われませんが、降順にソートされている場合は (n^2-n)/2 回行われます。
では、要素数 n の数列を昇順にソートする挿入ソートのプログラムを作成してください。上の疑似コードに従って実装してください。アルゴリズムが正しく実装されていることを確認するために、各 i についてその処理が終わった時点での配列を出力してください。
この問題は挿入ソートがどういったものかを理解した上で、問題文中にある擬似コードを参考にして実装をしてみるとよいでしょう。
2：選択ソート
2つめの問題は「選択ソート」です。
選択ソート（昇順）は、データ列を「整列済み」と「未整列」の2つに分け、「未整列な配列」の最小値を取り出し、「整列済み配列」の末尾に付け加えることを繰り返す手法です。「未整列な配列」の要素数が 1 になるまで処理を繰り返すと、1つの「整列済み配列」が得られます。
こちらも最悪計算量がO(n^2)と大きいのですが、直感的で実装が容易であることからよく利用されます。
ちなみに選択ソートのアルゴリズムを改良したソート法として、ヒープソートがあります。
3：バブルソート
3つめの問題は「バブルソート」です。
バブルソートは、データ列の隣り合う要素を比較し交換することを繰り返すことによりデータ列をソートする手法です。昇順に並べる場合は、常に右のほうがデータの値が大きくなるように並べ替えます。
バブルは「泡」という意味で、ソートの過程でデータが移動する様子が水中で泡が浮かんでいくように見えることからこの名前がついています。
こちらもやはり最悪計算量がO(n^2)と大きいのですが、実装が容易かつ並列処理に適しているためよく利用されます。
文章だけ見ても分かりづらいところもあると思いますので、ぜひ問題集の問題文と処理イメージの画像を参照して、実際にどのようにソートされるのか確認しながら理解を深めていきましょう。
まとめ
レベルアップ問題集に追加された「素朴なソートアルゴリズムメニュー」について紹介してきました。
本文にも記載したとおり、問題文の中で活用するアルゴリズムの解説をしています。また、掲載されている擬似コードを自分なりにアレンジすることで解ける形式の問題となっています。
そのため初めてアルゴリズムを学習する方にも、「以前勉強しようとしたけど挫折してしまった…」という方にもおすすめです。ぜひ、この問題集を使ってアルゴリズムの学習に挑戦してみてください。
プログラミングを始めたばかりで問題集の内容が難しいと感じた方は、まずは基礎文法からしっかり身につけるのもよいでしょう。
paizaラーニングでは、Python・PHP・Ruby・Java・C・C#・JavaScriptの7言語の入門講座を公開していますので、ぜひご活用ください。
練習問題をたくさん解いたあと、そろそろ自分のプログラミング力を腕試ししてみたい！という方は、時間制限ありのスキルチェックにもチャレンジしてみてください。
詳しくはこちら
*1:ただし、それらを閲覧するためには学習チケットが必要となります。チケットは毎日初回ログイン時に1枚付与され6枚まで所持できます。（有料会員の場合はチケットの消費なしで閲覧可能です）
