マージソートのプログラム
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]を保存して使用するようにしてください。
回答2件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2019/12/09 02:55