Dart - 探索とソート(バブルソート(bubble 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-4.をDartで解いてみる。

その他参考書籍

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

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

コード

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';
    List<num> bubbleSort1(Iterable<num> sequence){
      List<num> result = sequence.toList();
      int i = result.length - 1;
      pre.text += '$result\n';
      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;
          pre.text += '$result\n';
        }
        i = result.length - 1;
      }
      return result;
    }
    List<num> sequence = [6,5,4,3,7,1,2];
    bubbleSort1(sequence);
    pre.text += 'test\n';
    for (List l in [['空のリスト', [], []], ['要素が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]]]){
      pre.text += test(l[1], l[2]) ? 'true\n' : '${l[0]}\n';
    }
  });
  clear.onClick.listen((MouseEvent event) => pre.text = '');
}

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;
}

bool test(List<num> original, List<num> expected){
  int i;
  List<num> result = bubbleSort(original);
  int max = result.length;
  if (max != expected.length){
    return false;
  }
  for(i = 0; i < max; i += 1){
    if (result[i] != expected[i]){
      return false;
    }
  }
  return true;
}