C++で実装する初等的ソートアルゴリズム３【選択ソート】

初等的ソートアルゴリズム第3弾。今回は選択ソートです。

目標

選択ソートを理解することを目指します。例によって問題を解くことで理解を深めます。

選択ソート

計算量は $O(N^2)$ 。前方のソートずみ部分に、未ソート部分から小さい順に要素を選択して加えていくことで、ソート済み部分が後方へ拡大していくイメージです。

手順

ソートすべき数列の長さをNとする。

数列の全ての部分を未ソート部分とする。
以下をN-1回繰り返す：
1. 未ソート部分の最小要素を見つける。
2. 未ソート部分の先頭と最小要素を交換する。交換後の最小要素はソート済み部分に加わる。

問題を解いてみる

Aizu Online Judgeの問題を解きました。言語はC++です。
Selection Sort | Aizu Online Judge

#include<iostream>
using namespace std;

int main() {
  int i, j, N, min_j, tmp, change = 0;
  int seq[100];

  cin >> N;
  for (i = 0; i < N; i++) cin >> seq[i];

  // sort
  for (i = 0; i < N; i++) {  // iは未ソート部分の先頭
    // 未ソート部分の最小要素を見つける
    min_j = i;  
    for (j = i; j < N; j++) {
      if (seq[j] < seq[min_j]) {
        min_j = j;
      }
    }
    // 未ソート部分の先頭と最小要素を交換
    if (min_j != i) {
      tmp = seq[i];
      seq[i] = seq[min_j];
      seq[min_j] = tmp;
      change++;
    }
  }

  // output
  for (i = 0; i < N; i++) {
    if (i > 0) cout << " ";
    cout << seq[i];
  }
  cout << endl;
  cout << change << endl;

  return 0;
}