Dart - 探索とソート(マージソード(merge sort)とそのテスト)

Dart: Up and Running
(O'Reilly Media)
Kathy Walrath Seth Ladd (著)
[Kindle版]
このブログでの感想

開発環境

• OS X Mavericks - Apple (OS)
• Dart Editor (開発環境)
• Dartium | Dart/ Structured web apps (ブラウザ, Dart VM 用 (Chromium with the Dart VM))
• Safari (ブラウザ, JavaScript 用)
• Dart (プログラミング言語)

初めてのコンピュータサイエンス(Jennifer Campbell、Paul Gries、Jason Montojo、Greg Wilson(著)長尾 高弘(翻訳))の11章(探索とソート)、11.7(練習問題)、11-9.をDartで解いてみる。

その他参考書籍

• What is Dart? [Kindle版] (O'Reilly Media) Kathy Walrath Seth Ladd (著) このブログでの感想

11.7(練習問題)、11-9.

コード

sample.dart

import 'dart:html';

void main() {
  InputElement run = querySelector('#run_dart');
  InputElement clear = querySelector('#clear');
  Element pre = querySelector('#pre0');
  run.onClick.listen((MouseEvent event){
    pre.text = '${window.navigator.userAgent}\n';
    testList.forEach((List s){
      List a = s[1];
      List b = s[2];
      mergeSort(a);
      pre.text += cmpList(a, b) ? 'true' : s.first;
      pre.text += '\n';
    });
  });
  clear.onClick.listen((MouseEvent event) => pre.text = '');
}

List merge(List s1, List s2){
  List new_s = [];
  int i1 = 0;
  int i2 = 0;
  
  while(true){
    if(i1 == s1.length){
      for(var x in s2.sublist(i2)){
        new_s.add(x);
      }
      break;
    }
    if (i2 == s2.length){
      for(var x in s1.sublist(i1)){
        new_s.add(x);
      }
      break;
    }
    if (s1[i1] <= s2[i2]){
      new_s.add(s1[i1]);
      i1 += 1;
    } else {
      new_s.add(s2[i2]);
      i2 += 1;
    }
  }
  return new_s;
}

void mergeSort(List s){
  List<List> workspace = [];
  int i;
  for(i = 0; i < s.length; i += 1){
    workspace.add([s[i]]);
  }
  i = 0;
  while(i < workspace.length - 1){
    var s1 = workspace[i];
    var s2 = workspace[i + 1];
    var new_s = merge(s1, s2);
    workspace.add(new_s);
    i += 2;
  }
  if (workspace.length != 0){
    s.replaceRange(0, s.length, workspace.last.sublist(0));
  }
}

bool cmpList(List s1, List s2){
  if(s1.length != s2.length){
    return false;
  }
  int i;
  for(i = 0; i < s1.length; i += 1){
    if(s1[i] != s2[i]){
      return false;
    }
  }
  return true;
}

List testList = [["空のリスト", [], []],
                 ["要素が1個のリスト", [1], [1]],
                 ["要素が2個でソート済のリスト", [1, 2], [1, 2]],
                 ["要素が2個で逆順になっているリスト", [2, 1], [1, 2]],
                 ["3個の等しい値によるリスト", [3, 3, 3], [3, 3, 3]],
                 ["異なる値が1つ混ざっているリスト", [3, 0, 3], [0, 3, 3]]];