So-net無料ブログ作成

並べる [味村ノート]

pncl_02.jpg ワープロを使うようになって,鉛筆で書くことが減った。 
そのせいか、半分使い古しの鉛筆が溜まっている。暇つぶしに長いものから並べながら、思いつくことを書いてみた。コンビュータ屋流にいえば、鉛筆をその属性の一つである[長さ]をキーに整列することの一考察とでもなろうか。

選んで並べる     整列手順例は→こちら
 まず、鉛筆を一列に置く。先頭を2本目から末尾まで順に比べ,相手が長ければ場所を入れ換える。同じことを、2本目は3本目から、3本目は4本目から比べ、というように末尾の1本までやると、鉛筆の長さの降順に配列できる。未整列の中から、最長のものを選んで、次々に並べていくわけだ。

 比べる手数は、はじめ全数より1だけ少ない回数だが,どんどん減っていく、しかし、全部の手数は、鉛筆の本数を n として n2 に比例する。そこで、この方法は2乗時間だと呼ばれる。入れ換える手数も同様になる。整列アルゴリズムでは[挿入ソート]と呼ばれる。

探して並べる     整列手順例は→こちら  
 ある鉛筆に着目し、これと先頭よりの隣とを比べて相手より長ければ入れ換えることを先頭に向かって進める。隣が長くなったら止めて、いま着目した次の鉛筆で同じことをやる。これを2本目から末尾まで順にやれば、降順に整列できる。整列済みの中に並ぶべき境所を探して、そこへ入れていくわけだ。

 比べる手数は、はじめ1回だが、どんどん増える.毎度先頭まで比べるとは限らないが、平均でその半分くらいにはなろう。手数の合計はやはり n2 に比例するから、これも2乗時間だ。入れ換える手数も同様になる。鉛筆を縦に並べてやると、長さに応じた場所まで泡の立つように鉛筆が昇っていくから,[泡立ち整列(バブルソート)]という。

交ぜて並べる     整列手順例は→こちら  
 鉛筆を幾つか群に分割する。必要に応じて鉛筆の長さを比較しやすい小さい群(最小は要素数1)までさらに分割する。分割後の併合(マージ)は対応する分割列を先頭から比べ,長い方から新しい第3の配列に置く。どちらか一方の分割列が全て終わると,他方の分割列の残りはそのまま第3の配列の後に並べる。次の対応分割列も同様にして、新しい第4の配列を作る。これを繰り返し、一つの降順に整列した配列に併合する。

 [2ウェイ・マージ]と呼ばれる方法だ。比べる手数も入れ換える手数も n log2 n に比例する。筆書は,答案を学生番号順に揃えるときなどに重宝している。

分けて並べる     整列手順例は→こちら 
先頭から順に,末尾と比べて短い鉛筆がある場所を探す。次に,末尾の一つ手前からから逆順に、末尾と比べて長い鉛筆がある場所を探す。両場所の鉛筆を入れ換えて、さらに両方向に進める。ぷつかった所で先頭から探した短い鉛筆と末尾と入れ換える。そうすると、そこに置いた鉛筆より長いものが先頭からそこまでに、また短いものがそこから末尾までに、それぞれ分けられたことになる。同じことを、そこを除いた前半分と後半分とについてやる。こむつかしくいうと、再帰的に実行する。ついには、分けた部分の鉛筆がただ1本ずつになり降順に整列できる。

 [区分化整列]とか[クイックソート]と呼ばれるが,気の利いたプログラミングの本などでちょくちょく出会うものだ。比べる手数は n log2 n に比例し、入れ換える手数はこれより少なくて済むという。

エイヤッと並べる     整列手順例は→こちら 
最後に、いささか変わった方法を紹介する。
鉛筆の束を片手でゆる目に握り、これを机の上に真直にエイヤッと立てる。一番背の高いものから順に抜きとって並べる。束がなくなるまでやって,降順の整列が完了だ。配列の最小値(最大値)を持つ要素を探してそれを配列の先頭要素と交換することで整列を行う[選択ソート]のアルゴリズムの一種だろう。

 比べる手数はエイヤッの1回、並べる手数は n に比例するから、この方法は線形時間ということになる。前出の2乗時間はいうに及ばず、n log2 n と比べても格段に差がある。こういうものを「ツポにはまった小道具」つまり「ガジェット(gad-get)」というのだそうだ。

 ついでに、平行でない2本のレールの狭い方を高く広い方を低く置く。鉛筆を上から転がせば、長さがレールの間隔に等しくなった所で鉛筆は落ちる。レールの下には、鉛筆が自然に整列する。アメリカで,オレンジの選別に実用しているという。

   本稿は次の文献を参考にした
   遊びの発想 別冊サイエンス82(1987)  A.K.デュードニー著,山崎秀記監修
  
[目]

[ソート]機能は日常に利用していますが、その[アルゴリズム]を意識してみるとなかなか面白いものがあります。今回この[味村ノート_並べる]をアップするに当たって、私や周りもずいぶん楽しみました。[ソート]の手順を考えることは、中学生、場合によっては小学生から学生、大人まで[アルゴリズム]を理解するによい材料だと感じます。
[アルゴリズム]は数学やコンピュータでの[算法]のみならず、その概念は[問題解決]のための[手順][やり方][技法]として、いろいろな分野・シーンで参考になりますね。

整列手順例
  上記本文にほぼ対応した[整列手順例]を付加しました。→こちら
アニメーション
  本文の手順方式には沿っていませんが、
  実に愉快な動画コンテンツがありましたので、併せてご紹介します。
  日本語のコンテンツがあまり見当たらず寂しいのですが・・・。
  
  
  
◇ ソートダンス
楽しみながらよく理解できそうなコンテンツです。
教材により理解の難易度が変わることを教えてくれます。制作はいずれも、
  Sapientia University, Tirgu Mures (Marosvásárhely), Romania

○ 挿入ソート
整列済み最小配列を作成し、他の要素を適切な位置に挿入して並び替えます。
 Insert-sort with Romanian folk dance
  http://www.youtube.com/watch?v=ROalU379l3U&feature=related
○ バブルソート
基点となる要素とそれ以外の要素の値を比較・交換しながら並び替えます。
 Bubble-sort with Hungarian ("Csángó") folk dance
  http://www.youtube.com/watch?v=lyZQPjUT5B4&feature=related
○ マージソート
配列を再帰的に分割していき、再び併合(マージ)していくことで、並び替えます。
 Merge-sort with Transylvanian-saxon (German) folk dance
  http://www.youtube.com/watch?v=XaqR3G_NVoo&feature=related
○ クイックソート
軸要素よりも大きい値と小さい値を入れ替えていくことにより並べ替えます。
 Quick-sort with Hungarian (Küküllőmenti legényes) folk dance
  http://www.youtube.com/watch?v=ywWBy6J5gz8&feature=related
image03.jpg

○ 選択ソート
配列の中から、 最小あるいは最大の値をもつものを探し、それを先頭要素と交換しながら並び替えます。
 Select-sort with Gypsy folk dance
  http://www.youtube.com/watch?v=Ns4TPTC8whw&feature=related
○ シェルソート
ソート効率を高めるため、あらかじめ離れている要素を交換しておき、挿入ソートで並べ替えます。
 Shell-sort with Hungarian (Székely) folk dance
  http://www.youtube.com/watch?v=CmPA7zE8mx0&feature=related

SoS.jpg



◇ 知る人ぞ知る「Sorting Out Sorting 」
  30分がっちり勉強しましょう。
  http://video.google.com/videoplay?docid=3970523862559774879#docid=-4110947752111188923
  お急ぎの方はこちら、但し雰囲気のみ。
  http://www.youtube.com/watch?v=JdXoUgYQebM (3分)
  http://www.youtube.com/watch?v=gv0JUEqaAXo&feature=related (7分)

XoaX.jpg


◇ これも知る人ぞ知る 教育ビデオ・チュートリアル
  XoaX.netのwebサイトが制作。
 ○ Algorithms Lesson 1: Bubblesort
  http://www.youtube.com/watch?v=P00xJgWzz2c&feature=relmfu
 ○ Algorithms Lesson 2: Insertion Sort
  http://www.youtube.com/watch?v=c4BRHC7kTaQ&feature=relmfu
 ○ Algorithms Lesson 3: Merge Sort
  http://www.youtube.com/watch?v=GCae1WNvnZM&feature=relmfu
 ○ Algorithms Lesson 4: Quicksort
  http://www.youtube.com/watch?v=y_G9BkAm6B8&feature=relmfu
 ○ Algorithms Lesson 5: Linear and Binary Searching
  http://www.youtube.com/watch?v=wNVCJj642n4&feature=relmfu
 ○ Algorithms Lesson 6: Big O, Big Omega, and Big Theta Notation
  http://www.youtube.com/watch?v=6Ol2JbwoJp0&feature=fvwrel
 ○ Algorithms Lesson 7: Analyzing Bubblesort
  http://www.youtube.com/watch?v=ni_zk257Nqo&feature=relmfu
 ○ Algorithms Lesson 8: Selection Sort
  http://www.youtube.com/watch?v=6nDMgr0-Yyo&feature=related
 ○ Algorithms Lesson 9: Heaps
  http://www.youtube.com/watch?v=v1YUApMYXO4&feature=relmfu
 ○ Algorithms Lesson 10: Heapsort
  http://www.youtube.com/watch?v=6NB0GHY11Iw&feature=relmfu

  http://xoax.net/comp_sci/crs/algorithms/index.phpからもご覧になれます。
  [XoaX.net] http://xoax.net/ には
   [C++][Computer Science][Web Programming][Math][English][Music]
   [Children's]等、コンテンツが豊富です。

SAA.jpg


◇ Sorting Algorithm Animations
  アルゴリズムによる処理速度の違いが視覚的に理解できます。一度はご覧ください。
  http://www.sorting-algorithms.com/
   縦横に並んだ[Restart]ボタンをクリックすると、
   それぞれ初期データ状態やアルゴリズムによる比較ができます。


Animated Sorting Algorithms -David J. Eck
  step実行できるので理解しやすいかも。
  http://math.hws.edu/eck/jsdemo/sortlab.html
    [New Sort]をクリックしてからコンボボックスでアルゴリズムを指定します。

日本のコンテンツも
 ○ [ソート方法][初期配列][配列数]が選択指定でき、ステップ実行もできます。
   http://tokyo-ct.net/usr/kosaka/
   [公開資料][ソートアルゴリズムアニメイション]の[EXE]をダウンロードし実行します。

 ○ Sorting Algorithms Visualizer
   http://wonderfl.net/c/4xiQ
   アルゴリズム、配列数や速さを変更できます。見やすく美しい作りです。 


コメント(0)  トラックバック(0) 
共通テーマ:仕事

コメント 0

コメントを書く

お名前:
URL:
コメント:
画像認証:
下の画像に表示されている文字を入力してください。

※ブログオーナーが承認したコメントのみ表示されます。

トラックバック 0

トラックバックの受付は締め切りました
食費無料のアルバイト

この広告は前回の更新から一定期間経過したブログに表示されています。更新すると自動で解除されます。