Search code examples
algorithmsortingdata-structurespseudocode

Can Anyone provide the algorithm of Bead Sort with respect to string array?


As I'm unable to code it on java with the examples in integer values to String array. Please anyone could explain. Java would be better.


Solution

  • According to the Wikipedia article, the algorithm can only sort lists of positive integers and in the best case requires O(n^2) extra space.

    If you want to sort a list of strings with bead sort, you need some way to convert those strings to positive integers such that the relationships of the numbers exactly match the relationships among the strings. So if you have the strings "ABC", "JKL" and "XYZ", then the number you generate for "XYZ" has to be greater than the number you generate for "JKL", which has to be greater than the number for the string "ABC".

    That isn't a particularly difficult thing to do if your strings are all four bytes long (or shorter). Or even 8 bytes if you want to sort long integers: you just map each byte of the string to a byte in the integer. So "ABC" would become: 0x00414243.

    But in the general case, if your strings are longer than 8 bytes, coming up with that mapping would be more expensive than using a different sorting algorithm. Well, unless you wanted to use some special BigInteger class.

    Even then, the O(n^2) extra space is going to be a deal killer if you're trying to sort even a small array. Sorting an array of 32,000 integers would require four gigabytes of extra space.

    In short, with the description you've given, what you're asking to do is not reasonably possible.