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:
“There exists in a great part of the Northern people a gloomy diffidence in the moral character of the government. On the broaching of this question, as general expression of despondency, of disbelief that any good will accrue from a remonstrance on an act of fraud and robbery, appeared in those men to whom we naturally turn for aid and counsel. Will the American government steal? Will it lie? Will it kill?—We ask triumphantly.”
—Ralph Waldo Emerson (1803–1882)
“By the rude bridge that arched the flood,
Their flag to April’s breeze unfurled,
Here once the embattled farmers stood
And fired the shot heard round the world.”
—Ralph Waldo Emerson (1803–1882)
“Histories of the world omitted China; if a Chinaman invented compass or movable type or gunpowder we promptly “forgot it” and named their European inventors. In short, we regarded China as a sort of different and quite inconsequential planet.”
—W.E.B. (William Edward Burghardt)