Experiments with sorting algorithms in Dart, from Wikipedia articles.

sortings.dart

import 'dart:math';

// http://en.wikipedia.org/wiki/Bubble_sort
void bubble(List list) {
  var n = list.length;
  
  while (n != 0) {
    var newn = 0;
    for (var i = 1; i < n; i++) {
      if (list[i-1] > list[i]) {
        var x = list[i-1];
        list[i-1] = list[i];
        list[i] = x;
        newn = i;
      }
    }
    n = newn;
  }
}

// also from wikipedia
void insertion(List list) {
  for (var i = 1; i < list.length; i++) {
    var x = list[i];
    var j = i;
    while (j > 0 && list[j-1] > x) {
      list[j] = list[j-1];
      j = j - 1;
    }
    list[j] = x;
  }
}

// http://en.wikipedia.org/wiki/Quicksort
// not good, creates two new growable lists
List quicksort(List list) {
  if (list.length <= 1) return list;
  var pivot = list.removeAt(list.length~/2);
  var less = [];
  var greater = [];
  list.forEach((x) => x <= pivot ? less.add(x) : greater.add(x));
  return quicksort(less)..addAll([pivot])..addAll(quicksort(greater));
}

// better
quicksort2(List list, [int left, int right]) {
  if (left == null) left = 0;
  if (right == null) right = list.length-1;
  
  if (left < right) {
    var pivotIndex = list.length ~/ 2;
    var pivotNewIndex = partition(list, left, right, pivotIndex);
    quicksort2(list, left, pivotNewIndex - 1);
    quicksort2(list, pivotNewIndex + 1, right);
  }
}

int partition(List list, int left, int right, int pivotIndex) {
  swap(list, a, b) {
    var x = list[a];
    list[a] = list[b];
    list[b] = x;
  }
  
  var pivotValue = list[pivotIndex];
  
  swap(list, pivotIndex, right);
  
  var storeIndex = left;
  
  for (var i = left; i < right; i++) {
    if (list[i] <= pivotValue) {
      swap(list, i, storeIndex);
      storeIndex += 1;
    }
  }
  
  swap(list, storeIndex, right);
  
  return storeIndex;
}

main() {
  var things = genList(30000);
  var things2 = new List.from(things, growable: false);
  var things3 = new List.from(things);
  var things4 = new List.from(things, growable: false);
  
  measure(() {
    bubble(things);
  });
  
  measure(() {
    insertion(things2);
  });
  
  measure(() {
    quicksort(things3);
  });
  
  measure(() => quicksort2(things4));
  //print(things4);
}

List genList(int size) {
  var list = new List(size);
  var rand = new Random();
  for (var i = 0; i < size; i++) {
    list[i] = rand.nextInt(size);
  }
  return list;
}

measure(func()) {
  var sw = new Stopwatch()..start();
  func();
  sw.stop();
  print(sw.elapsedMilliseconds);
}