Abstract
Calendar
Project Development
Findings and Contributions
Links and References
Return to EuropaTheoretically this algorithm should take linear time to sort an array of words (strings of characters);however, the sorting process needs to create a highly complex data structure in order to perform its job. This led to the belief that even though it would sort in linear time, the time and memory overhead involved in creating the required data structures would result in a very large constant, rendering the algorithm useless for practical applications.
This idea of impracticallity lead to the implementation using RESOLVE/C++ which is known to be highly inefficient in development of time critical code. What makes this language useful is the simplicity of the coding involved and the presence of various components that make it perfetf for rapid development.
The first implementation was completed in about a weeks time leading to a revelation that after all the algorithm is not as bad as I had initially assumed it to be. Even though the time constant involved was extremenly large, making the code useless for sorting a few items, it was ofset by the fact that the algorithm was linear, leading to shorter sorting times for a large number of words. When timed against the quicksort implementation present as a component in the RESOLVE Catalog it was found that the new algorithm could sort faster than quicksort when the number of items to be sorted was greater than 20,000.
Even though the this implementation seemed to be comparable to the quicksort in RESOLVE/C++, it was significantly slower than the Unix sort command. Applications developed in RESOLVE/C++ are known to be inefficient because of the extreme complexity aquired by making the code more general and easier to read and mantain. Also since the algoritm required building of a massive tree structure it need to allocate memory very often. This would lead to fragmentation which added on to the ineffciency. Furthermore the recursion was used in the implementation which is not efficient. This led to a new implementation using ANSI C in which recursion was avoided and memory management was made more efficient by allocating large amounts of memory at a time.
The C implementation resulted in a code that was lot faster than the RESOLVE/C++ implementaion of the algorithm. It is also comparable to the unix sort command in the amount of time it takes to sort words using ASCII ordering.
Comparing the timing results of the RESOLVE/C++ implemenation and the one using C led me to conclude that RESOLVE/C++ was indeed very inefficient compared to C/C++. This led me into my next project which dealt with finding out what slowes down RESOLVE/C++ and if possible to find out means to improve it.