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