第16講 データの並び換えに挑戦！
第６話 隣項交換繰り返し法とは？
隣項交換繰り返し法とは、すべての隣項について、
隣項が昇順になっていないときに交換することを、
並び換えが成功するまで繰り返す方法です。
４，７，６，３，５
を例に具体的に説明します。
４，７，６，３，５
最初の隣項にスポットライトを当てます。
昇順でないときには交換しますが、
今回は昇順になっていますので、
何もしません。
４，７，６，３，５
次の隣項に焦点を当てます。
４，７，６，３，５
今回は昇順になっていないので交換します。
４，６，７，３，５
スポットライトは次に移ります。
４，６，７，３，５
今回も昇順になっていませんから交換します。
４，６，３，７，５
最後の隣項に焦点を移します。
４，６，３，７，５
今回も昇順になっていませんので、交換します。
４，６，３，５，７
残念ながら、グループ全体は昇順になっていません。
ですので、１巡目と同じことを繰り返します。
４，６，３，５，７
昇順になっていますので何もしません。
４，６，３，５，７
４，６，３，５，７
昇順になっていませんので交換します。
４，３，６，５，７
４，３，６，５，７
昇順になっていませんから交換します。
４，３，５，６，７
４，３，５，６，７
昇順ですから何もしません。
４，３，５，６，７
２巡目が終わりましたが、
残念がならまだ並び換えに成功していません。
３順目に入ります。
４，３，５，６，７
昇順ではありませんから交換します。
３，４，５，６，７
３，４，５，６，７
昇順ですから何もしません。
３，４，５，６，７
３，４，５，６，７
今回も昇順ですから何もしません。
３，４，５，６，７
３，４，５，６，７
昇順で何もしません。
３，４，５，６，７
これで３巡目が終了しました。
この時点で実は並び換えに成功していますが、
コンピュータは並び換えが成功したかどうかは、
判断できません。
４巡目を行い、交換が１回も発生しないことによって、
コンピュータは成功したことを判断することが出来ます。
私は、次の仮説を持っています。
ｎ個のデータは、
ｎ回以下の隣項繰り返し法で並び換えが終了できるというものです。
もちろん、本気になって考えれば数学的に証明できると思いますから、
定理に出来るでしょうが、
本格的に考えたことはありません。
でも、プログラムを組むことによって、
疑似証明は出来ます。
疑似を付けるのは、
プログラムによって、
１億個のデータ群についてｎ回以下で並び換えられたとしても、
数学の世界では証明であるとはいわないからです。
数学の証明は、
自然科学・社会科学・人文科学よりずっと厳格なのです。
では、皆さん隣項繰り返し法によって、
データの並び換えに挑戦して下さい。
２次元for文で可能ですよ。
よく考えて下さい。
おそらく私の仮説は間違っていないでしょうから、
データの個数を数えてその数をnとして、
for i=0 to n-1
と１次元目のfor文を組めば出来ます。
実行画面
10 18 17 13 3 16 17 3 3 15
データの最小値は18です。
データの最大値は0です。
小さい順に並び換え
3 3 3 17 13 10 16 17 18 15
大きい順に並び換え
18 17 17 16 15 13 10 3 3 3
基データの再表示
10 18 17 13 3 16 17 3 3 15
隣項交換繰り返し法による昇順並べ直し
3 3 3 10 13 15 16 17 17 18
隣項交換繰り返し法による降順並べ直し
18 17 17 16 15 13 10 3 3 3
プロジェクト終了
mainのまでのコード
#include<stdio.h>
#include<stdlib.h>
#include <time.h>
void f(int a[10]); //１桁のランダムデータを発生させる社員
char g(int a[10],int n); //データの１番小さい値を見つける社員
void h(int a[10]); //データ表示させる社員
char x(int a[10],int n); //データの1番大きい値を見つける社員
void j(int a[10]); //xを利用してデータを小さい順に並べ直す社員
void k(int a[10]); //gを利用してデータを大きい順に並べ直す社員
void cp(int a[10],int b[10]); //データのコピーを行う社員 aをbにコピー
void rs(int a[10]); //隣項交換繰り返し法による昇順並び換えを行う社員
void rk(int a[10]); //隣項交換繰り返し法による降順並び換えを行う社員
int main(){
int a[10],b[10],c[10],w;
srand((unsigned) time(NULL));
f(a); //１桁のランダムデータを発生させる社員
cp(a,b);
cp(a,c);
h(a);
w=g(a,0); //データの１番小さい値を見つける社員
printf("データの最小値は%dです。\n",a[w]);
w=x(a,10);
printf("データの最大値は%dです。\n",a[w]);
j(b); //xを利用してデータを小さい順に並べ直す社員
printf("小さい順に並び換え\n");
h(b);
k(c); //gを利用してデータを大きい順に並べ直す社員
printf("大きい順に並び換え\n");
h(c);
cp(a,b); //データの復元
cp(a,c); //データの復元
printf("基データの再表示\n");
h(a); //基データの表示
printf("隣項交換繰り返し法による昇順並べ直し\n");
rs(b); //隣項交換繰り返し法により、bを昇順に並べ直す。
h(b);
printf("隣項交換繰り返し法による降順並べ直し\n");
rk(c); //隣項交換繰り返し法により、cを降順に並べ直す。
h(c);
printf("プロジェクト終了\n");
}
では、皆さん完成させましょう。
初心者のための excel 2016 マクロ VBA 入門講義 基礎から応用まで
vc++ c言語 c++ 入門 初心者 基礎から応用まで
eclipse c++ 入門
魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
本サイトトップへ
