アルゴリズム基礎1:swap(２値の交換)

今回はアルゴリズムを学んでいく際に一番最初に必要となる概念swapを学んでいこう。

テーマ

以下のように２つの変数に値が代入されている。

int a = 10;
int b = 20;

この２つの変数の中身を交換したい。つまり以下を実行したときに

System.out.println("a:" + a + ",b:" + b);

a:20,b:10
と出力させたい。
どうすればよいだろうか？

え、簡単じゃないの？

ひと目、とても簡単そうだ。

int a=10;
int b=20;
a=b;
b=a;
System.out.println("a:" + a + ",b:" + b);

しかし、これではうまくいかない。３行目でbに入っていた値をaに代入することは成功したが、この段階でもともとのaの値が消滅してしまい4行目の処理が意味がなくなってしまった。（aもbも20になってしまった）

解決策

int a=10;
int b=20;
int tmp = a;
a = b;
b = tmp;
System.out.println("a:" + a + ",b:" + b);

一つ値を保持しておく変数を用意するのがポイントだ、この場合の変数名はtmpやtempが使われるのが一般的だ(Temporary:一時的なという意味の英単語)。(tもたまに見かけるがtの使用はタイプ量を極力減らしたい場合などに限定したほうがよいだろう。)

なにかに役立つのかな・・・

ここまで来てこんなのなにかに役立つのかな・・・と思う感覚は実に自然だ。
しかし、これが実に様々なところで活用されるのだ。簡単な例を見ていこう

配列を逆順(reverse)する

[1,2,3,4,5]
例えば上のような配列を逆順にし
[5,4,3,2,1]
とする処理を考えてみよう。

考え方

以下のように先頭と一番後ろ、2番目と後ろから２番めを交換すれば良さそうだ。

もし、配列の要素が偶数だった場合交換は以下のようになる。

どうやら交換回数は

配列の要素数 を２で割った商

で求めることができそうだ。Javaはint/intは商を求める計算となるのでこの処理は以下のようになる。

答え

import java.util.Arrays;
public class Test {
	public static void main(String[] args) {
		int[] data = {1,2,3,4,5};
		for(int i=0;i<data.length/2;i++){
			int tmp = data[i];
			data[i] = data[data.length-1-i];
			data[data.length-1-i] = tmp;
		}
		System.out.println(Arrays.toString(data));
	}
}

冒頭にやった２値の交換を用いることで簡単に配列を逆順にすることに成功した。

まとめ

今回はアルゴリズムを学ぶ上での最初の一歩となる２値の交換(Swap)のやり方を学んだ。頻出の処理なのでしっかりと覚えてもらいたい。