C++/CLI「επιστημηさんまで私を忘れたのですか？」
書いてみた...つか、C#版を機械的にportしただけ。
using namespace System;
using namespace System::Collections::Generic;
// 二つのキューをマージ(併合)して一つにする
generic<typename T> where T : IComparable<T>
void merge(Queue<T>^ in_q1, Queue<T>^ in_q2, ICollection<T>^ out_c) {
// 入力である二つのキューが共に要素を持っている間
while ( in_q1->Count != 0 && in_q2->Count != 0 ) {
// より小さい要素を取り出して出力する
out_c->Add(( in_q1->Peek()->CompareTo(in_q2->Peek()) < 0 )? in_q1->Dequeue():in_q2->Dequeue());
}
// キューに残る(取り出されなかった)要素を出力する
while ( in_q1->Count != 0 ) { out_c->Add(in_q1->Dequeue()); }
while ( in_q2->Count != 0 ) { out_c->Add(in_q2->Dequeue()); }
}
// 一つの入力列を二つのキューに分割する
generic<typename T> where T : IComparable<T>
bool split(ICollection<T>^ in_c, Queue<T>^ out_c1, Queue<T>^ out_c2) {
T last;
Queue<T>^ out_c = out_c1;
bool switched = false;
for each ( T current in in_c ) {
// 直前の要素より小さな要素を読み込んだら出力キューを切り替える
if ( last != nullptr && current->CompareTo(last) < 0 ) {
out_c = (out_c == out_c1) ? out_c2 : out_c1;
}
out_c->Enqueue(last = current);
// 一度でも切り替えが起こったらswitchedをtrueにする
if ( !switched ) switched = (out_c == out_c2);
}
return switched;
}
generic<typename T>
void print(String^ head, IEnumerable<T>^ collection) {
Console::Write("{0} : ", head);
for each ( T item in collection ) {
Console::Write("{0} ", item);
}
Console::WriteLine();
}
generic<typename T> where T : IComparable<T>
void merge_sort(ICollection<T>^ data) {
Queue<T>^ q1 = gcnew Queue<T>();
Queue<T>^ q2 = gcnew Queue<T>();
while ( split(data, q1, q2) ) {
Console::WriteLine(L"--------------------------------");
print(L"input ", data);
Console::WriteLine("split:");
print(L"queue1 ", q1);
print(L"queue2 ", q2);
data->Clear();
merge(q1, q2, data);
Console::WriteLine(L"merge:");
print(L"output ", data);
q1->Clear();
q2->Clear();
}
}
int main() {
List<int>^ data = gcnew List<int>(gcnew array<int> { 1, 3, 2, 5, 4, 7, 6, 9, 8, 0, 13, 12, 11 });
merge_sort(data);
Console::WriteLine(L"--------------------------------");
print(L"result ", data);
}