American flag sort

American flag sort

An efficient, in-place variant of radix sort that distributes items into hundreds of buckets. The first step counts the number of items in each bucket, and the second step computes where each bucket will start in the array. The last step cyclically permutes items to their proper bucket. Since the buckets are in order in the array, there is no collection step. The name comes by analogy with the Dutch national flag problem in the last step: efficiently partition the array into many "stripes". Using some efficiency techniques, it is twice as fast as quicksort for large sets of strings.
Note: This works especially well when sorting a byte at a time, using 256 buckets.

ee also

*Bucket sort

External links

*


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • American Airlines Flight 11 — AA 11 flight path from Boston to New York City Hijacking summary Date Tuesd …   Wikipedia

  • Flag Desecration Amendment — The Flag Desecration Amendment, often referred to as the flag burning amendment, is a controversial proposed constitutional amendment to the United States Constitution that would allow the United States Congress to statutorily prohibit expression …   Wikipedia

  • American imperialism — A 1900 Campaign poster for the Republican Party. The American flag has not been planted in foreign soil to acquire more territory but for humanity s sake. , President William McKinley, July 12, 1900.[1] On one hand, we see how the situation was… …   Wikipedia

  • Flag Desecration Amendment — Demonstranten in Washington Das Flag Desecration Amendment (Flaggenschändungsergänzung), auch als flag burning amendment bekannt, ist ein vorgeschlagener Zusatzartikel zur Verfassung der Vereinigten Staaten. Der neue Artikel würde den Kongress… …   Deutsch Wikipedia

  • Dutch national flag problem — Dutch national flag redirects here. For the flag, see Flag of the Kingdom of the Netherlands. The Dutch national flag problem is a famous computer science related programming problem proposed by Edsger Dijkstra. The flag of the Netherlands… …   Wikipedia

  • Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] …   Wikipedia

  • Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) …   Wikipedia

  • Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… …   Wikipedia

  • Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) …   Wikipedia

  • Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”