Graal Forums

Graal Forums (https://forums.graalonline.com/forums/index.php)
-   Code Gallery (https://forums.graalonline.com/forums/forumdisplay.php?f=179)
-   -   Boyer-Moore-Horspool, Quicksort, and Introsort (https://forums.graalonline.com/forums/showthread.php?t=81279)

WhiteDragon 08-17-2008 03:04 AM
Boyer-Moore-Horspool, Quicksort, and Introsort
 
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.

DrakilorP2P 08-23-2008 06:27 PM
This thread evidence that people want pretty screenshots rather than clever coding.

Chompy 08-23-2008 08:34 PM
Quote:
Originally Posted by DrakilorP2P (Post 1416802)
This thread evidence that people want pretty screenshots rather than clever coding.
Yup, screenshots and/or examples :]

LoneAngelIbesu 08-23-2008 08:39 PM
Quote:
Originally Posted by DrakilorP2P (Post 1416802)
This thread evidence that people want pretty screenshots rather than clever coding.
I can't help if this is esoteric. :cry:

Novo 11-22-2008 08:07 AM
These don't look ready for use.

You still have debug information in them (Such as player.chat @= "Stuff") as well as what I think is violating variable scope. (Such as using temp.a without having temp.a defined in the function).

Otherwise, it's good work. :)

Novo 11-22-2008 09:03 AM
Hope you don't mind, I did some edits to the quicksort! I added the ability to compare any object using a custom function.

PHP Code:
/**
  * Compares two values and returns a value that represents an order.
  *
  * If A < B, output is negative
  * If A == B, output is zero
  * If A > B, output is positive
  *
  * @param object First element to compare
  * @param object Second element to compare
  */
function default_cmp( sideA, sideB ) {
  return (sideA - sideB);
}

/**
  * Adaptor method for quicksort.
  *
  * @param array The array to be sorted.
  * @param function The function that compares two elements
  */
function quicksort(array, compare_function ) {
  this.cmp = ( temp.compare_function == null ? this.default_cmp : temp.compare_function );
  qsort(array, 0, array.size()-1, compare_function);
}

/**
  * 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
  * @param function The function that compares two elements
  */
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 );
  }
  return temp.array;
}

/**
  * 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
  * @param function The function that compares two elements
  */
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 ( cmp( temp.array[temp.i], temp.pivotValue ) <= 0 ) {
      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;
} 
This allows you to actually sort multi-dimensional array with specific indexes (or objects with values):

PHP Code:
  temp.compare_function = function(a,b){
    return (a[0] - b[0]);
  };

  quicksort( initial_list, temp.compare_function ); 
Or decreasing order:

PHP Code:

  temp.compare_function = function(a,b){
    return (b - a);
  };

  quicksort( initial_list, temp.compare_function ); 
Or whatever way you wish to sort.

WhiteDragon 11-23-2008 06:02 AM
Ah, I didn't realize I left those in there, I guess I put on an older version. It works entirely though.

And personally I would have passed around the compare function, but good job. You added some extra @params in the functions though.


All times are GMT +2. The time now is 11:58 PM.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2026, vBulletin Solutions Inc.
Copyright (C) 1998-2019 Toonslab All Rights Reserved.