Search code examples
algorithmlanguage-agnosticsortingprogramming-languages

Sorting a list of items by alphabetical order when the language has no function to do so?


If you would need to sort a list of items, but the programming language does not faciliate this scenario, what would be a good technique to do this? This is hypothetical but worthwhile asking.

Thanks


Solution

  • Two parts to the question:

    • how to sort
    • how to apply this to alphabetical sorting in general (aka lexicographical sorting).

    The two general types of sorting which are most appropriate for alphabetical sorting are:

    Comparison sorts are more common (partly because they're more general in what they can sort, partly because applying a radix sort to variable-length strings is slightly fiddly compared with a fixed-width radix sort). There are many to choose from with different trade-offs, but all treat the actual comparison of two items as a "black box" separate from the sort algorithm proper.

    So the remaining functionality needed is a lexicographic comparison. The way to compare two strings is to look at each character in turn until you find the first pair where they differ, and the left-hand string is "less" if this character is "less". If you don't find a difference then either the strings are the same length (in which case they're equal), or they aren't (in which case the shorter one is "less").

    If your character set is ASCII, then it's quite easy to compare characters in alphabetical order (either case-sensitive or case-insensitive). If your character set is full unicode, then you may need either language support, or a third-party library, or a very large table of character properties to get the exact alphabetical order you want.