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:
“No slogan of democracy; no battle cry of freedom is more striving then the American parent’s simple statement which all of you have heard many times: ‘I want my child to go to college.’”
—Lyndon Baines Johnson (1908–1973)
“Swift blazing flag of the regiment,
Eagle with crest of red and gold,
These men were born to drill and die.
Point for them the virtue of slaughter,
Make plain to them the excellence of killing
And a field where a thousand corpses lie.”
—Stephen Crane (1871–1900)
“Here is this vast, savage, howling mother of ours, Nature, lying all around, with such beauty, and such affection for her children, as the leopard; and yet we are so early weaned from her breast to society, to that culture which is exclusively an interaction of man on man,—a sort of breeding in and in, which produces at most a merely English nobility, a civilization destined to have a speedy limit.”
—Henry David Thoreau (1817–1862)