var QuickSort = {

  // sortable has to be an abstract object that provides the following properties and functions:
  // Size: integer N
  // Compare: function( i, j )
  // Swap: function( i, j )
  //
  // Compare(i,j) sould return -1 if element i has to be in before element j, 
  //   +1 in the other case or 0 if elements are the same.
  // Swap(i,j) must swap two elements

  Sort: function( sortable ) {
    if (sortable.Size <= 0) return;
    this.SortRange( sortable, 0, sortable.Size-1 );
  },

  SortRange: function( sortable, lo, hi ) {
    var i = lo;
    var j = hi;
    var x = Math.floor((lo+hi)/2);
    while (i <= j) {
      while (i != x && sortable.Compare(i,x) < 0) i++;
      while (j != x && sortable.Compare(j,x) > 0) j--;
      if (i <= j) {
        if (i != j) {
          sortable.Swap( i, j );
          if (i == x) {
            x = j;
          } else if (j == x) {
            x = i;
          }
        }
        i++;
        j--;
      }
    }
    // recursion
    if (lo < j) {
      this.SortRange( sortable, lo, j );
    }
    if (i < hi) {
      this.SortRange( sortable, i, hi );
    }
  },
};

Anwendungsbeispiel QuickSort

Das folgende Objekt implementiert die Sortable Schnittstelle, welche der obige QuickSort Algorithmus verlangt. Daher kann dieses Objekt direkt an die Sort-Funktion übergeben werden, welche die Items IxList und DistList des Objektes sortiert.

var SortedGeoData = {
  Size: 0,
  IxList: [],
  DistList: [],

  Create: function( camPos ) {
    // creates display list for GeoData array
    for (var i = 0; i < GeoData.length; i++) {
      var dataPoint = GeoData[i];
      this.IxList[i] = i;
      this.DistList[i] = V3.Length( V3.Sub( camPos, dataPoint.Pos ) );
    }
    this.Size = GeoData.length;
    QuickSort.Sort( this );
  },

  Compare: function( i, j ) {
    if (this.DistList[i] == this.DistList[j]) return 0;
    return (this.DistList[i] > this.DistList[j]) ? -1 : 1;
  },

  Swap: function( i, j ) {
    var tmp = this.IxList[i];
    this.IxList[i] = this.IxList[j];
    this.IxList[j] = tmp;
    var tmp = this.DistList[i];
    this.DistList[i] = this.DistList[j];
    this.DistList[j] = tmp;
  },

};