第17講 並び替えその２＝最大値排除繰り返し法
第５話 最大値排除繰り返し法エンジン部分トレース
コードエンジン部分再掲
public static void g(int x[],int n){
int i,j,mx,w,jk=0;
for(i=0;i<n;i++){
mx=0;
for(j=i;j<n;j++){
if(mx<x[j]){
mx=x[j];
jk=j;
}
}
if(jk>i){
w=x[i];
x[i]=x[jk];
x[jk]=w;
}
}
}
２，８，５，１，１０
このデータでトレースをしてみましょう。
つまり、n=5の場合でトレースします。
１次元目ループの制御変数iは、
i=0、i=1、i=2、i=3、i=4
と動いていきます。
Ⅰ i=0のとき、
ⅰ j=0のとき、
mx=0,x[j]=x[0]=2ですから、mx<x[j]は真ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
が実行されて、mx=2、jk=0です。
jkは最大値のときのjを記録するための変数です。
２，８，５，１，１０
ⅱ j=1のとき、
mx=2,x[j]=x[1]=8ですから、mx<x[j]は真ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
が実行されて、mx=8、jk=1です。
２，８，５，１，１０
ⅲ j=2のとき、
mx=8,x[j]=x[2]=5ですから、mx<x[j]は偽ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
は実行されず、mx=8、jk=1のままです。
２，８，５，１，１０
ⅳ j=3のとき、
mx=8,x[j]=x[3]=1ですから、mx<x[j]は偽ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
は実行されず、mx=8、jk=1のままです。
２，８，５，１，１０
ⅴ j=4のとき、
mx=8,x[j]=x[4]=10ですから、mx<x[j]は真ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
は実行されて、mx=10、jk=4となります。
これでfor(j=i;j<n;j++)は終了となり、
if(jk>i){
w=x[i];
x[i]=x[jk];
x[jk]=w;
}
２，８，５，１，１０
jk=4、i=0なので、jk>iが真となりif文が実行されます。
w=x[0];
x[0]=x[4];
x[4]=w;
は
w=2;
x[0]=10;
x[4]=2;
ですのえで、データの交換が行われ
１０，８，５，１，２
Ⅱ i=1のとき、
for(i=0;i<n;i++){
mx=0;
でmx=0に戻されます。
そして、
for(j=i;j<n;j++){
ですからjは1から始まります。
１０，８，５，１，２ （色のついている数字がデータ対象群）
ⅰ j=1のとき、
mx=0,x[j]=x[1]=8ですから、mx<x[j]は真ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
が実行されて、mx=8、jk=1です。
１０，８，５，１，２
ⅱ j=2のとき、
mx=8,x[j]=x[2]=5ですから、mx<x[j]は偽ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
が実行されず、mx=8、jk=1のままです。
１０，８，５，１，２
ⅲ j=3のとき、
mx=8,x[j]=x[3]=1ですから、mx<x[j]は偽ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
は実行されず、mx=8、jk=1のままです。
１０，８，５，１，２
ⅳ j=4のとき、
mx=8,x[j]=x[4]=2ですから、mx<x[j]は偽ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
は実行されず、mx=8、jk=1のままです。
これでfor(j=i;j<n;j++)は終了となり、
if(jk>i){
w=x[i];
x[i]=x[jk];
x[jk]=w;
}
の登場ですが、i=1、jk=1でif文は実行されず、データは
１０，８，５，１，２のままです。
Ⅲ i=2のとき、
for(i=0;i<n;i++){
mx=0;
でmx=0に戻されます。
そして、
for(j=i;j<n;j++){
ですからjは2から始まります。
１０，８，５，１，２ （色のついている数字がデータ対象群）
ⅰ j=2のとき、
mx=0,x[j]=x[2]=5ですから、mx<x[j]は真ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
が実行されて、mx=5、jk=2です。
１０，８，５，１，２
ⅱ j=3のとき、
mx=5,x[j]=x[3]=1ですから、mx<x[j]は偽ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
が実行されず、mx=5、jk=2のままです。
１０，８，５，１，２
ⅲ j=4のとき、
mx=5,x[j]=x[4]=2ですから、mx<x[j]は偽ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
は実行されず、mx=5、jk=2のままです。
これでfor(j=i;j<n;j++)は終了となり、
if(jk>i){
w=x[i];
x[i]=x[jk];
x[jk]=w;
}
の登場ですが、i=1、jk=1でif文は実行されず、データは
１０，８，５，１，２のままです。
Ⅳ i=3のとき、
for(i=0;i<n;i++){
mx=0;
でmx=0に戻されます。
そして、
for(j=i;j<n;j++){
ですからjは3から始まります。
１０，８，５，１，２ （色のついている数字がデータ対象群）
ⅰ j=3のとき、
mx=0,x[j]=x[3]=1ですから、mx<x[j]は真ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
が実行されて、mx=1、jk=3です。
１０，８，５，１，２
ⅱ j=4のとき、
mx=1,x[j]=x[4]=2ですから、mx<x[j]は真ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
が実行されて、mx=2、jk=4となります。
これでfor(j=i;j<n;j++)は終了となり、
if(jk>i){
w=x[i];
x[i]=x[jk];
x[jk]=w;
}
の出番となり、i=3、jk=4でif文は実行されて、データは
１０，８，５，２，１となります。
Ⅳ i=4のとき、
for(i=0;i<n;i++){
mx=0;
でmx=0に戻されます。
そして、
for(j=i;j<n;j++){
ですからjは４から始まります。
１０，８，５，２，１ （色のついている数字がデータ対象群）
ⅰ j=4のとき、
mx=0,x[j]=x[4]=1ですから、mx<x[j]は真ですから
if(mx<x[j]){
mx=x[j];
jk=j;
}
が実行されて、mx=1、jk=4です。
１０，８，５，２，１
これでfor(j=i;j<n;j++)は終了となり、
if(jk>i){
w=x[i];
x[i]=x[jk];
x[jk]=w;
}
のステージに上がります。
w=x[4];
x[4]=x[4];
x[4]=w;
は意味がなく、データは
１０，８，５，２，１
のままですが、任務は遂行しています。
以上で長いトレースは終了です。
皆さんは、他のデータでもトレースを試してみてください。
トレース=コンピュータの動きを追うことはとても大切なことです。
さて、次の課題です。
public static void g(int x[],int n){
int i,j,mx,w,jk=0;
for(i=0;i<n;i++){
mx=0;
for(j=i;j<n;j++){
if(mx<x[j]){
mx=x[j];
jk=j;
}
}
if(jk>i){
w=x[i];
x[i]=x[jk];
x[jk]=w;
}
}
}
外側のループ、すなわち第1次元ループの方を自己再帰で実現してください。
第４話へ 第６話へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 入門 C++ 入門
基礎から応用まで第１部
初心者のための VC++による C言語 入門 C++ 入門
基礎から応用まで第２部
初心者のための
VC++による C言語 入門 C++ 入門 基礎から応用まで第３部
