アルゴリズムについて教えてください(1/2)

＃７です。
すみません。「元祖」バブルソートは、次のアルゴリズムです。
このほうがビールの泡に似ています。

ｉを１から１２まで繰り返す
－－ｉ番目とｉ＋１番目のカードを比べ前者が大きければ交換
上記を１ループとして、これを無限に繰り返す
１ループの中で交換が１回も行われなければ終了

＃７で紹介したものはバブルソートの変形です。正確な名前は知らないので、どなたか助け舟を。

投稿日時 - 2007-02-24 22:07:30

質問者さんは初心者とお見受けします。もし違ったらごめんなさい。
まず「バブルソート」を覚えてください。これは、コップの中の泡が次第に上がっていくようすを指します。

i を１から１２まで繰り返す
－－ｊをi+1から１３まで繰り返す
－－－－ｉ番目がｊ番目より大きければ入れ替える

で完成です。実際にダイヤ１３枚と、「ｉ」「ｊ」と書いた札を用意して、机の上でやってみましょう。あとはプログラミングですね。

ちょっと丸投げ質問の疑いもありますが、このあと自力でプログラミングができるなら、よしとしましょう。

投稿日時 - 2007-02-24 11:05:38

> トランプのダイヤのカードが１３枚、
これって別々のカードですか？　もし、そうならソートする必要なんかなくて、データを作ってしまえばいいんですけど。

そうでないなら、ソートすることになりますが、トランプのカードなら、値が限定されているのでビンソートが高速でしょうね。

投稿日時 - 2007-02-24 07:15:34

数分差で #4 さんに先に書かれちゃいました … (^^;

#4 さんのアルゴリズムはビンソート (バケットソートなどともいう) といい，
私の知る限り最速のソートアルゴリズムで，データ数 (この場合は13枚) に
比例する時間でソートできます．しかしキーが整数型以外の場合には
使いにくいせいか，あまり知られていないようです．

「ビンソート」で Google 検索
http://www.google.co.jp/search?sourceid=navclient-ff&ie=UTF-8&rls=GGGL,GGGL:2006-34,GGGL:ja&q=%22%E3%83%93%E3%83%B3%E3%82%BD%E3%83%BC%E3%83%88%22

ソート (Wikipedia)
http://ja.wikipedia.org/wiki/Category:%E3%82%BD%E3%83%BC%E3%83%88

投稿日時 - 2007-02-24 00:38:16

実際にトランプを番号順に並べたいときどうしますか，
いろいろな方法が思いつきますが，どれかひとつを子供でもできるように説明すれば，アルゴリズムになっているでしょう。
例えば，
(1)カードを置くスペースを13箇所確保し，左から１～13番とする。
(2)カードを１枚めくって，ランクがｋだったらｋ番目の位置に置く。
(3)(2)を13回繰り返す。

投稿日時 - 2007-02-24 00:26:29