与えられたデータを一定の大小関係に基づいて並べ替えることをソートと呼ぶ. 「並べ替える」というと単純そうだが,ソートの手順(アルゴリズム)には様々なバリエーションが存在し,またこれらを学ぶ中で計算量(complexity)や再帰(recursion)といった重要な概念に触れることができるため,ソートは計算機科学のカリキュラムに必ず登場する基本的なトピックとなっている.

ここではもっともシンプルなソートアルゴリズムのひとつである選択ソート(selection sort)を実装しよう.

選択ソートは,次の手順で配列を並べ替えるアルゴリズムである.ただしここでは昇順(小さい方から順番に並べる)を想定している.

  1. 配列全体から,もっとも値の小さいデータを探し,配列の1番手前に移動する.
  2. 配列の残りのデータの中から,もっとも値の小さいデータ(全体で2番目に値の小さいデータ)を探し,配列の手前から2番目に移動する.
  3. 配列の残りのデータの中から,もっとも値の小さいデータ(全体で3番目に値の小さいデータ)を探し,配列の手前から3番目に移動する.
  4. 以下同様

問題

与えられた配列データを選択ソート(selection sort)により昇順に並べ替えるプログラムを作成せよ.また,「ふたつの数の比較」の回数を数えよ.

プログラムは以下の仕様を満たすこと(以下の仕様を満たしたプログラムに5点を加点する).

実行例

(1)

入力されるデータファイル (selectionsort_data1.txt) の例

4
1 2 3 4

リダイレクション ‘<’ を用いて selectionsort_data1.txt の内容を標準入力から読み込む.

$ ./a.out < selectionsort_data1.txt

selectionsort_data1.txt に対する実行結果の例(> は標準出力を示し, は半角スペースを示す.)

> 1⊔2⊔3⊔4
> 6

(2)

入力されるデータファイル (selectionsort_data2.txt) の例

5
7 1 3 4 5

selectionsort_data2.txt に対する実行結果の例(> は標準出力を示し, は半角スペースを示す.)

> SWAP(0,1)
> #⊔1⊔7⊔3⊔4⊔5
> SWAP(1,2)
> #⊔1⊔3⊔7⊔4⊔5
> SWAP(2,3)
> #⊔1⊔3⊔4⊔7⊔5
> SWAP(3,4)
> #⊔1⊔3⊔4⊔5⊔7
> 1⊔3⊔4⊔5⊔7
> 10

(3)

入力されるデータファイル (selectionsort_data3.txt) の例

8
2 4 3 1 8 7 6 5

selectionsort_data3.txt に対する実行結果の例(> は標準出力を示し, は半角スペースを示す.)

> SWAP(0,3)
> #⊔1⊔4⊔3⊔2⊔8⊔7⊔6⊔5
> SWAP(1,3)
> #⊔1⊔2⊔3⊔4⊔8⊔7⊔6⊔5
> SWAP(4,7)
> #⊔1⊔2⊔3⊔4⊔5⊔7⊔6⊔8
> SWAP(5,6)
> #⊔1⊔2⊔3⊔4⊔5⊔6⊔7⊔8
> 1⊔2⊔3⊔4⊔5⊔6⊔7⊔8
> 28