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

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

ただいまの
回答率

87.49%

マージソートの使用メモリ量を半分にする方法を教えてください

解決済

回答 2

投稿

  • 評価
  • クリップ 1
  • VIEW 1,133
退会済みユーザー

退会済みユーザー

マージソートのプログラム

void merge(int first, int last, int *data, int *work)
{
   int middle, mae, ato,i;

   if(first == last)
   {
      return;
   }

   middle = (first + last) / 2;

   merge((i = mae = first), middle, data, work);
   merge((ato = middle + 1), last, data, work);

   while(mae <= middle && ato <= last)
   {
      if(data[mae] <= data[ato])
      {
         work[i++] = data[mae++];
      }
      else
      {
         work[i++] = data[ato++];
      }
   }

   while(mae <= middle)
   {
      work[i++] = data[mae++];
   }

   while(ato <= last)
   {
      work[i++] = data[ato++];
   }

   for(i = first; i <= last; i++)
   {
      data[i] = work[i];
   }
}

メイン関数

int main()
{
   int data[8] = {2, 8, 7, 3, 6, 1, 5, 4};
   int work[8];

   merge(0, 7, data, work);

   for(int i = 0; i < 8; i++)
   {
      printf("%d", data[i]);
   }
}

出力結果

12345678

質問内容

data配列の要素数をnとしたとき、上記のようなマージソートの使用メモリ量はnですが、半分のメモリ量しか使用しなくて済むようなプログラムの改造方法を教えてください。またその時の条件として、int work[(n + 1) / 2]を確保し、data[first]からdata[middle]を保存して使用するようにしてください。

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • 退会済みユーザー

    2019/12/09 09:50

    複数のユーザーから「やってほしいことだけを記載した丸投げの質問」という意見がありました
    「質問を編集する」ボタンから編集を行い、調査したこと・試したことを記入していただくと、回答が得られやすくなります。

回答 2

checkベストアンサー

+1

前半と後半のソートが終わった後、前半を work にコピーし、その work と
data の後半をマージすれば work のサイズは半分で済みます。

void merge(int first, int last, int *data, int *work)
{
   if (first == last) return;

   int middle = (first + last) / 2;
   merge(first, middle, data, work);
   merge(middle + 1, last, data, work);

   int i = first, j = first, k = 0, n = 0;
   while (j <= middle) work[n++] = data[j++];  // 前半を work に

   while (k < n && j <= last)
      if (work[k] <= data[j])
         data[i++] = work[k++];
      else
         data[i++] = data[j++];

   while (k < n) data[i++] = work[k++];
   while (j <= last) data[i++] = data[j++];
}

#include <stdio.h>

int main(void)
{
   int data[8] = {2, 8, 7, 3, 6, 1, 5, 4};
   int work[4];

   merge(0, 7, data, work);
   for (int i = 0; i < 8; i++) printf("%d", data[i]);
}

追記
while (j <= last) data[i++] = data[j++]; の行は不要でした。削除してください。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/12/09 11:55

    質問投稿後、自分で続けて考えており、ソートする前にwork[4]にdata[0]〜data[3]を入れて...など色々試して上手くいかなかったので助かりました。ありがとうございます!

    キャンセル

+1

データは8bitに収まるのでchar型にします。これでたいていの環境では1/4になります
データの大きさがMaxで8なので、4bitにおさまるので、charに2要素を詰め込めば
1/8になります

とりあえず簡単な解決法です

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

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

  • ただいまの回答率 87.49%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る