交換のアルゴリズム | Programming Place Plus　アルゴリズムとデータ構造編【その他のアルゴリズム】　第１章

この章の概要

この章の概要です。

• 値の交換
• 一時変数を使う
• XOR演算を使う
• 部品化
• まとめ
• 練習問題
• 参考リンク
• 更新履歴

値の交換

この章では、アルゴリズムのごく簡単な例として、２つの変数に格納された値を交換する方法を取り上げます。いわば、交換のアルゴリズムです。

実際のプログラミングでは、値の交換はいたるところで行われます。単純に２つの変数の値を入れ替えたいというケースだけでなく、整列アルゴリズムの多くは、整列の過程の中で、頻繁に交換を行っています。

また、配列を逆順になるように反転させる操作も、先頭と末尾、先頭+1 と末尾-1 … といったように、２つの要素を交換していく操作を繰り返すことで実現できます（Ｃ言語編　逆引き）。

このように、非常によく使われる操作ですから、効率的な形で部品化しておくことも考えておきたいところです。その点についても取り上げます。

一時変数を使う

まず、初心者にありがちなミスを取り上げておきます。

#include <stdio.h>

int main(void)
{
    int a = 10;
    int b = 20;

    // 変数a と b の値を交換している？
    a = b;
    b = a;

    printf( "%d %d\n", a, b );

    return 0;
}

実行結果：

20 20

変数a と b の初期値はそれぞれ、10 と 20 ですから、正しく交換できていれば出力結果は「20 10」となるはずですが、そうなっていません。この実装には間違いがあるということです。

a = b;
b = a;

という実装は、ぱっと見では確かに交換しているように見えるかもしれませんが、それは、この２つの文が「同時に」実行されるように考えてしまっているからです。実際には、この２つの文は「１つずつ」実行されるのですから、最初の a = b; が実行された後の時点で、変数a と b は両方とも 20 になってしまいます。

何が起こっているか詳しく書くと、次の表のようになります。上から順番に時系列になっていると考えてください。

結局、問題なのは「a = b;」の実行後には、変数a の元の値である 10 が失われてしまう点にあります。10 がどこにもない状態になってしまうのですから、最終的に変数 b の値が 10 にならないのは当然といえば当然です。

そこで、変数a の 10 をいったん、どこかに退避させてしまおうという考えが浮かびます。そのように書き換えると、次のようになります。

#include <stdio.h>

int main(void)
{
    int a = 10;
    int b = 20;
    int tmp;

    // 変数a と b の値を交換している
    tmp = a;
    a = b;
    b = tmp;

    printf( "%d %d\n", a, b );

    return 0;
}

実行結果：

20 10

実行結果を見る限り、今度は正しく交換できているようです。今度は何が起きているのか、先ほどのように表にまとめてみます。

今度は「a = b;」の実行後の時点で、変数a の元の値 10 が、変数tmp に保存されていますから、これを使えば、変数b を 10 にできます。

このように、別の変数にいったん、値を退避させておけば、値の交換が実現できます。このとき、変数tmp のような作業用に使われる変数を、一般に一時変数とか作業用変数などと呼びます。

my $x = 10;
my $y = 20;

# 変数x と y の値を交換している
($y, $x) = ($x, $y);

20 10

XOR演算を使う

もう１つ、別の手法を紹介しておきましょう。今度は、ビット単位の XOR演算を利用します（Ｃ言語編第４９章参照）。

XOR演算は、ビット同士を比較したとき、いずれか一方だけが 1 のときに結果が 1 になるビット演算です。

XOR演算には、２回繰り返すと、元のビット列に戻るという特性があります。この特性をうまく利用すると、値の交換が実現できます。ただし、この方法は、ビット演算を利用しているため、整数の交換でしか使えません（Ｃ言語編第４９章参照）。

#include <stdio.h>

int main(void)
{
    int a = 10;
    int b = 20;

    // 変数a と b の値を交換している
    a ^= b;
    b ^= a;
    a ^= b;

    printf( "%d %d\n", a, b );

    return 0;
}

実行結果：

20 10

変数の値の変化を確認してみましょう。( ) の中の数値は 2進数に変換したものです。

これだけだと原理がよく分からないと思います。次のように、各過程での結果ではなく、各過程で適用されている式を書き出してみると原理が見えてきます。

XOR演算を２回適用すると元の値に戻るということは、「(a ^ b) ^ b == a」だということです。したがって、b ^= a; 実行後 という行の変数b の式 b ^ (a ^ b) は結局のところ、a に置き換えられるということです。

同様に、一番下の行の変数a の式 (a ^ b) ^ (b ^ (a ^ b)) は、(a ^ b) ^ a となります。これはさらに進めて b にまで置き換えられます。

このように式を縮めた状態で表記すれば、次のようになります。

ということで、一番下の行の結果を見ると、確かに変数a と b の値は入れ替わっています。

なお、この方法は、a と b が同じ変数の場合には、結果がともに 0 になってしまい、うまくいきません。同じ変数のときには、そもそも交換処理を行わないようにする必要があります。

この手法は、一時変数を必要としないため、メモリにアクセスする回数を減らす効果があり、効率が良い可能性があります。実際にはさまざまな要因が絡むため、どちらの方法が高速かは、実測してみるしかありません（【導入】第２章）。

部品化

では、交換のアルゴリズムを部品のようにまとめておいて、手軽に使えるようにしてみましょう。

Ｃ言語で関数化すると次のようになります。

#include <stdio.h>

inline void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int main(void)
{
    int a = 10;
    int b = 20;

    swap( &a, &b );

    printf( "%d %d\n", a, b );

    return 0;
}

実行結果：

20 10

引数a と b はポインタ変数（Ｃ言語編第３１章参照）でなければなりません。

ポインタ変数である以上、ヌルポインタが渡される可能性がありますから、厳密にはそのチェックが必要です。しかし、呼び出し回数が非常に多くなることが想像される関数ですし、使い方を考えると誤ってヌルポインタを渡す可能性はかなり低いでしょう。そういう意味で、あまりヌルポインタかどうかのチェックしているものは見かけません。

これはＣ言語での事情ですが、int型などの特定の型に依存してしまうため、「double型の値を交換したい」という要望があれば、別の関数が必要です。

あるいは関数形式マクロ（Ｃ言語編第２８章参照）を使うことも考えられます。

#define SWAP(type, a, b)  do { type work = a; \
                               a = b;         \
                               b = work; } while(0)

この SWAPマクロの実装については、Ｃ言語編第２８章の練習問題で詳説しています。

template <typename T>
inline void swap(T* a, T* b)
{
    T tmp = *a;
    *a = *b;
    *b = tmp;
}

int a, b;
double c, d;

swap( &a, &b );  // 自動的に T は int型と判断
swap( &c, &d );  // 自動的に T は double型と判断
swap<int>( &a, &b );    // 明示的に T に int型を指定
swap<double>( &c, &d ); // 明示的に T に int型を指定

まとめ

変数の値を交換する方法について、代表的な２つのアルゴリズムを取り上げました。効率面でどちらが優れているかは、プログラムを実行する環境によって変わってきますから、効率を求めるのなら実測に基づいて判断する必要があります。

ただし、プログラミング言語によっては、値の交換の処理は標準機能として用意していることもあるので、その場合はそれを優先して使うといいでしょう。