Brunobkr/llama.cpp_AlgMor24_github

1/**2 * A classic Quicksort algorithm with Hoare's partition3 * - Works also on LinkedList objects4 *5 * Copyright: i-Vis Research Group, Bilkent University, 2007 - present6 */7 8const LinkedList = require('./LinkedList.js');9 10class Quicksort {11    constructor(A, compareFunction) {12        if(compareFunction !== null || compareFunction !== undefined)13            this.compareFunction = this._defaultCompareFunction;14 15        let length;16        if( A instanceof LinkedList )17            length = A.size();18        else19            length = A.length;20 21        this._quicksort(A, 0, length - 1);22    }23 24    _quicksort(A, p, r){25        if(p < r) {26            let q = this._partition(A, p, r);27            this._quicksort(A, p, q);28            this._quicksort(A, q + 1, r);29        }30    }31 32    _partition(A, p, r){33        let x = this._get(A, p);34        let i = p;35        let j = r;36        while(true){37            while (this.compareFunction(x, this._get(A, j)))38                j--;39            while (this.compareFunction(this._get(A, i), x))40                i++;41 42            if (i < j){43                this._swap(A, i, j);44                i++;45                j--;46            }47            else48                return j;49        }50    }51 52    _get(object, index){53        if( object instanceof LinkedList)54            return object.get_object_at(index);55        else56            return object[index];57    }58 59    _set(object, index, value){60        if( object instanceof LinkedList)61            object.set_object_at(index, value);62        else63            object[index] = value;64    }65 66    _swap(A, i, j){67        let temp = this._get(A, i);68        this._set(A, i, this._get(A, j));69        this._set(A, j, temp);70    }71 72    _defaultCompareFunction(a, b){73        return b > a;74    }75}76 77module.exports = Quicksort;