それがあなたが探しているものかどうかはわかりませんが、主な条件orをに置き換えることでマージ ループを簡素化できます。and
while length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end while
# You know that one of left and right is empty
# Copy the rest of the data from the other
while length(left) > 0
append first(left) to result
left = rest(left)
end while
while length(right) > 0
append first(right) to result
right = rest(right)
end while
はい、3 つのループがありますが、最後の 2 つのうち 1 つだけが実行されます。
疑似コードに基づいた C99 コードの動作
したがって、コードは C99 可変長配列 (C11 のオプション機能) を使用します。でコンパイルすると-DDEBUG、プログラムの実行中に広範なトレースが得られます。なしでコンパイルすると、入力 (ソートされていない) 配列と出力 (ソートされた) 配列のみが出力されます。愚かなタイプミスを診断するためにそれが必要でした（aが明らかに必要なr_pos場所）。l_pos一般的なテクニックに注意してください。
- ドキュメントの入力と関数の終了
- 診断出力関数を作成します (ここ
dump_array()では、1 つの引数に「タグ」(どの呼び出しが使用されているかを識別するため)、その他の引数には出力するデータ構造を指定します)。
- 適切なポイントで診断印刷機能を呼び出します。
- 診断を簡単に有効または無効にできます。
製品品質のコードの場合、私の診断出力関数もFILE *fp引数を取り、指定されたファイルに書き込みます。ここでだまされて使用されstdoutました。追加の一般性は、この関数を使用して、stderrまたはログ ファイルに書き込むことができることを意味しますstdout。
スペース管理
このmerge_sort()コードは、完全な入力配列を 2 つの小さな配列 (leftとright) にコピーしてから、小さな配列を並べ替え (再帰)、並べ替えられた小さな配列を入力配列にマージします。これは、log N レベルの再帰のそれぞれで発生します。いくつかの実験的テストでは、使用されるスペースは約 2N 個のアイテムであることが示されています。これは、O(N) スペースの使用量です。
以前の 2 つの配列をマージするたびに、新しい配列を作成する必要があるのではないでしょうか?
関数型プログラミング言語では、新しい配列があります。C では、入力配列を出力配列としても使用します。このコードは、元の入力配列を別の小さな配列にコピーし、それらの小さな配列を並べ替えて、並べ替えられた小さな配列を元の配列にマージします。
私のもう 1 つの質問は、配列の左側を分割する再帰の前に戻ることができるコードの手順です。これにより、右側で作業して 43 a 3 を取得し、それらをマージすることもできます。
分割プロセスにより、入力配列のコピーが作成されます (そのため、元のデータの情報は一時的に不要になります)。マージ プロセスは、(現在ソートされている) 分割された配列を元の配列にコピーします。(主に自分自身を繰り返します。 )
ソース
#include <stddef.h>
extern void merge_sort(int *array, size_t arrlen);
/* Debug */
#ifdef DEBUG
static void dump_array(const char *tag, int *array, size_t len);
static void enter_func(const char *func);
static void exit_func(const char *func);
#else
#define dump_array(t, a, l) ((void)0)
#define enter_func(f) ((void)0)
#define exit_func(f) ((void)0)
#endif
/*
function merge(left, right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end while
# You know that one of left and right is empty
# Copy the rest of the data from the other
while length(left) > 0
append first(left) to result
left = rest(left)
end while
while length(right) > 0
append first(right) to result
right = rest(right)
end while
return result
end function
*/
static void merge(int *left, size_t l_len, int *right, size_t r_len, int *output)
{
size_t r_pos = 0;
size_t l_pos = 0;
size_t o_pos = 0;
enter_func(__func__);
dump_array("Left:", left, l_len);
dump_array("Right:", right, r_len);
while (r_pos < r_len && l_pos < l_len)
{
if (right[r_pos] < left[l_pos])
output[o_pos++] = right[r_pos++];
else
output[o_pos++] = left[l_pos++];
}
while (r_pos < r_len)
output[o_pos++] = right[r_pos++];
while (l_pos < l_len)
output[o_pos++] = left[l_pos++];
dump_array("Output:", output, r_len + l_len);
exit_func(__func__);
}
/*
function merge_sort(m)
if length(m) ≤ 1
return m
var list left, right, result
var integer middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after middle
add x to right
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result
*/
void merge_sort(int *array, size_t len)
{
if (len <= 1)
return;
int left[(len+1)/2];
int l_pos = 0;
int right[(len+1)/2];
int r_pos = 0;
size_t mid = len / 2;
enter_func(__func__);
dump_array("Input:", array, len);
for (size_t i = 0; i < mid; i++)
left[l_pos++] = array[i];
for (size_t i = mid; i < len; i++)
right[r_pos++] = array[i];
dump_array("Left:", left, l_pos);
dump_array("Right:", right, r_pos);
merge_sort(left, l_pos);
merge_sort(right, r_pos);
merge(left, l_pos, right, r_pos, array);
dump_array("Result:", array, len);
exit_func(__func__);
}
/* Test code */
#include <stdio.h>
#ifdef DEBUG
static void enter_func(const char *func)
{
printf("-->> %s\n", func);
}
static void exit_func(const char *func)
{
printf("<<-- %s\n", func);
}
#endif
/* dump_array is always used */
#undef dump_array
static void dump_array(const char *tag, int *array, size_t len)
{
printf("%-8s", tag);
for (size_t i = 0; i < len; i++)
printf(" %2d", array[i]);
putchar('\n');
}
int main(void)
{
int array[] = { 38, 27, 43, 3, 9, 82, 10 };
size_t arrlen = sizeof(array) / sizeof(array[0]);
dump_array("Before:", array, arrlen);
merge_sort(array, arrlen);
dump_array("After:", array, arrlen);
return 0;
}
サンプル出力
非デバッグ
Before: 38 27 43 3 9 82 10
After: 3 9 10 27 38 43 82
デバッグ
Before: 38 27 43 3 9 82 10
-->> merge_sort
Input: 38 27 43 3 9 82 10
Left: 38 27 43
Right: 3 9 82 10
-->> merge_sort
Input: 38 27 43
Left: 38
Right: 27 43
-->> merge_sort
Input: 27 43
Left: 27
Right: 43
-->> merge
Left: 27
Right: 43
Output: 27 43
<<-- merge
Result: 27 43
<<-- merge_sort
-->> merge
Left: 38
Right: 27 43
Output: 27 38 43
<<-- merge
Result: 27 38 43
<<-- merge_sort
-->> merge_sort
Input: 3 9 82 10
Left: 3 9
Right: 82 10
-->> merge_sort
Input: 3 9
Left: 3
Right: 9
-->> merge
Left: 3
Right: 9
Output: 3 9
<<-- merge
Result: 3 9
<<-- merge_sort
-->> merge_sort
Input: 82 10
Left: 82
Right: 10
-->> merge
Left: 82
Right: 10
Output: 10 82
<<-- merge
Result: 10 82
<<-- merge_sort
-->> merge
Left: 3 9
Right: 10 82
Output: 3 9 10 82
<<-- merge
Result: 3 9 10 82
<<-- merge_sort
-->> merge
Left: 27 38 43
Right: 3 9 10 82
Output: 3 9 10 27 38 43 82
<<-- merge
Result: 3 9 10 27 38 43 82
<<-- merge_sort
After: 3 9 10 27 38 43 82