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

その他参考書籍

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

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

コード

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';
    int n = 10;
    List s1 = new List.generate(n, (int index) => index, growable:true);
    List s2 = new List.generate(n,(int index) => (n - 1) - index, growable:true);
    List s3 = new List.generate(n, (int index) => 0, growable:true);
    for(var f in [selectionSort, insertionSort]){
      for(List s in [s1, s2, s3]){
        List temp = f(s);
        int cmp = temp.first;
        int cp = temp[1];
        pre.text += '比較: ${cmp} コピー: ${cp}\n';
      }
    }
  });
  clear.onClick.listen((MouseEvent event) => pre.text = '');
}

List selectionSort(List sequence){
  int i = 0;
  int cmp = 0;
  int cp = 0;
  while (i != sequence.length){
    List temp = findMin(sequence, i, cmp);
    int smallest = temp.first;
    cmp  = temp[1];
    cp += 2;
    i += 1;
  }
  return [cmp, cp];
}

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

List insertionSort(List sequence){
  int i = 0;
  int cmp = 0;
  int cp = 0;
  while(i != sequence.length){
    List temp = insert(sequence, i, cmp, cp);
    cmp = temp.first;
    cp = temp[1];
    i += 1;
  }
  return [cmp, cp];
}

List insert(List sequence, int b, int cmp, int cp){
  int i = b;
  while(i != 0){
    cmp += 1;
    if(sequence[i - 1] >= sequence[b]){
      i -= 1;
    } else {
      break;
    }
  }
  var v = sequence.removeAt(b);
  sequence.insert(i, v);
  cp += 2;
  return [cmp, cp];
}