Implementation (Part 1)
Coddyの「マージソート - DSAシリーズ」コースのレッスン 5/9。
マージソートを、その核心となる操作から順に構築していきます。
チャレンジ
簡単マージソートの核心は、既にソートされた2つのリストを1つのソートされたリストに結合することです。まずはそれを作成しましょう。
2つのソート済み整数配列 left と right を受け取り、それらすべての要素を含む1つのソート済み配列を返す、merge という名前の関数を作成してください。
両方の配列を同時に走査します。2つの先頭要素のうち、小さい方を繰り返し取り出します。一方の配列が空になったら、もう一方の配列に残っているすべての要素を追加します。
自分で試してみよう
#include <stdlib.h>
int* merge(int* left, int left_size, int* right, int right_size, int* returnSize) {
// ここにコードを書いてください
*returnSize = 0;
return left;
}
腕試しこのレッスンには短いクイズがあります。レッスンを始めて解答し、進捗を記録しましょう。
マージソート - DSAシリーズのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity