Hello!
I'm trying to speed up the quicksort algorithm to sort arrays of strings. As you might know, internally the algorithm compares two members of an array at a time, finding the lower and the greater. Probably Delphi does a scan comparison, checking each byte (word, dword, etc) until finding a difference, if no difference is found the scan will run until the end of both strings. Large strings would take a lot of processing to be compared. One of the ideas I have is compressing the strings using different methods like:
1. RLE (run-length encoding), but might not be a good idea since the strings I want to sort are mostly word-like (identifiers, file paths, etc) with very few characters repeating.
2. Limit the character set, using less bits to store a character. The comparison would not need to be bit-wise, as long as the symbols respect the order of ASCII, and each has the same size in bits, those can be compared in groups of byte, word, etc.
3. Some sort of Huffman compression, which stores the most common characters with less bits. But it should be designed in such way that allows byte groups comparisons, otherwise won't help.
Does anyone have other ideas to make a faster quicksort?
Bookmarks