[QuickSort] #algorithms

quick-sort.dart

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();

}

quick-sort.ts

class Quick {

  swap(arr: number[], i: number, j: number) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }

  partition(arr: number[], pivot: number, left: number, right: number) {
    var pivotValue = arr[pivot];
    var partitionIndex = left;

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

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

  step(arr: number[], left: number, right: number) {
    var pivot = null;
    var partitionIndex = null;

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

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

  sort(arr: number[]) {
    var left = 0;
    var right = arr.length - 1;
    this.step(arr, left, right);
  }

}

function readableInt(x: number): string {
  var xS = x.toString().split('').reverse().join('');
  var y = '';
  for (var i = 0; i < xS.length; i++) {
    if (i % 3 == 0 && i != 0) y += '.';
    y += xS[i];
  }
  return y.split('').reverse().join('');
}

const quick = new Quick();

const x = 1000;

const a = [];

for (let i = 0; i < x; i++) {
  a.push(Math.floor(Math.random() * x));
}

var start = Date.now();
quick.sort(a);
var end = Date.now();

var items = readableInt(x);
var ms = readableInt(end - start);
console.log('SORTED ' + items + ' ITEMS IN ' + ms + ' MS');

export { };