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

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

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

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

マージ

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

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

1回答

5671閲覧

C言語でのマージソートのコード

Yhaya

総合スコア439

C

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

マージ

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

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2017/12/21 22:47

今、アルゴリズムの勉強をしています。マージソートのところで、次のようなコードが書かれていたのですが理解できません。

C

1#include <stdio.h> 2#include <stdlib.h> 3#include <time.h> 4 5#define N 15 6 7int sort[N]; 8int buffer[N]; 9 10void MergeSort(int n, int x[]){ 11 int i, j, k, m; 12 if (n <= 1){ 13 return ; 14 } 15 m = n / 2; 16 17 MergeSort(m, x); 18 MergeSort(n - m, x + m); //int型と配列を足せる? 19 20 for (i = 0; i < m; i++){ 21 buffer[i] = x[i]; 22 } 23 j = m; 24 i = k = 0; 25 26 while (i < m && j < n){ 27 if (buffer[i] < x[j]){ 28 x[k++] = buffer[i++]; 29 }else{ 30 x[k++] = x[j++]; 31 } 32 } 33 while (i < m){ 34 x[k++] = buffer[i++]; 35 } 36}

このコード中の Mergesort(n-m, x+m) の部分が何をしているのかよくわかりません。また、その後のコードについても何をしているのかよくわかりません。

よろしくお願いいたします

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

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

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

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

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

guest

回答1

0

ベストアンサー

まず、「マージソート」がどんなソートだったか考えてみましょう。

  • 前半をソートする
  • 後半をソートする
  • 前半と後半をマージする

まず、 MergeSort(m, x);x[0]x[m-1]までの分をソートします。そして、MergeSort(n - m, x + m);で残りのn - m個をソートしています。なお、「配列 + 整数」はポインタ演算で、結果は「x[m]以降を指すもの」になります。

半分ずつのソートが済めば、あとはマージをするわけですが、後半に入ったままだとマージをやりづらいので、いったん後半をbufferにコピーして、それからマージを行っています。

投稿2017/12/21 23:02

maisumakun

総合スコア145121

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問