Warning: Declaration of Suffusion_MM_Walker::start_el(&$output, $item, $depth, $args) should be compatible with Walker_Nav_Menu::start_el(&$output, $item, $depth = 0, $args = Array, $id = 0) in /homepages/4/d153601691/htdocs/natebird/wp-content/themes/suffusion/library/suffusion-walkers.php on line 39

Linear-Time Sort

 computer science  No Responses »
Mar 042013
 

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 47

Warning: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead in /homepages/4/d153601691/htdocs/natebird/wp-content/plugins/latex/latex.php on line 49

Sorting.  That perennial problem that forms the backbone of every introductory Algorithms class.  Now, hardly anyone ever has to code up their own sorting algorithm, as great implementations are included in the standard libraries for every language worth naming.  But, ask anyone who passed an algorithms class in college which particular sorting algorithm to use on a large unsorted array of real numbers, and they would probably answer Quicksort or some other algorithm.  Give this hypothetical computer scientist a half hour and they would most likely be able to produce a reasonable facsimile of Quicksort on the whiteboard, even if they had not thought about it since their college days.

But sorting algorithms are not the end of sorting.  There is a certain class of sorting problems that can run faster.  Much faster.  In certain circumstances, you can sort an array in .  That's linear time!  The speedup over naively using Quicksort on these problems is immense.

So how does linear sort work?  The central concept goes back to one of my favorite topics in algorithms--techniques that trade memory space for speed.  The restriction for linear sort is that it can only be done when the numbers being sorted are both bound and countable.  An example of such a set of numbers is integers within some defined range.  Instead of shuffling items around an array like is done in Quicksort, the linear sorting algorithm creates a new array to keep a count of each of the numbers in the source range encountered, and then using these counts to create the final sorted array.

Let us now add some specificity to this discussion.  We will start with an unsorted array in which every item is an integer in the range .  We define our new array of counts over the range . Finally, we return the sorted array .

Here is the pseudocode for this algorithm:

Linear-Sort 
    
    
    

    = new array

    for each 
        
    end

    = new array of size 
    
    
    while 
        if 
            
            
            
        else
            
        end
    end

    return 
end

The code above starts by finding some information about the unsorted array , and then create the array of counts .  After that, we have a loop which goes through all elements of and increments each count in as needed.  Finally, we have the last loop which goes through all elements in to create the output array .  Overall, the runtime of the entire algorithm is then .

Of course, we are sacrificing space to get this linear runtime.  We can see that we need an length array to hold the counts.  Therefore, the memory space required is as well.

A few final thoughts:

  • I glossed over the array indexing for to make the algorithm description readable.  It's unlikely that a programming language would support exactly what I have written above--you would instead have to create a mapping for the index from to and use that for indexing the array.
  • If the range is large compared to the number of items in the array , it probably makes sense to use a hash table instead of an array to keep track of the counts ( above).  That would save memory space since would be sparse.  It would also save time by shortening the length final loop that produces the output array .  Note that the exact space and time needed in this case ultimately rely on how the hash table being used is implemented, which is why I have not provided a final Big-O.
  • For another example of trading memory space for speed, check out my post on dynamic programming.