Just some random algorithms I coded into GScript awhile ago.
I'm pretty sure they are never going to be used on Classic, so I'll just post them here.
Boyer-Moore-Horspool
PHP Code:
//#CLIENTSIDE
/**
* Finds the first occurrence of a pattern P in search string
* T using the Boyer-Moore-Horspool string search algorithm
* (I didn't code the second table for a full Boyer-Moore).
*
* Returns -1 if no match.
*
*
* Average Case Complexity of O(mn).
* Worst Case of O(n**2) if m==n.
* m = pattern length
* n = search string length
*
*
* @param string The search string
* @param string The pattern
* @return int The position of the first occurrence of pattern
*/
function boyer_moore(T, P) {
temp.last = last_table(P);
player.chat = temp.last;
temp.n = T.length();
temp.m = P.length();
temp.i = temp.m-1;
temp.j = temp.m-1;
do {
if (P.charat(temp.j) == T.charat(temp.i)) {
if (temp.j == 0) {
return temp.i; // Matched
} else {
temp.i--;
temp.j--;
}
} else {
player.chat = temp.j SPC temp.i SPC P.charat(temp.j) SPC T.charat(temp.i);
temp.i = temp.i + temp.m - min(temp.j, 1 + temp.last[getascii(T.charat(temp.i))]);
temp.j = temp.m - 1;
player.chat @= temp.j SPC temp.i SPC P.charat(temp.j) SPC T.charat(temp.i);
}
} while (temp.i <= temp.n);
return -1; // P does not exist in T
}
/**
* Generates an array of the last locations
* of each character in a string P.
*
* @param string
* @return array
*/
function last_table(P) {
temp.last = new [255];
for (temp.i=0; temp.i<P.length()-1; temp.i++)
temp.last[getascii(P.charat(temp.i))] = temp.i;
return temp.last;
}
Quicksort
PHP Code:
//#CLIENTSIDE
/**
* Adaptor method for quicksort.
*
* @param array The array to be sorted.
*/
function quicksort(array) {
qsort(array, 0, array.size()-1);
}
/**
* Sorts the array with the quicksort algorithm.
*
* Average Case Time Complexity of O(n log n).
* Worst Case Time Complexity of O(n**2).
* Average Case Space Complexity of O(log n).
* n = array size
*
* @param array The array to be sorted
* @param int The position of the left side of the array
* @param int The position of the right side of the array
*/
function qsort(temp.array, temp.left, temp.right) {
if (temp.right > temp.left) {
temp.pivotNewIndex = qsort_partition(temp.array, temp.left, temp.right, temp.left);
qsort(temp.array, temp.left, temp.pivotNewIndex - 1);
qsort(temp.array, temp.pivotNewIndex + 1, temp.right);
}
}
/**
* In-place parition algorithm. Paritions the portion of
* the array between indexs left and right, inclusively.
*
* @param array The array to be partitioned
* @param int The left bound
* @param int The right bound
* @param int The pivot index
*/
function qsort_partition(temp.array, temp.left, temp.right, temp.pivotIndex) {
temp.pivotValue = temp.array[temp.pivotIndex];
temp.s = temp.array[temp.right];
temp.array[temp.right] = temp.array[temp.pivotIndex];
temp.array[temp.pivotIndex] = temp.s;
temp.storeIndex = temp.left;
for (temp.i = temp.left; temp.i < temp.right; temp.i++) {
if (temp.array[temp.i] <= temp.pivotValue) {
temp.s = temp.array[temp.storeIndex];
temp.array[temp.storeIndex] = temp.array[temp.i];
temp.array[temp.i] = temp.s;
temp.storeIndex++;
}
}
temp.s = temp.array[temp.right];
temp.array[temp.right] = temp.array[temp.storeIndex];
temp.array[temp.storeIndex] = temp.s;
return temp.storeIndex;
}
Introsort
PHP Code:
//#CLIENTSIDE
this.threshold = 16;
/**
* Sorts an algorithm with the introspective sort algorithm.
* (Begins with quicksort and switchs to heapsort when
* the recursion depth exceeds a level based on the
* logarithm of the number of elements being sorted.)
*
* Uses median-of-3 pivot selection algorithm
*
* Average Case Time Complexity comparable to quicksort on typical data sets
* Worst Case Time Complexity of O(n log n)
*
* @param array The array to be sorted.
*/
function introsort(temp.a) {
this.a = temp.a;
introsort_loop(0, this.a.size(), 2*floor_lg(this.a.size()));
insertionsort(0, this.a.size());
return this.a;
}
function introsort_loop(temp.lo, temp.hi, temp.depth_limit) {
while (temp.hi - temp.lo > this.threshold) {
if (temp.depth_limit == 0) {
heapsort(temp.lo, temp.hi);
return;
}
temp.depth_limit--;
temp.p = partition(temp.lo, temp.hi, medianof3(temp.lo, temp.lo+((temp.hi - temp.lo)/2)+1, temp.hi-1));
introsort_loop(temp.p, temp.hi, temp.depth_limit);
temp.hi = temp.p;
}
}
function partition(temp.lo, temp.hi, temp.x) {
temp.i = temp.lo;
temp.j = temp.hi;
while (true) {
while (this.a[temp.i] < temp.x)
temp.i++;
temp.j--;
while (temp.x < this.a[temp.j])
temp.j--;
if (temp.i > temp.j)
return temp.i;
exchange(temp.i, temp.j);
temp.i++;
}
}
function medianof3(temp.lo, temp.mid, temp.hi) {
if (this.a[temp.mid] < this.a[temp.lo]) {
if (this.a[temp.hi] < this.a[temp.mid])
return this.a[temp.mid];
else {
if (this.a[temp.hi] < this.a[temp.lo])
return this.a[temp.hi];
else
return this.a[temp.lo];
}
} else {
if (this.a[temp.hi] < this.a[temp.mid]) {
if (this.a[temp.hi] < this.a[temp.lo])
return this.a[temp.lo];
else
return this.a[temp.hi];
} else
return this.a[temp.mid];
}
}
function heapsort(temp.lo, temp.hi) {
temp.n = temp.hi - temp.lo;
for (temp.i = temp.n/2; temp.i >= 1; temp.i--) {
downheap(temp.i, temp.n, temp.lo);
}
for (temp.i = temp.n; temp.i > 1; temp.i--) {
exchange(temp.lo, temp.lo + temp.i - 1);
downheap(1, temp.i-1, temp.lo);
}
}
function downheap(temp.i, temp.n, temp.lo) {
temp.d = this.a[temp.lo + temp.i - 1];
while (temp.i <= temp.n/2) {
temp.child = 2*temp.i;
if (temp.child < temp.n && this.a[temp.lo+temp.child-1] < this.a[temp.lo+temp.child])
temp.child++;
if (!temp.d < this.a[temp.lo+temp.child-1])
break;
this.a[temp.lo+temp.i-1] = this.a[temp.lo+temp.child-1];
temp.i = temp.child;
}
this.a[temp.lo + temp.i - 1] = temp.d;
}
function insertionsort(temp.lo, temp.hi) {
for (temp.i = temp.lo; temp.i < temp.hi; temp.i++) {
temp.j = temp.i;
temp.t = this.a[temp.i];
while (temp.j != temp.lo && temp.t < this.a[temp.j-1]) {
this.a[temp.j] = this.a[temp.j-1];
temp.j--;
}
this.a[temp.j] = temp.t;
}
}
function exchange(temp.i, temp.j) {
temp.t = this.a[temp.i];
this.a[temp.i] = this.a[temp.j];
this.a[temp.j] = temp.t;
}
function floor_lg(temp.a) {
return int(log(2.718281828459, temp.a)/log(2.718281828459, 2));
}
The sortbyvalue function uses heap sort, but is considerable faster since it's native. You should only use these sorts if you know your data set is very large to make up for the difference.
I coded a Boyer-Moore-Horspool because it's preprocessing time is considerably less than a Boyer-Moore even though a Boyer-Moore can achieve O(n). A Boyer-Moore only reaches faster times when you start reaching text sizes near the lengths of books.