質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

マージ

複数のデータベースやファイル、プログラムなどを決まった手順や規則に従って一つに結合すること。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1460閲覧

c++ マージソートについて

_._._ami

総合スコア26

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

マージ

複数のデータベースやファイル、プログラムなどを決まった手順や規則に従って一つに結合すること。

ソート

複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

1グッド

1クリップ

投稿2020/11/22 15:10

マージソートについてですが, void margeの中の上から3行目のL[i]を出力してみたところ,
入力がn=8,A[i]=8 7 6 5 4 3 2 1にすると, L[i]は8 6 7 8 4 2 3 4 5 6 7 8でした.

A[i]=8 7 6 5 4 3 2 1をマージソートすると,
8 7 6 5 4 3 2 1
7 8 5 6 3 4 1 2
5 6 7 8 1 2 3 4
1 2 3 4 5 6 7 8
となると思ったのですが,このL[i]は何を表しているのですか?

また最後は1234ではなく5678がL[i]に格納されている(?)のはなぜですか.

基本的な質問かもしれませんがよろしくお願いします.

c++

1#include<iostream> 2using namespace std; 3 4#define INFTY 2000000000 5#define MAX 500000 6 7int L[250000+2],R[250000+2]; 8int t=0; 9 10void marge(int A[],int left,int mid,int right){ 11 int n1 = mid - left; 12 int n2 = right - mid; 13 14 for(int i=0;i<n1;i++) L[i] = A[left + i]; //ここです! 15 for(int i=0;i<n2;i++) R[i] = A[mid + i]; 16 17 L[n1]=R[n2]=INFTY; 18 19 int i=0,j=0; 20 for(int k=left;k<right;k++) 21 { 22 t=t+1; 23 if(L[i]<R[j]){ 24 A[k] = L[i]; 25 i = i+1; 26 }else{ 27 A[k] = R[j]; 28 j = j+1; 29 } 30 } 31 32} 33 34void margeSort(int A[],int left,int right){ 35 if(left+1 < right){ 36 int mid = (left+right)/2; 37 margeSort(A,left,mid); 38 margeSort(A,mid,right); 39 marge(A,left,mid,right); 40 } 41} 42 43int main(){ 44 int A[MAX],n; 45 46 cin >> n; 47 for(int i=0;i<n;i++) cin >> A[i]; 48 49 margeSort(A,0,n); 50 51 for(int i=0;i<n;i++){ 52 if(i)cout << " "; 53 cout << A[i]; 54 } 55 cout << endl; 56 cout << t << endl; 57 58 return 0; 59}
DrqYuto👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

C++

1void print(int L[], int n1, int R[], int n2) 2{ 3 cout << "L:[ " << L[0]; 4 for (int i = 1; i < n1; i++) cout << ' ' << L[i]; 5 cout << " ]\t\tR:[ " << R[0]; 6 for (int i = 1; i < n2; i++) cout << ' ' << R[i]; 7 cout << " ]\n"; 8} 9 10 for(int i=0;i<n1;i++) L[i] = A[left + i];//ここです! 11 for(int i=0;i<n2;i++) R[i] = A[mid + i]; 12 print(L, n1, R, n2);

このようにすると、実行結果は次のようになりました。

text

18 28 7 6 5 4 3 2 1 3L:[ 8 ] R:[ 7 ] 4L:[ 6 ] R:[ 5 ] 5L:[ 7 8 ] R:[ 5 6 ] 6L:[ 4 ] R:[ 3 ] 7L:[ 2 ] R:[ 1 ] 8L:[ 3 4 ] R:[ 1 2 ] 9L:[ 5 6 7 8 ] R:[ 1 2 3 4 ] 101 2 3 4 5 6 7 8 1124

merge sort では、入力の [8 7 6 5 4 3 2 1] を
[8 7 6 5] と [4 3 2 1] に分けます。

次に [8 7 6 5] を [8 7] と [6 5] に分けます。

次に [8 7] を [8] と [7] に分けます。
これが最初の L:[ 8 ]   R:[ 7 ] です。
これはマージされて [7 8] になりますが、デバッグ表示はまだ先です。

次に [6 5] を [6] と [5] に分けます。
これが2番目の L:[ 6 ]   R:[ 5 ] です。
これはマージされて [6 5] になります。
そして、3番目の L:[ 7 8 ]   R:[ 5 6 ] になります。
マージされて [5 6 7 8] になりますが、デバッグ表示は最後になります。

以下同様に [4 3 2 1] についてソートします。

最後は、L:[ 5 6 7 8 ]   R:[ 1 2 3 4 ] をマージします。

投稿2020/11/22 18:49

kazuma-s

総合スコア8224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

_._._ami

2020/11/23 00:57

非常にわかりやすく, 丁寧にありがとうございます...!!とても助かりました
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問