交換法のアルゴリズム

[ニート匿名]

　以下のプログラムは交換法を使って降順に並べるプログラムです。

具体的には、以下のようなアルゴリズムです。

①　添え字a[0]～a[4]から最大値をみつけて、a[0]と交換する。

②　添え字a[1]～a[4]から最大値をみつけて、a[1]と交換する。

③　添え字a[2]～a[4]から最大値をみつけて、a[2]と交換する。

④　添え字a[3]～a[4]から最大値をみつけて、a[3]と交換する。

⑤ a[4]が必然的にひとつに決まる。

#include <stdio.h> 

      int main (void)
      {
         int i,j,k,w;
         
         int a[5]={2,5,3,1,4};

         for(i=0;i<4;i++){
            
             k=i;/*交換する場所*/

         for(j=i+1;j<5;j++){

          if(a<a[j]){
 
     
               i=j;/*最大値の添え字の設定*/

                       }
                            }

            w=a; a=a[k];a[k]=w;　/*要素の交換*/

                             
                                    }


       return 0;
      }

このプログラムを応用して、次のような自分なりのアルゴリズムをプログラムとして実現したいのですが、どのようにプログラムにしたらよいか、紙や鉛筆を使ってトレースして何度も考えまくったのですが、なかなかいい方法がなさそうなのです。自分で考えたプログラムの途中を示します。

①　添え字a[0]～a[4]のなかの最大値を見つけたら、その要素を最後尾の要素（つまり、a[4]）と交換する。（これでa[4]の値が確定する）


②　添え字a[0]～a[3]のなかの最小値を見つけたら、その要素を先頭の要素（つまり、a[0]）と交換する。
（これで、a[0]の値が確定する。）

③　添え字a[1]～a[3]のなかの最大値を見つけたら、その要素をa[3]と交換する。
　（これで、a[3]の値が確定する。）

④　添え字a[1]～a[2]のなかから最小値を見つけたら、その要素をa[1]と交換する。

（これで、a[1]が確定し、a[2]は必然的に決まる。）

#include<stdio.h>

      int main(void)
{
  int i,j,k,l,saisho,saidai;

  int a[5]={2,5,3,1,4};

saisho=0;
saidai=0;
 for(i=4;i>0;i--){

                 k=i;
                 l=4-k;/*最大値と交換する要素の添え字*/

for(j=i-1;j>-1;j++){

if(a<a[j]){
i=j; saidai=a;
}

if(a>a[j]){

i=j;  saisho=a
}
......



return 0;
}

どのように改良すればよいのでしょうか。

どなたかご教授願います。

[たいちう]

> どのように改良すればよいのでしょうか。

改良という言葉は、現時点でも最低限のものができている場合に使います。
現時点のプログラムはコンパイルすらできないようですが、
もしも正常に動作するものができているならばそれを貼り付けてください。

【冒頭の問題？】
(1)　添え字a[0]～a[4]から最大値をみつけて、a[0]と交換する。

【途中の方針】
(1)　添え字a[0]～a[4]のなかの最大値を見つけたら、
その要素を最後尾の要素（つまり、a[4]）と交換する。（これでa[4]の値が確定する）

冒頭と途中とで逆になっています。
ソートが目的ならば逆でも構わないので、
逆だと言うことだけはしっかり意識しておいてください。


以下は正常に動作するものが出来上がっていないという前提での方針です。

全部をソートしようと思わずに、(1)だけ行うプログラムを作ってください。
その後に、必ず配列全部を表示して、意図したとおりの結果であることを
確認します。

これができたら、(1)の後に(2)を行い結果を表示するプログラム、
(1)～(3)を行い、、、と順に作成し、最後に(1)～(5)までを行うプログラムを作成します。
必要に応じて途中経過を表示すると、デバッグが楽です。

ここまでできたら、プログラムの「改良」という作業に入れます。
必要ならばその時に再度質問してください。

[ニート匿名]

　早速のご返信をありがとうございました。

たいちうさんのアドバイスどおりプログラムを逆からみていく（最後尾の要素と交換する）ものに直してみました。（1）だけできました。

 #include<stdio.h>

     int main(void){

         int i,j,k,w;
         
         int a[5]={2,5,3,1,4};


         for(i=4;i>0;i--){

                     k=i;

        for(j=i-1;j>-1;j--){

          if(a<a[j]){
                  i=j;
                       }

                            }

w=a; a=a[k]; a[k]=w;

}



            return 0;
                     }

[たいちう]

結果を表示していません。

[ニート匿名]

　そうですね。結果は1回目なので、
2 5 3 1 4から

2 4 3 1 5になっていました。

以下同様に2 4 3 1 5から　2 1 3 4 5

となっていました。

[たいちう]

結果を表示する機能をプログラムに追加してください、
という意味だったのですが、まぁいいや。

> 以下同様に2 4 3 1 5から　 2 1 3 4 5

これの意味がわかりません。
以下同様とは？
(1)から(5)まで全部やったつもりだけど1と2が逆のまま、ということですか？

やっぱり状況が分かりませんので、表示する機能を付けたプログラムを
貼り付けてください。そのプログラムがどこまでできているつもりかも
書いてください。
(1)までとか、(5)まで書いたつもりだけどバグあり、とか。
後者の場合は、(1)まで正しく動くプログラムもお願いします。

[ニート匿名]

　以下同様という書き方が不十分でした。

a[0]からa[4]までを見ていくと、a[1]が最大値なのでそれを最後の要素a[4]と交換　2 4 3 1 5

a[4]=5が確定したのでa[0]からa[3]までを見ていくと、a[1]が最大値なのでそれを要素a[3]と交換　2 1 3 4 5

a[3]=4が確定したのでa[0]からa[2]までを見ていくと、a[2]が最大値なのでそれを要素a[2]と交換　2 1 3 4 5
(ここでは、最初から最大値になっているので変化なし。)

a[2]=3が確定したのでa[0]からa[1]までを見ていくと、a[0]が最大値なのでそれを要素a[1]と交換　1 2 3 4 5

a[1]=2が確定したので残り１つは必然的に確定　　1 2 3 4 5
　

ということなのです。プログラムは正常に動いていますし、結果も正しくなっております。。

[たいちう]

> ということなのです。プログラムは正常に動いていますし、結果も正しくなっております。。

自力で作成できたようで何よりです。
それで、質問はまだありますか？
無いなら解決！マークをチェックしてください。

あるならば具体的に書いてください。
例えば改良したいならば、改良元のソースコードを。

保留ならば当面このままでも良いですが、数日中には解決か追加の質問かをお願いします。

[ニート匿名]

早速の返信をありがとうございます。私の実現したいアルゴリズムは以下の流れです。

①　添え字a[0]～a[4]のなかの最大値を見つけたら、その要素を最後尾の要素（つまり、a[4]）と交換する。（これでa[4]の値が確定する）
②　添え字a[0]～a[3]のなかの最小値を見つけたら、その要素を先頭の要素（つまり、a[0]）と交換する。（これで、a[0]の値が確定する。）
③　添え字a[1]～a[3]のなかの最大値を見つけたら、その要素をa[3]と交換する。　（これで、a[3]の値が確定する。）
④　添え字a[1]～a[2]のなかから最小値を見つけたら、その要素をa[1]と交換する。 （これで、a[1]が確定し、a[2]は必然的に決まる。）

やはり難しいでしょうか。

[たいちう]

# インターネットで丸付き数字等（環境依存文字）の使用は控えましょう。

(1)と(2)を同時に行うのですね。
どうせ最大値を探すのならば、最小値も一緒に探すことで、
配列を見る回数が半分になる、というコンセプトでいいですか？

別に難しいことは無いと思います。
まずは(1)と(2)の部分だけ作ってみてはいかがですか。


難しく感じるようでしたら、応用の前に基本をしっかり確認しておくという意味で、
普通のソートを改良するのが有効かもしれません。
No:53420やNo:53426を見る限りは、改良の余地がありそうです。
完成形が完璧なのかもしれませんが。

[ニート匿名]

早速のご返信をありがとうございます。質問の意味がわからない箇所がありました。
> (1)と(2)を同時に行うのですね。
> どうせ最大値を探すのならば、最小値も一緒に探すことで、
> 配列を見る回数が半分になる、というコンセプトでいいですか？
とありますが、配列を見る回数が半分になるとはどういうことでしょうか。

何度もすみません。ご返信をお願いします。

[たいちう]

> とありますが、配列を見る回数が半分になるとはどういうことでしょうか。

ニート匿名さんの意図を私が誤解したものですので、
回数が半分にならないのならばそれで結構です。

No:53435のままの仕様でしたら、普通のソートを変更して作りましょう。
奇数回目は最大を見つけて未確定範囲の最後に、
偶数回目は最小をみつけて未確定範囲の先頭に置き換えれば良いでしょう。

具体的な説明は、ソースコードを元にして行ったほうがわかり易いと思います。

[ニート匿名]

ご返信をありがとうございます。

今度はアルゴリズムを実現する以前の質問です。

for文の中に最大値と最小値両方を求めることは可能でしょうか。

最大値だけ、もしくは最小値だけを求めるということはできるのですが。

for(i=0;i<4;i++){

for(j=i+1;j<5;j++){

if(a<a[j]){

i=j;
}

else if(a>a[j]){
j=i;
}

上の場合、iがありえない値をとってしまい、間違っているということはわかるのですが。




ご返信をお願いします。

[たいちう]

> for文の中に最大値と最小値両方を求めることは可能でしょうか。

もちろん可能ですが、その前に普通のソートをちゃんと作りましょう。
下記の問題点は最初のプログラムからありました。


> 上の場合、iがありえない値をとってしまい、間違っているということはわかるのですが。

forの内側でループ変数に代入することはやめた方が良いでしょう。
文法的に間違いではないですが、バグの温床になりますよ。
最大値や最小値を保持するための変数を別に用意しておきましょう。

for(i=0;i<4;i++){  // この内側でiを変更してはいけない
    for(j=i+1;j<5;j++){ // この内側でjを変更してはいけない
        if(a<a[j]){
            i=j;             // i を 変更している！
        }
        else if(a>a[j]){
            j=i;             // j を 変更している！
        }
        ...
    }
}

[ニート匿名]

返事遅れて申し訳ありませんでした。例の質問は解決できました。
本当にありがとうございます。