掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.29370

直接挿入法について
投稿者---mikito(2007/01/08 23:08:40)


友人に20個の整数データを直接挿入法で整列化する、以下Cプログラムを教えてもらったんですが、
#include<stdio.h>
#define size 20

main()
{
int i, j, temp, a[size];
for(i=; i<size; ++i)
scanf("%d", &a[i]);

for(i=; i<size; ++i){
for (j=i; j>0 && a[j-1] > a[j]; --j){
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}

printf(整列化の表示を作る)・・

}
   
三番目のfor文の
for (j=i; j>0 && a[j-1] > a[j]; --j)
の意味が良くわからず、友人に聞いたところ、
曖昧な言い方で良くわかりませんでした。
どなたか教えてください。


この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:直接挿入法について 29371 επιστημη 2007/01/08 23:54:14


No.29371

Re:直接挿入法について
投稿者---επιστημη(2007/01/08 23:54:14)
http://blogs.wankuma.com/episteme/


端から順に舐めてって、
「隣接する2要素が昇順になってなければ交換」
を繰り返してるだけ。

これのどこが直接挿入法なんでしょ?
どうみても出来の悪いバブル・ソートです。




この投稿にコメントする

削除パスワード

No.29372

Re:直接挿入法について
投稿者---mikito(2007/01/09 09:22:35)


すいませんでした。友人の言うことを
そのまま鵜呑みにしていました。





この投稿にコメントする

削除パスワード

No.29373

Re:直接挿入法について
投稿者---ありえないざ(2007/01/09 09:25:54)
http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88


http://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88
挿入ソートと同義だと思いますが、Wikipediaには同じ様なソースの記述があります。
これも出来の悪いバブル・ソートなのでしょうか?




この投稿にコメントする

削除パスワード

No.29374

Re:直接挿入法について
投稿者---ありえないざ(2007/01/09 10:35:46)


同じ様・・じゃありませんでした。。


この投稿にコメントする

削除パスワード

No.29470

Re:直接挿入法について
投稿者---へるぱ(2007/01/18 02:25:49)


これは、挿入ソートですね。
隣接する2要素を比較する範囲が、これまでに整列済みの範囲であ
ることに注目してみてください。
これまでに整列済みの範囲を順に調べていって、現在注目している
値よりも小さい(または大きい)値が見つかれば、その値に関して
はもうそれ以上調べなくてもいいよというのが挿入ソートの要点で
す。
整列済みのデータをこの方法で処理した場合、比較回数がデータの
数-1回だけで済み、他のどのソート法より高速に完了します。
むろんWikipediaにあるサンプルのようにして「swapのための手間
を減ら」したほうがよいのですが、このままでもバブルソートより
は優れた手順です。

#include <stdio.h>
#define SIZE 20
void trace(int*);

int main(){
    int i,j,tmp;
    int a[]={8,6,16,4,18,17,5,7,10,13,3,15,11,20,19,12,9,2,14,1};

    for(i=1;i<SIZE;i++){
        trace(a);   /* デバッグ用 */
        for(j=i;j>0&&a[j-1]>a[j];j--){
            tmp=a[j];
            a[j]=a[j-1];
            a[j-1]=tmp;
        }
    }

    trace(a);   /* デバッグ用 */
    return 0;
}

void trace(int a[]){
    int i;

    for(i=0;i<SIZE;i++)
        printf("%2d ",a[i]);
    printf("\n");
}




この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧