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 d开发者_JAVA百科oes not faciliate this scenario, what would be a good technique to do this? This is hypothetical but worthwhile asking.

Thanks

There's very thorough coverage of this on Wikipedia: http://en.wikipedia.org/wiki/Sorting_algorithm

It has a long list of common algorithms, and information about their advantages and disadvantages.

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:

• a comparison sort, where the comparison compares lexicographically
• an MSD radix sort.

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.

The steps are the same as writing any sorting algorithm. Create a comparison function. Then using what ever sorting algorithm is appropriate which in most cases is quicksort. For the comparison function you will have to assign a numeric value to each letter and then compare the letters by rank. This will give you a lexigraphic sort but thats what I assume you meant any way.

Basically, the answer to your question is to understand how Sorting works. A good reference would be Jonathan Shewchuk's video lectures on the same.

Give three hours and you are on track with the fundamentals. :)

Use a Trie =)

There's a really good tool on the internet for this kind of question

As you haven't found it, here's a good starting point: quicksort