- ベストアンサー
Lispでマージソート
Lisp初心者のものです。 Lispでマージソートはどのように書けばいいのでしょうか？ 結果のリストは、二つの引数リストの要素すべてを含んでいなければならず、たとえば (marge ' (3 3 6 7) ' (2 5 8)) の答えは (2 3 3 5 6 7 8) です。
- lowright
- お礼率68% (11/16)
- その他（プログラミング・開発）
- 回答数3
- ありがとう数2
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
厳密にいうと全然足りないけどまあいいか. まず, 2つのリスト L1, L2 がどちらも「要素を持つ」ときを考えます. L1, L2 の先頭要素はもってこれますか? で, L1 の先頭要素の方が小さければ, これは「最終的にできるリスト」の先頭要素になることが確定します. 残りの部分は「L1 から先頭要素を除いたリスト」と L2 をマージしたリストなので, これを (再帰的に) 求めてから L1 の先頭要素を (先頭に) 追加します. L2 の先頭要素の方が小さいときもほぼ同じなので省略. あと, いずれかのリストが空のときにはもう一方のリストを返せばいいですね. だから, 全体としておよそ (defun merge (x y) (if (null x) y (if (null y) x (let (....) ....)))) という形になるはずです. let は使わなくてもいいんだけど多分使った方がきれい.
その他の回答 (2)
- Tacosan
- ベストアンサー率23% (3656/15482)
CommonLisp にはそのままずばりの merge って関数があるんだけど, これを「自分で作れ」って話ですよね? そもそも手順を書けますか?
補足
はい、自分で作るということです。 手順的には、リストの先頭データを比較して、小さい値を選んで、それを繰り返していく、という手順を考えたのですが・・・。
- sakusaker7
- ベストアンサー率62% (800/1280)
マージソートというか、そのマージの部分では? > (marge ' (3 3 6 7) ' (2 5 8)) の答えは 名前も merge だし、この例だとリストは両方とも 昇順にソートされてる状態ですよね。 引数は常にソートされてる状態だと仮定していいんでしょうか?
補足
すいませんマージの部分です。 はい、引数は常にソートされている状態です。
関連するQ&A
- C++でのマージソートの実現方法について
C++でのマージソートの実現方法について、以下のコードを書いたのですが、どうしてもうまくソートできませんでした。 marge関数がおかしいと思うのですが、自分で確かめてみても、どこがおかしいのか分かりませんでした。 どなたか、どうすればソートされた結果がメイン関数で表示されるようにできるのか教えていただけないでしょうか？ #include <iostream> #include <vector> using namespace std; class Array { private: vector<int> array; public: void insert( int value ){ array.push_back( value ); } int getSize( ){ return (int)array.size( ); } void marge_sort( ){ marge_sort( 0, (int)array.size( ) - 1 ); } void marge_sort( int left, int right ); void marge( int left, int middle, int right ); void print( ); }; // マージソートにより配列の添字 left ～ right の部分を整列する関数 void Array::marge_sort( int left, int right ){ if( left >= right ) { return; } int middle = (left + right) / 2; //中央の添字を求める marge_sort( left, middle ); //左の要素が全てバラバラになるまで marge_sort( middle + 1 , right ); //右の要素が全てバラバラになるまで marge( left, middle, right ); //バラバラの要素をソートして併合 } // 個別にソートされた2つの配列（添字 left ～ middle と添字 middle+1 ～ right）を作業用配列を使ってマージする関数 void Array::marge( int left, int middle, int right ) { int num=right-left; int *tmp=new int[num]; int t=0,l=left,r=middle; while(l<middle&&r<right){ if(array[l]<=array[r]){ tmp[t++]=array[l++]; } else { tmp[t++]=array[r++]; } } while(l<middle){ tmp[t++]=array[l++]; } while(r<right){ tmp[t++]=array[r++]; } for(int i=0;i<num;i++){ array[left+i]=tmp[i]; } delete tmp; } // 配列の内容を表示する関数 void Array::print( ) { for ( int i = 0; i < (int)array.size( ); i++ ) { cout << array[i] << " "; } cout << endl; } int main( ) { Array a1; a1.insert( 56 ); a1.insert( 34 ); a1.insert( 57 ); a1.insert( 64 ); a1.insert( 3 ); a1.insert( 87 ); a1.insert( 85 ); a1.insert( 37 ); a1.insert( 21 ); a1.insert( 4 ); a1.insert( 68 ); a1.insert( 62 ); a1.insert( 42 ); a1.insert( 55 ); a1.insert( 63 ); a1.insert( 95 ); a1.insert( 7 ); a1.insert( 32 ); a1.insert( 78 ); a1.insert( 11 ); cout << "要素数: " << a1.getSize( ) << endl; cout << "ソート前: "; a1.print( ); a1.marge_sort(); // ここで，ソートを行う関数を呼び出す cout << "ソート後: "; a1.print( ); return 0; } // 実行結果 要素数: 20 ソート前: 56 34 57 64 3 87 85 37 21 4 68 62 42 55 63 95 7 32 78 11 ソート後: 3 4 34 37 21 42 55 56 57 62 63 7 32 64 68 78 85 87 95 11 ↑のソート後の表示が、昇順にソートされるようにしたいのです。
- ベストアンサー
- C・C++・C#
- 非再帰のマージソートについて
非再帰のマージソートを作成しているのですが、 上手いこと出来なくて困っています。 条件として配列の開始と終了のインデックスを指定して、 その間の要素だけをソートしたいのです。 ex： int array[10] = { 9,8,7,6,5,4,3,2,1,0 }; MergeSort( array, 2, 6 ); // array[2]～array[6]をソート for( int i=0; i<10; i++ ) printf( "%d, ", array[i] ); 出力） 9, 8, 3, 4, 5, 6, 7, 2, 1, 0, 以下のサイトで公開されているマージソートを元に 私なりに弄ってはいるのですが、 メモリを壊してしまうようなエラーが頻発して、 どうもうまくいかないのです・・・。 http://besky-works.spaces.live.com/Blog/cns!555CF2E2F9E31C71!557.entry どなたがおわかりの方がいらっしゃれば、 その方法を教えていただければ助かります。
- ベストアンサー
- C・C++・C#
- マージソートについて
マージソートの要素の比較と交換回数を計測するプログラムを作っているのですが、マージのどの段階が交換処理になるのかが分からず困っています。 マージ処理の実行回数をカウントする配列ｓを設けて処理をカウントする場合、以下のプログラムだとどのタイミングでカウントすればよいでしょうか？ ちなみに配列aは初めに値を割り振った配列で、配列bは別途で用意した作業用配列です。 最後のfor文やif文付近で配列の値を変化させて計測してみたのですが、計算量に合った動きをしてくれませんorz void merge_sort(int a[], int low, int high){ int mid, i, j, k; if(low >= high) return; mid = (low + high)/2; merge_sort(a, low, mid); merge_sort(a, mid+1, high); for(i = low; i <= mid; i++) b[i] = a[i]; for(i = mid+1, j=high; i <= high; i++, j--) b[i] = a[j]; i = low; j = high; for(k = low; k <= high; k++){ if(b[i] <= b[j]){ a[k] = b [i++]; } else{ a[k] = b[j--]; } } }
- ベストアンサー
- C・C++・C#
- マージソートが外部整列に向いている理由。
現在ソート方法について学んでいます。 色々と調べながら勉強を進めているのですが、 マージソートは外部整列に向いている。 とよく書かれているものの、 「なぜ」外部整列に向いているのかが分かりません。 パソコンの知識が乏しい者ですので、出来るだけ初心者でも分かりやすい説明をして頂けると助かります。 宜しくお願い致します。
- ベストアンサー
- その他（プログラミング・開発）
- 22年春 基本情報処理試験 問8 マージソート
22年春の基本情報処理試験 、問8のマージソートが解らないでいます。 設問2で与えられている、3、8、2、7、5、1という値を関数Sortに渡し、 これを実行すると、 一番最初に関数Mergeが実行される時に、関数Mergeに渡される引数は、 slist1 = 8、num1 = 1、slist2 = 2、num2 = 1になりますよね？ それで、関数Mergeを実行して、list[] = {2,8} が返却されるところまでは、 理解できるのですが、その後の動きがわかりません。 僕はいくら考えても、ここで終わっちゃうんです。 どの関数に、どの引数を渡してあげればよいのでしょうか… どなたか教えて下さい。 よろしくお願いします。
- ベストアンサー
- 情報処理技術者
- 配列の中に、リストが入っているものをボトムアップ形式でマージソートして
配列の中に、リストが入っているものをボトムアップ形式でマージソートしています。 リストは、空のノードの次に文字列が入ったノード、というものです。 sizeは、配列の要素数となっています。 merge_listは、リスト２つをマージするものです。 ２つのリストをマージして、ひとつになったリストを最初のリストが入っていた配列に入れる。 もう片方はＮＵＬＬにする。 順に繰り返していき、配列の要素が１つのみになったらそれを返す・・・ といったアルゴリズムなのですが、うまく配列の中のリストが指定できません。 調べたところ、おそらくプログラム中の矢印があるところに問題があってprintfが実行できないようなんですが、原因がわかりません。 同じ原因によりmerge_listに、マージしたいリストが入っていないようなんですが・・・。 説明下手ですいませんが、どうかよろしくお願いします。 typedef struct list * word_list; struct list { char* word; word_list rest; }; word_list _mergesort(word_list* word_lists, int size) { int i=0, j; while(1){ while(1){ while(word_lists[i] =NULL) //配列に一つ目の要素が見つかるまで回す <- 原因 i++; j = i+1; while(word_lists[j] =NULL) //配列に二つ目の要素が見つかるまで回す<- 原因 j++; if(j == size) //マージする要素が後ろになかったら終了 break; //printf("%d,%d\n",i, j); printf("%s\n",word_lists[i] ->rest ->word); ＜－ここでエラー printf("%s\n",word_lists[j] ->rest ->word); word_lists[i] =merge_list(word_lists[i], word_lists[j]); word_lists[j] =NULL; printf("%s",word_lists[i]->rest ->word); i = j+1; } if(i !=0){ i = 0; }else{ break; //要素がひとつしかなかったら終了 } } return word_lists[0]; }
- ベストアンサー
- C・C++・C#
- Lispについてわからないことが(Scheme)
あるLispの勉強ソフトで、 「関数lを『引数としてxを受け取ると、xの要素の数を返す関数』として定義しなさい。」 という問題があるのですが、私は以下のようにしました。 (define l (lambda (x) (if (= x null?) 0 (+ 1 (l (cdr x)))))) しかしこれだとオーバーフローと表示されて強制終了されてしまいました。 そこで答えをネットで検索したところ以下のものが見つかりました。 (define l (lambda (x) (cond ((null? x) 0) (else (+ 1 (l (cdr x))))))) これが正解なようですが、この2つのリストの違いがわかりません。 初歩的なことですがifの使い方を間違っているんでしょうか？
- ベストアンサー
- その他（プログラミング・開発）
- マージソート内の再帰処理にすいて
#include<stdio.h> #define MAX 4 int temp[MAX]; void marge(int num[],int left,int right) { int i,j,mid,k if(left>=right)return; mid=(left+right)/2; marge(num,left,mid);//(1) maege(num,mid+1,right);//(2) for(i=left;i<=mid;i++) temp[i]=num[i]; for(i=mid+1,j=right;i<=right;i++,j--) temp[i]=num]j]; i=left; j=right; for(k=left;k<=right;k++) if(temp[i]<=temp[j]) num[k]=temp[i++]; else num[k]=temp[j--] } マージソート内はこういった関数を記述してエラーもでないのですが、(1)と(2)の処理がよくわかりません。 (1)は再帰的に処理していってif(left>=right)return;の条件を満たした場合に(2)の処理に入っていきますよね？ その場合、(2)の処理を行う際に(1)が(2)の再帰より前に記述されているので(1)がまた処理されるのでしょうか？ 一連の流れを(1)、(2)を使って表してほしいです。
- 締切済み
- C・C++・C#
お礼
なるほど、そういう手順でいけばいいわけですね。 ありがとうございました。