- 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.
This is a blog for interview questions. The questions are primarily from certain web forums, BBS or books. The owner of this blog doesn't claim any copyright of those questions. The blog is established primarily to help the blog owner prepare job interviews.
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.
Subscribe to:
Post Comments (Atom)
Here is complete description of Heap Sort Algorithm with example and screenshots
ReplyDeletehttp://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