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
http://rmarcus.info/?p=641
- Does it beat Shell's sort?Jul 2, 2013
- 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
- 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