Archive for August, 2009

CSortedArray / CSortedArrayEx v1.40

August 11, 2009 Comments off

Just to let everyone know that v1.40 of CSortedArray / CSortedArryEx has been released. Updates for this version include:

  • Following testing of the Sort method to ensure correctness, this method has been completely reimplemented. When using the functor version of this method, it is now nearly 20% faster compared to the previous version as well as addressing some sorting errors for specific arrays.
  • Fixed a bug in UniqueSort where it incorrectly used the pointer returned by GetData when calling the comparison function. If you called UniqueSort with a nHighIndex < GetUpperBound() for the array then the value returned by GetData could become corrupt if the array was realloc’ed.
  • Addition of an IsSorted simple helper method
  • Updated the code in the test app to better exercise the functionality of the class
  • Please note that since the implementation of the Sort method is implemented recursively, you can run out of Win32 stack space if you use the code to sort extra large sized arrays. Some informal testing indicates that with a standard Win32 1 MB stack, you will hit a stack overflow with an array containing random values from 0 to 1000 at roughly 2.9 million elements. Bear in mind that the amount of stack space used will depend on the actual values and their positions in your arrays. You will need to be aware of this issue if you will be using the code for array sizes upwards of a few
    hundred thousand. I may consider reimplementing the code to avoid using the Win32 stack to implement the recursion if anyone things this would be a useful addition.
  • Addition of a StableSort method. Unlike the "Sort" method which internally uses the quicksort algorithm which is not stable, StableSort internally uses an insertion sort algorithm which is. Thanks to "yv" for prompting this update.
Categories: Web Site Updates