Tuesday, November 1, 2011

About American Flag Sort

American Flag Sort is an extension of Dutch Flag Problem which divides an array into three group. American Flag Sort further divides an array into multiple buckets based on certain order. For example, 256 buckets based on ASCII value. Essentially, it is a in-place radix sort. It is favored for sorting integers and strings givens its speed and space advantage.

  • The algorithm needs two passes. First scan the array, so that we know the number of the the objects that will be stored in each bucket.
  • Then we know the start location of each bucket. Scan the array for the second time, put the object to the corresponding bucket and update the bucket cursor.
  • If sorting strings, may need to apply the same algorithm to sort objects within each bucket.

1 comment:

  1. Here is complete description of Heap Sort Algorithm with example and screenshots
    http://geeksprogrammings.blogspot.in/2013/08/explain-heapsort-with-example.html

    Code for Bubble Sort with explanation
    http://geeksprogrammings.blogspot.in/2012/10/blog-post_20.html

    Selection sort with code and explanation
    http://geeksprogrammings.blogspot.in/2012/10/blog-post_511.html

    ReplyDelete