- ベストアンサー
テーブルをクイックソートする方法
- JavaScriptを使用して、HTMLのテーブルをクイックソートする方法について教えてください。
- 超初心者の未経験者が、Javascriptでテーブルをクイックソートする方法について困っています。アルゴリズムデータ構造が理解できていないため、アドバイスが欲しいです。
- テーブル内の数字をクイックソートするためのJavaScriptコードと、HTMLの例があります。ソートアルゴリズムについての説明と、コードの解説をお願いします。
- kuma31
- お礼率75% (6/8)
- JavaScript
- 回答数3
- ありがとう数3
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
クイックソート http://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88 スクリプトは動作しないですね・・・。FirefoxのFirebugプラグインでデバッグされるのがよろしいかと。 間違っている点をいくつかあげると ---------- function stringSort(0) { の引数定義が0というのは×。通常変数名を定義。ここでは不要で呼び出しにも要らないかと。 ---------- document.getElementById("tr"+i)) 該当IDの要素がないので×。ここで取得したい要素オブジェクトはtreに入っているのがわかるでしょうか？ ---------- quickSort(x,start,end); のstart、endはインデックスを指定すべき。 start = x[0]; end = x[n-1]; では値が入ってしまう。 ---------- var e; e = x[start]; 基準値がこれでは・・・。 中央値算出すると逆に手間がかかるので、インデックス的に中央近辺にいるのを使用するといいでしょう。 ---------- あと、一番問題なのは、これでは値の配列はソートできても、目的であるノードのソートができないことです。 ヒント。 x[i]=[xval, nodeArray[i]]; とします。※[a, b] で new Array(a, b) と同じ。 ---------- 単に業務で使えればいいということであれば答えてしまうのですが、課題ということなのでこれぐらいにしておきます。 頑張ってください＾＾
その他の回答 (2)
- susie-t
- ベストアンサー率86% (37/43)
> tbody.appendChild(x[i][1]) > とありますが、子供のノードオブジェクトを追加 > する時に、１行足しているという考えなのでしょうか？？ １行足している→[1]のことを指していますか？ だとすると、Noです。 [1]は配列のインデックス指定です。 ---------------------- var ary = new Array(); ary[1] = "one"; ---------------------- とかの[1]と同じです。 つまり、x[i]が配列なのです。更に言えば、xが2次元配列になっているということでもあります。 ---------------------- for(i=0;i<n;i++) { xval=nodeArray[i].firstChild.firstChild.nodeValue; //ソート対象となるデータをxの配列に設定している x[i]=[xval, nodeArray[i]]; } ---------------------- で2次元配列が作成されています。どういうデータかというと ---------------------- [0] [1] [0] 48 1行目のオブジェクト [1] 24 2行目のオブジェクト [2] 36 3行目のオブジェクト [3] 18 4行目のオブジェクト [4] 52 5行目のオブジェクト ---------------------- というデータです。で、quickSortを再帰的に呼び出して値(横軸0)を元に全体をソートします。 ---------------------- [0] [1] [0] 18 4行目のオブジェクト [1] 24 2行目のオブジェクト [2] 36 3行目のオブジェクト [3] 48 1行目のオブジェクト [4] 52 5行目のオブジェクト ---------------------- この後、showで表示されているテーブルの行を全部消した後(removeChild)、この2次元配列の行のオブジェクト(横軸1)を順番に追加する(appendChild)ことでソート結果が表示されるわけです。この横軸1が質問の[1]に対応します。 ・・・2次元配列とか、プログラム初めて間もない方にはちょっと難易度が高いかもしれませんね＾＾； 先は長いですから、今理解できなくても焦らないでいいと思いますよ。ああ、そんな話があるんだ、程度でも頭に入れておけばあとで役に立つと思います。
お礼
回答ありがとうございました。 説明がとってもわかりやすいです！！ 本当に先は長いですが、susie-tさんが 教えてくださったことが、役立てるように がんばります。 また、分からないことがありましたら、 ご指導いただきたいと思います。 本当にありがとうございました(＞θ＜)
- susie-t
- ベストアンサー率86% (37/43)
了解しました。回答です。(なるべく元のコードを使用するようにしています。効率化できる部分もあるのですが、学習のためにはこちらのほうがいいと思いました。) ------------------------- <html> <head> <meta http-equiv="Content-Language" content="ja"> <meta http-equiv="Content-Type" content="text/html; charset=shift_jis"> <title>ソート</title> <script language ="JavaScript"> <!-- var x=new Array(); var nodeArray=new Array(); var n; function TableSort() { var tbd1 = document.getElementById("tbd1"); //ドキュメントにある特定のIｄを持つオブジェクトを示す //HTMLタグのID属性で指定したもの var tre = tbd1.getElementsByTagName("tr") ; // タグを取得する n = tre.length ; // 行の数 for(i=0;i<n;i++) { nodeArray[i] = tre[i]; } } function show() { tbody=document.getElementById('tbd1'); for(i=0;i<n;i++) { tbody.removeChild(nodeArray[i]); //子供のノードオブジェクトを削除 } for(i=0;i<n;i++) { tbody.appendChild(x[i][1]); //子供のノードオブジェクトを追加 } } function stringSort() { start = x[0]; end = x[n-1]; for(i=0;i<n;i++) { xval=nodeArray[i].firstChild.firstChild.nodeValue; //ソート対象となるデータをxの配列に設定している x[i]=[xval, nodeArray[i]]; } quickSort(x,0,x.length-1); show(); } function quickSort(x,start,end){ var data = Math.floor((start + end)/2); var i = start; var j = end; var e; e = x[data]; while(true){ while(x[i][0] < e) i++; //基準値より大きい値を先頭から探す while(x[j][0] > e) j--; //基準値より小さい値を末尾から探す if( i >= j ) break; //両者が交錯していたら抜ける var n =x[i]; //交錯していなければ値を交換 x[i] =x[j]; x[j] =n; i++; // 交換した一つ後に添え字を進める j--; // 交換した一つ前に添え字を進める } if(start < i-1) quickSort(x,start,i-1); // 基準値より小さいグループの再起処理 if(j+1 < end) quickSort(x,j+1 ,end); // 基準値より大きいグループの再起処理 } //--> </script> </head> <body onload="TableSort();" bgcolor="pink"> <!--<img src="img/59.gif">--> <tr><th><big><strong>数字をソートしよう！！</strong></big></th></tr> <br> <br><p> ↓click here!!</p> <table border=1 id="tb1" width=200 bgcolor="white"> <thead > <tr> <th><button onclick="stringSort()">push!!</button></th> </tr> </thead> <tbody id="tbd1"> <tr><td align=center>48</td></tr> <tr><td align=center>24</td></tr> <tr><td align=center>36</td></tr> <tr><td align=center>18</td></tr> <tr><td align=center>52</td></tr> </tbody> </table> </body> </html> --------------------------------------- 処理が理解できたら、効率化に挑戦してみることをオススメします。(学習するのが違う言語になってしまったとのことなので、時間がないかもしれませんが) 頑張ってください＾＾
お礼
susie-tさん、回答ありがとうございます。 お礼が遅くなってしまって申し訳ないです。 言語が変わっても、javascriptは勉強を続けていきます。 「頑張ってください」の一言はとても ありがたかったです。本当にありがとうございました！！
補足
susie-tさん、回答ありがとうございました。 たびたび申し訳ありません。 教えてください。 tbody.appendChild(x[i][1]) とありますが、子供のノードオブジェクトを追加 する時に、１行足しているという考えなのでしょうか？？ よろしくお願いします。
お礼
回答ありがとうございます。 行き詰っていたので、とっても助かります。 アドバイスを頼りにもう一度考えてみます。 本当にありがとうございました！！(〃＾￢＾〃)
補足
susie-tさん、先日はどうもありがとうございます。アドバイスいただいたのですが、結局出来ないでいます。学習内容が変更になり、今後は違う言語を学習することになってしまいました。 答えがわからないまま終わるのは嫌なので回答 いただけないでしょうか。 よろしくお願いします。