T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS 選択ソートについて

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

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

まだ、コンピュータサイエンスとプログラミング入門(Part2)の一回目の授業:"09. Binary Search, Bubble and Selection Sorts(バイナリサーチ、バブルソート、選択ソート)"の話題が続きます。前回の「選択ソート」をもう少し突っ込んでみます。

ソート対象のリスト \([1,8,3,6,4]\) が並べ替えられていく過程を図示してみました。
画像


まず一番左の \(L[0]\) に注目して、右に順番に見ていって最低値を探します。
この場合は \(L[0]=1\) が最低値なので、自分自身と交換(ということは何も変わらない)します。

次は左から二番目 \(L[1]\) に注目して、(自分より)右に順番に見ていって最低値を探します。
この場合は \(L[2]=3\) が最低値なので、\(L[1]\) と \(L[2]\) を交換します。
この時点で、 \(L[0],L[1]\) は昇順に \(1,3\) と並ぶことになります。

この手順を注目する箇所を1つずつ右にずらしていって同様なことを行えば、ソートが完成することになります。

手数を考えると、リスト長を \(n\) とすると、最初は \(n-1\) の比較、次は \(n-2\) の比較、… なので、
\[
(n-1)+(n-2)+\cdots +1=\sum_{k=1}^{n-1}k= \frac{n\left ( n-1 \right )}{2}
\]
となり、\(O(n^{2})\) の程度ということになります。
前記事で述べた \(n\log _{2}n\) というのと少し異なるようですね。これはバブルソートということなのかと思いますが、それは後記事とさせていただきます。

今日はこの辺で。。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

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

トラックバック(0件)

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

トラックバック用URL help


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

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

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