これって何ソート？
- ソートの関数ってものを一回作ってみようかと思って単純に考えて思いついたのがコレなんですがこのやり方ってなんか名前があるんでしょうか？
- コレって速度的にはどんなもんなんでしょうか？
- メモリはジャブジャブ使いますがバブルソートよりははやいみたいです
- ベストアンサー
これって何ソート？
ソートの関数ってものを一回作ってみようかと思って 単純に考えて思いついたのがコレなんですが このやり方ってなんか名前があるんでしょうか？ コレって速度的にはどんなもんなんでしょうか？ function sepSort(&$arr){ $lower=array(); $upper=array(array_pop($arr)); foreach($arr as $n){ if($n<$upper[0]){ $lower[]=$n; }else{ $upper[]=$n; } } if(isset($lower[1]))sepSort($lower); if(isset($upper[1]))sepSort($upper); $arr=array_merge($lower,$upper); } メモリはジャブジャブ使いますが バブルソートよりははやいみたいです
- H240S18B73
- お礼率60% (78/128)
- PHP
- 回答数4
- ありがとう数4
- みんなの回答 （4）
- 専門家の回答
質問者が選んだベストアンサー
要素を一つ選んで、それより上か下かで分割→それぞれを同様に処理 と言う流れはクイックソートのものですね。 配列をコピーしている分、通常のクイックソートよりは遅くなっていると思われます。
その他の回答 (3)
ピボットを先頭要素にとったクイックソートかな？ というかアルゴリズム云々いろいろやるならC言語でやった方がいいと思います。 http://qiita.com/mpyw/items/e6ef473fe3464599f498
お礼
ありがとうございます 実のところ基本だとか言われてるCはObjective-Cをちょっと触ってみた時にちょっとさわり程度にやっただけで全然です、特にCを使わないといけない何かもないし、オブジェクト指向についてはAS3である程度やったので、わざわざ使う予定のないもので同じ事やりなおすのもなぁってカンジで億劫になってます、というかCをさわり程度さわった時、AS3の方がオブジェクト指向としてキレイだと思ったので手をだしてないです、そのAS3も使う予定がないわけですが…
- Gotthold
- ベストアンサー率47% (396/832)
クイックソートかな。 メモリの消費量は工夫すれば減らせる。
お礼
基本配列をコピーしながら再起的にやる現行のやり方でも ２～３無駄と思われるとこがあるので とりあえずそこから手をつけてみます 引数に整列対象の範囲を渡せるようにすれば 配列をコピーしないで済みそうですが 処理がややこしくなりそうなのでこっちは後回しにします ありがとうございます
- Tacosan
- ベストアンサー率23% (3656/15482)
たぶんクイックソート.
お礼
なんか結構はやいと思ったらブレはあるにしろ普通に最速候補なんですね、シンプル・イズ・ベストってカンジでしょうか
関連するQ&A
- ２つの配列を再帰的に上書きでマージしたい
array_merge_recursive では配列が同じ数値キーを有している場合、 後の値は元の値を上書せず、追加されます。 これを上書されるようにしたいのですが、どのようにすれば良いでしょうか？ $arr3 = mymerge($arr1,$arr2); のような形で$arr3が得られると助かります。 $arr1,$arr2は再利用したいので書き換えられないようにしたいです。 次のような物をネット上で見つけたのですが、これでは$arr1が書き換えられてしまいます。 function mymerge(&$arr1,$arr2){ foreach ($arr2 as $key=>$value){ if(is_array($value)){ mymerge(&$arr1[$key],$value); }else{ $arr1[$key]=$value; } } return $arr1; } 次のようにすれば良いのかもしれませんが、１つのfunctionでできると助かります。 $temp1 = array(); $temp2 = mymerge($temp1,$arr1); $arr3 = mymerge($temp2,$arr2); いくら考えても分からないので、すみませんがどなたか教えてください。_○_
- ベストアンサー
- PHP
- マージソート
マージソートの実行時間を測定するプログラムを書いています。 コンパイルの時にはエラーが出ないのですが、実行するとコマンドプロンプトが強制終了されます。 どこが悪いか、どう直せばいいのか指摘していただけないでしょうか？ よろしくお願いします。 ～qtime.c～ //マージソート実行用プログラム //bcc32 mtime.c merge.c m1.c sfmt.c #include <stdio.h> #include <stdlib.h> #include <time.h> #include "sfmt.h" #define MAX 5000 void merge_sort(int a[], int start, int end); main() { int i , x[MAX] , n; time_t start , end ; int sn; printf("適当な数字の入力 : "); scanf("%d", sn); init_gen_rand(sn); for(i=0; i<MAX; i++) x[i]= (gen_rand32()% MAX);; n=MAX; start = clock(); //測定対象プログラム merge_sort(x, 0, n-1); end = clock(); printf("sort\n"); for(i =0 ; i < n ; i++ ) if ( i == i/100*100) printf("%d\n" , x[i]); printf ("実行時間: %f sec\n" , (double)(end-start) /CLOCKS_PER_SEC); return 0; } ～merge.c～ int b[100]; void merge_array(int x[], int start, int end) { int mid, i, j, k; mid = (start + end) /2; i = start; j = mid + 1; for(k = start; k <= end; k++){ if(x[i] > x[j] && j <= end || i > mid){ b[k] = x[j]; j++; } else{ b[k] = x[i]; i++; } } for(k = start; k <= end; k++){ x[k] = b[k]; } } ～m1.c～ void merge_array(int x[], int start, int end); void merge_sort(int a[], int start, int end); void merge_sort(int a[], int start, int end) { int mid; if(start >= end) return; mid = (start + end) / 2; merge_sort(a, start, mid); merge_sort(a, mid + 1, end); merge_array(a, start, end); }
- ベストアンサー
- C・C++・C#
- 割り切れなくなるまで分割して配列に入れたい
<?php make(7); function make($n) { $arr = array($n); $arr_new = division_arr($arr); print_r($arr_new); } function division_arr($arr) { for ($i = 0; $i < count($arr); $i++) { $arr_new[$i] = division($arr[$i]); if ($arr_new[$i][0] > 0) { return division_arr($arr_new[$i]); } else { } } return $arr_new; } function division($n) { $a = $b = floor($n / 2); if ($n % 2 != 0) { $b+=1; } return array($a, $b); } /* array( [3,4], [[1,2],[2,2]], [[0,1],[1,1],[1,1],[1,1]] ); 再帰的に配列を分割していき、最終的にこのような出力にしたいです。 */ ?> 教えて下さい。よろしくお願いいたします。m(_ _)m
- ベストアンサー
- PHP
- modified bubble sort
ソーティングについて教えてください． ソーティングの手法に，バブルソートというものがあります(隣接するふたつを入れ替える)．このソーティングでは，最大交換回数は要素数が n のとき， n(n-1)/2 となります． 隣接する要素の交換に加え，先頭と最後の要素の入れ替えも可能だとすると(イメージとしては，サイクリックなバブルソートです)，最大交換回数は n^2/4 となるそうです． この n^2/4 になる，という理由が分かりません(普通のバブルソートが n(n-1)/2 になるのは理解できます)．どなたかご教授頂ければと思います．
- 締切済み
- 数学・算数
- 配列の日付ソート処理2
先ほど下記のような質問をしたのですが、、、 最初の配列の添え字を取得したい場合はどのようにしたらいいのでしょうか？？ ksort($up_date, "cmp"); while (list ($key, $value) = each ($up_date)) { echo "$key: $value\n"; } function cmp ($a, $b) { if ($a == $b) return 0; return ($a > $b) ? -1 : 1; } としても、日付がうまく昇順されません。 この方法では駄目なのでしょうか？？ ******************************************* 配列に下記のような日付が入ってます。 $array[0]=2004-11-01 14:20:10.412761+09; $array[1]=2004-11-28 19:09:42.898169+09; $array[2]=2004-11-26 17:16:10.531744+09; $array[3]=2004-11-30 20:25:39.622259+09; これをもっとも新しい日付の順序にしたいのですが、 これはやはり、バブルソートなどを作成する必要がでてきますでしょうか？？？ *********************************************
- ベストアンサー
- PHP
- javascript バブルソート
javascriptでバブルソートの実装をしています。 リストにある数値を取得して昇順 or 降順したいのですがうまくいきません。 方法を教えていただけないでしょうか。 よろしくお願いします。 <!DOCTYPE html> <html lang="ja"> <head> <meta charset="UTF-8"> <script type="text/javascript"> function bubbleSort(){ var liVal = document.getElementsByTagName("li"); var array = []; for(var i = 0; i < liVal.length; i++){ for(var j = 0; j < liVal.length-i-1; j++){ array[j] = parseInt(liVal[j].innerHTML); if(array[j] > array[j+1]){ var n = array[j]; array[j] = array[j+1]; array[j+1] = n; } } } } </script> </head> <body> <ul> <li>10</li> <li>5</li> <li>48</li> <li>22</li> <li>679</li> </ul> <p><a href="javascript:void(0);" onclick="bubbleSort()">ソート(降順)</a></p> </body> </html>
- 締切済み
- JavaScript
- マージソートのプログラム
↓が自分の作ったマージソートのプログラムなのですが、コンパイルするとエラーが起きてしまいます。 mergesort()にポインタを引数として渡してる、引数の数が足りない、ということが書いてありますが…。 ちゃんとint型を渡してるし、引数の数も合ってるように思います。 どこがおかしいのでしょう？ #include<stdio.h> #include<stdlib.h> #include<time.h> #define Max 255 int A[Max]; main(){ int n,k; n=inputdata(); int w=1; mergesort(w,n); printdata(n); return(0); } inputdata(){ //配列に乱数を要素として入れていく int n,i; printf("n= "); scanf("%d",&n); //使用者にいくつの要素を入れるか指定してもらう srand(time(NULL)); for(i=1; i<=n; i++){ A[i]=1+rand()%30; } printf("A[%d]={%d,",n,A[1]); for(i=2;i<n;i++) printf("%d,",A[i]); printf("%d}\n",A[n]); return(n); } void mergesort(int p, int r){ int q; if(p<r){ q=(p+r)/2; mergesort(p,q); mergesort(q+1,r); merge(p,q,r); } } void merge(int p, int q, int r){ int i,j,k,B[Max]; i=p; j=q+1; for(k=p;k<=r;k++){ if((j>r) || ((i<=q)&&(A[i]<=A[j]))){ B[k]=A[i]; i++; }else{ B[k]=A[j]; j++; } } for(k=p; k<=r; k++) A[k]=B[k]; } printdata(int n){ int i; printf("A[%d]={%d,",n,A[1]); for(i=2; i<n; i++) printf("%d,",A[i]); printf("%d}\n",A[n]); } ・エラーメッセージ merge1.c: In function ‘main’: merge1.c:12: warning: passing argument 1 of ‘mergesort’ makes pointer from integer without a cast merge1.c:12: error: too few arguments to function ‘mergesort’ merge1.c: At top level: merge1.c:31: error: conflicting types for ‘mergesort’ /usr/include/stdlib.h:294: error: previous declaration of ‘mergesort’ was here merge1.c:41: warning: conflicting types for ‘merge’ merge1.c:37: warning: previous implicit declaration of ‘merge’ was here
- ベストアンサー
- C・C++・C#
- ソートの名称について
以下のようなソートに、選択ソートやバブルソート等といった名称は存在しますか？ #include <stdio.h> int main(void) { int array[10]; int i, j, tmp; /* Input */ for(i=0; i<sizeof(array)/sizeof(int); i++){ printf("array[%d]> ", i); scanf("%d", &array[i]); } /* Sort */ for(i=0; i<sizeof(array)/sizeof(int)-1; i++){ for(j=i+1; j<sizeof(array)/sizeof(int); j++){ if(array[i]>array[j]){ tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } } /* Output */ for(i=0; i<sizeof(array)/sizeof(int); i++){ printf("array[%d]: %d\n", i, array[i]); } return 0; }
- ベストアンサー
- C・C++・C#
- バブル・ソート、クイック・ソート
N個（N=4,5,6）のデータが全て等しいデータ列（例えばN個の数字全部が1のとき）をバブルソートで並び替えたとき、データの交換回数は何回か。また、同じデータ列をクイックソートで並び替えたときはどうか。 という問題があるのですが、どう比較するのかがわかりません。詳しい方、説明よろしくお願いします。
- 締切済み
- C・C++・C#
- キーが倍数の時の値の存在チェック方法
PHP5.2.4を使用しています。 連想配列のキーが[]で囲まれている時、 その中の数字が倍数としてチェックされるとします。 次の例では、3と4の倍数の時に条件（if (is_int($wk))）に引っかかり キーの値（3の倍数です、など）が表示されます。 ただこのやり方だと、foreachでループさせないと倍数かどうかが分からないので、 もっと効率の良い（isset($arr[$i])で調べられるような）調べ方はできないでしょうか？ $arr = array( '1' => '1です', '2' => '2です', '[3]' => '3の倍数です', '[4]' => '4の倍数です', ); for ($i = 1; $i < 15; $i++) { if (isset($arr[$i])) //←全てこの（簡単な）条件式で調べられれば良いのですが・・・ { print "{$arr[$i]}<br>\n"; } foreach ($arr as $key => $value)//←キーが倍数かはどうしても全てのキーをチェックせざるえない { if (preg_match("/\[(\d+)\]/", $key, $match)) { $wk = $i / $match[1]; if (is_int($wk)) //←除算した結果が整数ならその倍数だと判明 { print "i={$i} {$arr[$match[0]]}<br>\n"; } } } } 1です 2です i=3 3の倍数です i=4 4の倍数です i=6 3の倍数です i=8 4の倍数です i=9 3の倍数です i=12 3の倍数です i=12 4の倍数です i=15 3の倍数です
- 締切済み
- PHP
お礼
値を入れ替える処理においても結局数値型の値が追加されることになるのでどっちか判断つかず簡単な方を取りました $a=$a^$b; $b=$a^b; $a=$a^b; なんてやり方もあるみたいですが数値にしか使えないし 早いのかどうかもわからないので放置してます また試してみます ありがとうございました
補足
クイックソートの概要をわかりやすく言ってくれたのでBA