sorting

sorting + pagination

by juvian

JavaScript

function SortingHelper(arr, compare) {


    this.cacheVals = [] // keep cache of items, might be expensive to calculate value for each comparisson
    this.indexes = [] // array of indices, we actually sort this array instead of arr

    this.update(arr) // change values

    this.customCompare = compare

    return this;
}

SortingHelper.prototype.data = function(){
	return this.arr;
}

SortingHelper.prototype.update = function(arr){
	this.arr = arr		
	this.cacheVals.length = this.arr.length
}

SortingHelper.prototype.getValues = function(from, to){
	return this.indexes.slice(from, to).map((idx) => this.arr[idx])
}

SortingHelper.prototype._compare = function(idx1, idx2) {
	this.cnt++
	//idx1 == idx2 && console.log(idx1, idx2)
	if(this.compareToUse(this.cacheVals[idx1],  this.cacheVals[idx2])) return 1;
	if(this.compareToUse(this.cacheVals[idx2],  this.cacheVals[idx1])) return -1;

	return idx1 < idx2;

}

SortingHelper.prototype.sort = function(from, to){
	this.quickSort(from, to);
}

SortingHelper.prototype.quickSort = function(from, to) {
	this.cnt = this.swaps = 0

	this.from = from == undefined ? 0 : from;
	this.to = to == undefined ? this.arr.length - 1 : to;

	this.compareToUse =  this.customCompare ? this.customCompare : (a, b) =>  a < b;

	var getValue = this.customValue ? this.customValue : (a) => a

	var oldLength = this.indexes.length

	this.cacheVals.length = this.indexes.length = this.arr.length

	for(var i = 0; i < this.arr.length; i++){
		this.cacheVals[i] = (getValue(this.arr[i], i)) 
	}

	for(var i = oldLength; i < this.arr.length; i++){
		this.indexes[i] = i;
	}

    this._quickSort(0, this.arr.length - 1, Math.max(Math.ceil(Math.log2(this.arr.length)) * 2, 5))

	console.log("comparissons", this.cnt, "swaps", this.swaps)

}

SortingHelper.prototype.insertionSort = function(left, right){ // interval [)
	for(var i = left + 1; i < right; i++){
		var tmp = this.indexes[i];
		var j = i;
		while(--j >= left && this._compare(tmp, this.indexes[j]) ==...