Press question mark to see available shortcut keys


Discover
Join Google+
Send feedback
Help
©2019 Google • Privacy Policy • Terms of Service • Maps Terms


Has the words
From
Anyone
Me
Not Me
Specific person...
Enter a name
Has

Attachments

Videos

Photos & images

Links

Text documents

Presentations

Spreadsheets

Forms

Polls
Date
Any time
Today
Yesterday
Last 7 days
Last 30 days
Last 90 days
Custom...
Between:
YYYY-MM-DD

YYYY-MM-DD

Commenter
Me
Not Me
Specific person...
Enter a name
In
Anywhere
Any community
Any collection
Specific community...
Specific collection...
Search Communities
Search Collections
Mentions
Me
Specific person...
Enter a name
Search
Reset
Learn More

Sign in
Ryan Marcus
ProgrammingGeneral Discussion
Jul 1, 2013

Just wanted to share an interesting trick I found for quickly sorting small sets -- it greatly outperforms the standard qsort function!

http://rmarcus.info/?p=641
Fallthrough Sort: Quickly Sorting Small Sets | RMarcus.info
In many applications, such as a median filter, we want to sort a small ( n < 30 ) set of numbers. In the case of the median filter, we are only concerned with sorting sets of one exact size -- if this is the case, one can generate an optimal sorting network using a tool like this one to create a ...
rmarcus.info
3 comments
3
2 plus ones
2
one share
1
Shared publicly•View activity
  • Lars Fosdal's profile photo
    Lars Fosdal
    Does it beat Shell's sort?
    Jul 2, 2013
  • Ryan Marcus's profile photo
    Ryan Marcus
    From a quick side-by-side, it definitely beats a "traditional" implementation of Shellsort (one with loops / branching). A "hard-coded" Shellsort, in my quick side-by-side comparison, doesn't perform any better or worse, likely because the same number of swaps are being performed, but in a different order.
    Jul 2, 2013
  • Lars Fosdal's profile photo
    Lars Fosdal
    I know that Shell's doesn't degrade on sorted or partially sorted lists, like quicksort.  But - I've seen at least three different implementations of Shell's - and they don't perform equally.

    pseudo pascal

    procedure Sort(var Item:Array of Double; Count:Integer)
    // - Shell's Sort
    var
      CurrItem : Double;
      h,i,j    : Integer;
    begin
      h := 1;
      repeat
        h := 3 * h + 1;
      until h > Count;
      repeat
        h := h DIV 3;
        for i := h + 1 to Count
        do begin
          CurrItem := Item[i];
          j := i;
          while Item[j-h] > CurrItem
          do begin
            Item[j] := Item[j-h];
            j := j - h;
            if j <= h
             then Break;
          end;
          Item[j] := CurrItem;
        end;
      until h = 1;
    end; 
    Jul 2, 2013
Add a comment...