T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS バブルソートについて

<<   作成日時 : 2016/01/15 00:01   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

やっと、コンピュータサイエンスとプログラミング入門(Part2)の一回目の授業:"09. Binary Search, Bubble and Selection Sorts(バイナリサーチ、バブルソート、選択ソート)"の最後の話題「バブルソート」を考えるところまで来ました。

まず、プログラムとテスト結果を示します。
画像

このアルゴリズムを \(test1\) の最初の出力が出てくるまでを図示してみました。
画像

しかし、このプログラムだと、ソートが終わっているのに、同じことをしている冗長性があります。
隣り合う \(pair\) 同士を比較して、全く交換が起こらない状況になれば、ソート終了にするように改善したものが、次のプログラムです。
画像

手数は、これだと \(O(n^{2}\) 程度ではないか?と思います。 \(n\log _{2}n\) のはもう少し後に出てくるようです。

今日はこの辺で。。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
バブルソートについて T_NAKAの阿房ブログ/BIGLOBEウェブリブログ
文字サイズ:       閉じる