C言語関係掲示板

過去ログ

No.240.シェルソートと単純挿入ソート


No.1453

シェルソートと単純挿入ソート
投稿者---こー(2002/04/24 13:49:46)


シェルソートと単純挿入ソートについて勉強しています。
しかし、仕組みはわかったのですがこの二つの
実際の効率というか、速さの違いはどのくらいになるのでしょうか?
いろいろ考えて見たのですが、どうもよくわからなくて
書き込みさせて頂きました。

No.1462

Re:シェルソートと単純挿入ソート
投稿者---ともじ(2002/04/26 11:44:07)


こんにちは、返信遅くなりました。

>シェルソートと単純挿入ソートについて勉強しています。
>しかし、仕組みはわかったのですがこの二つの
>実際の効率というか、速さの違いはどのくらいになるのでしょうか?

シェルソートは基本挿入ソートの拡張で、基本挿入ソートが間隔1で
データを比較交換するのと同じやり方で、データ数nに対して間隔を
n/2 や n/4 … にしたものです。
データがある程度整列されている場合、基本挿入ソートでは隣り合った
データを比較するので交換が行われない無駄な比較が多くなり効率が
悪くなります。そのような場合、シェルソートは初めから離れたデータ
を比較しますので、無駄な比較が少なくなり、結果として基本挿入ソート
よりも高速にソートが行われます。

No.1470

Re:シェルソートと単純挿入ソート
投稿者--- 2児のオヤジ です。(2002/05/04 23:50:38)


アルゴリズム体験学習プログラム Ver.0.70

http://www.bohyoh.com/Algorithms/download.html

にソートの速度比較があります。

No.1475

Re:シェルソートと単純挿入ソート
投稿者---ともじ(2002/05/06 17:18:54)


こんにちは。よい連休をお過ごしですか。

よいプログラムをご紹介いただきありがとうございました。



戻る


「初心者のためのポイント学習C言語」 Last modified:2002.06.22
Copyright(c) 2000-2002 TOMOJI All Rights Reserved