Dart - 探索とソート(挿入ソート、選択ソートとバブルソートのパフォーマンスを比較)

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-5.をDartで解いてみる。

その他参考書籍

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

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

コード

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';
    pre.text += '選択ソート\n挿入ソート\nバブルソート\n';
    for(int l in [500, 5000, 6000, 7000, 8000, 9000]){
      List<num> nums = new List.generate(l, (int index) => l - index);
      print(nums);
      pre.text += printTimes(nums);
    }
  });
  clear.onClick.listen((MouseEvent event) => pre.text = '');
}

String printTimes(List<num> sequence){
  String result = '${sequence.length}\n';
  for(var f in [selectionSort, insertionSort, bubbleSort]){
    List<num> temp = sequence.toList();
    var t1 = new DateTime.now().millisecondsSinceEpoch;
    var a = f(sequence);
    var t2 = new DateTime.now().millisecondsSinceEpoch;
    result += '${t2- t1} ms\n';
  }
  return result;
}

List<num> selectionSort(List<num> sequence){
  List<num> result = sequence.toList();
  int i = 0;
  while(i != result.length){
    int smallest = findMin(result, i);
    num temp = result[i];
    result[i] = result[smallest];
    result[smallest] = temp;
    i += 1;
  }
  return result;
}

num findMin(List<num> sequence, int b){
  int smallest = b;
  int i = b + 1;
  while (i != sequence.length){
    if (sequence[i] < sequence[smallest]){
      smallest = i;
    }
    i += 1;
  }
  return smallest;
}

List<num> insertionSort(List<num> sequence){
  List<num> result = sequence.toList();
  int i = 0;
  while(i != result.length){
    insert(result, i);
    i += 1;
  }
  return result;
}

void insert(List<num> sequence, int b){
  int i = b;
  while (i != 0 && sequence[i - 1] >= sequence[b]){
    i -= 1;
  }
  num n = sequence[b];
  sequence.removeAt(b);
  sequence.insert(i, n);
}

List<num> bubbleSort(Iterable<num> sequence){
  List<num> result = sequence.toList();
  int i = result.length - 1;
  for(int b in new List.generate(result.length, (int index) => index)){
    while (i > b){
      if (result[i] < result[i - 1]){
        num temp = result[i];
        result[i] = result[i- 1];
        result[i - 1] = temp;
      }
      i -= 1;
    }
    i = result.length - 1;
  }
  return result;
}