An american flag sort is an efficient, in-place variant of radix sort that distributes items into hundreds of buckets. Non-comparative sorting algorithms such as radix sort and american flag sort are typically used to sort large objects such as strings, for which comparison is not a unit-time operation.
American flag sort iterates through the bits of the objects, considering several bits of each object at a time. For each set of bits, american flag sort makes two passes through the array of objects: first to count the number of objects that will fall in each bin, and second to place each object in its bucket. This works especially well when sorting a byte at a time, using 256 buckets. With some optimizations, it is twice as fast as quicksort for large sets of strings.
The name comes by analogy with the Dutch national flag problem in the last step: efficiently partition the array into many "stripes".
Read more about American Flag Sort: Algorithm, Sample Implementation in Python
Famous quotes containing the words american, flag and/or sort:
“Indeed, I believe that in the future, when we shall have seized again, as we will seize if we are true to ourselves, our own fair part of commerce upon the sea, and when we shall have again our appropriate share of South American trade, that these railroads from St. Louis, touching deep harbors on the gulf, and communicating there with lines of steamships, shall touch the ports of South America and bring their tribute to you.”
—Benjamin Harrison (1833–1901)
““Justice” was done, and the President of the Immortals, in Æschylean phrase, had ended his sport with Tess. And the d’Urberville knights and dames slept on in their tombs unknowing. The two speechless gazers bent themselves down to the earth, as if in prayer, and remained thus a long time, absolutely motionless: the flag continued to wave silently. As soon as they had strength they arose, joined hands again, and went on.
The End”
—Thomas Hardy (1840–1928)
“Rice and peas fit into that category of dishes where two ordinary foods, combined together, ignite a pleasure far beyond the capacity of either of its parts alone. Like rhubarb and strawberries, apple pie and cheese, roast pork and sage, the two tastes and textures meld together into the sort of subtle transcendental oneness that we once fantasized would be our experience when we finally found the ideal mate.”
—John Thorne, U.S. cookbook writer. Simple Cooking, “Rice and Peas: A Preface with Recipes,” Viking Penguin (1987)