[ 通常表示 ]  [ 簡易表示 ]  [ シンプル表示 ]

「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典イメージぴよ画像「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

隣接交換法

pointこの用語のポイント

point並べ替えのやり方だよ

point昇順 or 降順に並べたいときに使うよ

point隣り合う要素の大小比較を繰り返すことで、全体を並べ替えるよ

スポンサーリンク

簡単に書くよ

隣接交換法とは

「バブルソート」のこと。
つまり

データを昇順 or 降順に並べ替える際の、やり方のひとつ
であり

隣り合う要素の大小比較と並べ替えを繰り返すことで、全体を並べ替えるやり方
です。

image piyo

詳しく書くよ

※このページの説明は「バブルソート」の説明と、ほとんど同じです。既に「バブルソート」の説明をご覧になった方は、読んでもあまり意味は無いと思います。

データを小さい順(昇順)、もしくは大きい順(降順)に並べたいとしましょう。

いろいろなやり方があります。

その「いろいろなやり方」のひとつが「隣接交換法」です。
バブルソート」とも呼ばれます。

隣接交換法では隣り合う要素の大小比較と並べ替えを繰り返して、全体を並べ替えます……と言われても、ピンと来ないですよね。

実際の例を見ながら、説明していきます。

なお、先に理屈だけ書いておくと

1.1つ目の値と2つ目の値を比較する
2.1つ目が大きければ、左右を入れ替える
3.次に2つ目の値と3つ目の値を比較する
4.2つ目が大きければ、左右を入れ替える
5.同じことを3つ目以降も繰り返すと、最終的に1番大きな値が1番右側に来る
6.再度1から4の手順を繰り返す
7.2番目に大きな値が右から2番目に来る
8.再度1から4の手順を繰り返す
8.3番目に大きな値が右から3番目に来る
9.これを全要素が並ぶまで繰り返す


です。

文字だけで見ても、よく分からないと思います。
今の時点では理解できなくてOKです。
気が向いたら、最後まで読んだ後に見返してください。

それでは、見ていきましょう。

例えば、以下の4つの数字があったとします。
これを小さい順に並べ替えます。

3、2、1、4

隣接交換法では、まず一番左の値「3」に注目します。
仮に、これを「要素1」と呼びましょう。

隣接交換法

ついでなので、左から2番目の値「2」は「要素2」ということにします。
同様に左から3番目の値「1」は「要素3」です。
左から4番目、一番右の値「4」は「要素4」になります。

隣接交換法2

隣接交換法で最初にやるのは、要素1と要素2の比較です。

隣接交換法3

もし要素1の方が大きければ、要素2と左右を入れ替えます。
小さい順に並べる場合は、

常に右の方が大きくなるようにする

のです。
ちなみに、大きい順に並べるときは逆です。
右の方が小さくなるようにします。

さて、今回の例では、要素1は「3」です。
要素2は「2」です。
左の要素1の方が大きいですね。

隣接交換法4

右の方を大きくしたいので、要素1と要素2を入れ替えます。

隣接交換法5

次は、要素2と要素3の比較です。
要素2には、先ほど入れ替えた「3」が入っています。
要素3は「1」です。

隣接交換法6

また、左の要素2の方が大きいですね。
要素2と要素3を入れ替えます。

隣接交換法7

次に、要素3と要素4の比較です。
要素3には、先ほど入れ替えた「3」が入っています。
要素4は「4」です。

隣接交換法8

これは最初から右の方が大きいです。
要素の入れ替えは行いません。
そのままにしておきましょう。

隣接交換法9

次は要素4と要素5……は無いので、一旦、終了です。
この時点で、並びは以下のようになっています。

2、1、3、4

一番右側の要素が一番大きい値になっていますね。

隣接交換法10

小さい順に並べるということは、一番右側には一番大きな値が来ます。
実際に今、一番右側に一番大きな値が来ています。
ということは、一番右側は、これで確定としてしまって良いでしょう。

要素4の値は「4」で確定です。

隣接交換法11

次に、まだ確定していない要素

2、1、3

に対して、同じことをやります。

隣接交換法12

要素1は「2」です。
要素2は「1」です。
左の方が大きいので、入れ替えます。

隣接交換法13

入れ替えた後の要素2は「2」です。
要素3は「3」です。
右の方が大きいので、そのままにしておきます。

隣接交換法14

これで、残りの要素の中で一番大きい値「3」が(残りの要素の中で)一番右に来ました。

隣接交換法15

要素3の値は「3」で確定です。

隣接交換法16

次に、まだ確定していない要素

1、2

に対して、同じことをやります。

隣接交換法17

あぁ、これは何もしなくて大丈夫ですね。
この時点で、要素1の値は「1」で、要素2の値は「2」で確定します。

全体は

1、2、3、4

になりました。
ちゃんと、小さい順に並んでいます。

隣接交換法18

このような

隣接する要素の大小比較と入れ替えを繰り返すことで昇順(降順)に並べ替えるやり方

が、隣接交換法です。

カッコつけて言うと

値を昇順・降順で並べ替えるアルゴリズムのひとつ

ですかね。
アルゴリズムは「考え方」や「やり方」と解釈してください。

……というのが、隣接交換法の教科書的な説明です。
隣接交換法の説明を読むと、九割がた、似たような例が書いてあると思います。

説明が画一的になるのは、最終的な目的がプログラムを作ることだからです。

ぶっちゃけ、隣接交換法の処理の書き方って決まり文句みたいなものなのですね。
「隣接交換法 サンプル 【プログラミング言語の種類(Javaとか)】」を検索キーワードにしてGoogleとかYahoo!検索すれば、サンプルが腐るほど見つかります。

その処理を日本語に直したのが、ここまでに書いたような説明なのです。
隣接交換法の処理の書き方なんて、似たりよったりです。
そのため、隣接交換法自体の説明も似たりよったりになります。

とはいえ、そんな説明に対して「よく分からない」な人もいるでしょう。
そんな人に向けて、ちょっと目先を変えた説明も書いておきますね。

ただし、あくまでイメージを掴むための説明です。
実際のプログラムを作る際には、上に書いたような説明も頑張って理解してください。

それでは、始めます。

ある日のことです。
ピヨ太君が川で洗濯をしていると、上からミカン箱が流れてきました。

隣接交換法19

ピヨ太君はミカン箱を拾います。

なんと!
ミカン箱にはミカンが3個入っていました。

隣接交換法20

おっと、またミカン箱が流れてきました。
ピヨ太君は貧弱なので、2つは持って帰れません。
今持っているミカン箱か、流れてきたミカン箱か、どちらかを選ぶ必要があります。

隣接交換法21

上から覗き見たところ、流れてきたミカン箱には、ミカンが2個入っていました。
今持っているミカン箱の方が、ミカンがいっぱい入っています。

ピヨ太君は、流れてきたミカン箱をスルーしました。

隣接交換法22

おっと、またミカン箱が流れてきました。

隣接交換法23

上から覗き見たところ、流れてきたミカン箱には、ミカンが1個入っていました。
今持っているミカン箱の方が、ミカンがいっぱい入っています。

ピヨ太君は、流れてきたミカン箱をスルーしました。

隣接交換法24

おっと、またミカン箱が流れてきました。

隣接交換法25

上から覗き見たところ、流れてきたミカン箱には、ミカンが4個入っていました。
今持っているミカン箱よりも、ミカンがいっぱい入っています。

ピヨ太君は今持っているミカン箱を川に流し、流れてきたミカン箱を拾いました。

隣接交換法26

どうやらミカン箱は、もう流れてこないようです。
ピヨ太君は、ミカンが4個入ったミカン箱をお家に持って帰りました。

隣接交換法27

ピヨ太君は、欲ばりさんです。
残りのミカン箱も回収するために川に戻りました。

隣接交換法28

おっと、先ほどスルーしたミカン箱が流れてきたようです。
ミカンが2個入っています。

隣接交換法29

ピヨ太君は、ミカン箱を拾いました。

隣接交換法30

おっと、またミカン箱が流れてきました。
ミカンが1個入っています。

隣接交換法31

今、持っている方がいっぱい入っていますね。
スルーしましょう。

隣接交換法32

おっと、またミカン箱が流れてきました。
ミカンが3個入っています。

隣接交換法33

流れてきたミカン箱の方が、ミカンがいっぱい入っています。
ピヨ太君は今持っているミカン箱を川に流し、流れてきたミカン箱を拾いました。

隣接交換法34

ミカン箱は、もう流れてきません。
ピヨ太君は、ミカンが3個入ったミカン箱をお家に持って帰りました。

隣接交換法35

ピヨ太君は、欲ばりさんです。
残りのミカン箱も回収するために川に戻ります。

隣接交換法36

ミカン箱が流れてきました。
ミカンが1個入っています。

隣接交換法37

取りあえず、拾っておきましょう。

隣接交換法38

おっと、またミカン箱が流れてきました。
ミカンが2個入っています。

隣接交換法39

流れてきたミカン箱の方が、ミカンがいっぱい入っています。
ピヨ太君は今持っているミカン箱を川に流し、流れてきたミカン箱を拾いました。

隣接交換法40

ミカン箱は、もう流れてきません。
ピヨ太君は、ミカンが2個入ったミカン箱をお家に持って帰りました。

隣接交換法41

ピヨ太君は、欲ばりさんです。
残りのミカン箱も回収するために川に戻ります。

隣接交換法42

そして、ミカンが1個入ったミカン箱も回収してきました。

隣接交換法43

これでピヨ太君のお家には、ミカン箱が4つあります。
しかも、部屋の奥に行けば行くほど、たくさんのミカンが入ったミカン箱です。

隣接交換法44

部屋の手前から、小さい(ミカンが少ない)順に並んでいますよね?

これが隣接交換法のイメージです。

今持っている要素と後から来た要素を比較して、後から来た要素の方が大きければ、持ち替えます。
それを繰り返すと、すべての要素が通過した時点で、手元には一番大きな要素が残ります。
一番大きな要素を取り除いて、残った要素に対して同じ手順を行います。
繰り返すと、大きな要素から取り除かれていって、最終的に一番小さな要素が残ります。
取り除いた要素を逆に辿ると、小さい順に並んでいる理屈です。

実際のところ、マジメな説明も、ミカン箱の説明も、やっていることは同じです。

観測対象が固定で観測位置が移動すると解釈したのが、真面目な説明です。

隣接交換法45

観測位置が固定で観測対象が移動すると解釈すると、ミカン箱の説明になります。

隣接交換法46

最初は、イメージしやすい方で覚えてください。
どちらもイメージしにくい場合は……もっと説明の上手い人のところで勉強してください。けっ!

image piyo2

一言でまとめるよ

まぁ「隣接交換法」って単語が出てきたら「並べ替えのやり方なんだな~」と、お考えください。

一番上に戻るよ
スポンサーリンク