import 'dart:math';

class Quick {

  void swap(List<int> arr, int i, int j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  int partition(List<int> arr, int pivot, int left, int right) {
    var pivotValue = arr[pivot];
    var partitionIndex = left;

    for (var i = left; i < right; i++) {
      if (arr[i] < pivotValue) {
        swap(arr, i, partitionIndex);
        partitionIndex++;
      }
    }

    swap(arr, right, partitionIndex);
    return partitionIndex;
  }

  void step(List<int> arr, int left, int right) {
    var pivot = null;
    var partitionIndex = null;

    if (left < right) {
      pivot = right;
      partitionIndex = partition(arr, pivot, left, right);

      step(arr, left, partitionIndex - 1);
      step(arr, partitionIndex + 1, right);
    }
  }

  void sort(List<int> arr) {
    var left = 0;
    var right = arr.length - 1;
    step(arr, left, right);
  }

}

String readableInt(int x) {
  var xS = x.toString().split('').reversed.join();
  var y = '';
  for (var i = 0; i < xS.length; i++) {
    if (i % 3 == 0 && i != 0) y += '.';
    y += xS[i];
  }
  return y.split('').reversed.join();
}

void main() {

  final quick = Quick();

  var x = 1000000000;

  var a = List.generate(x, (_) => Random().nextInt(x));

  var w = Stopwatch()..start();
  quick.sort(a);

  var items = readableInt(x);
  var ms = readableInt(w.elapsedMilliseconds);
  print('SORTED $items ITEMS IN $ms MS');
  w.stop();

}