M
Majnu
Hi community,
just in case somebody needs a shellsort in c#, I rewrote the pascal
code that I found in another newsgroup. Here are both. For more
explanation on the pascal code you can search for the post on google.
I was interested in the shell sort because I needed to sort long lists
of data that may already be in order. For that reason I didn't want to
use the arraylist's sort method, which uses quick sort (and has a
worst case for lists that are already in order). However, I found out
that the shell sort performs slower than the arraylist's sort method,
even for ordered lists with 1000000 members. I guess this is because
the sort method is hard wired into c#, but I'm not sure.
Anyway, here it is:
public static void shellSort(IList list, int first, int n, IComparer
comparer)
{
int dummyRemainder; // not needed but required by System.Math.DivRem
int incr = System.Math.DivRem((n * 10), 17, out dummyRemainder);
int last = n - 1 + first;
while(incr > 0)
{
for(int i = first; i <= (last - incr); i++)
{
int j = i;
while((j >= first) &&
(comparer.Compare(list[j], list[j + incr]) > 0))
{
listSwap(list, j, j + incr);
j -= incr;
}
}
incr = System.Math.DivRem((incr * 10), 17, out dummyRemainder);
}
}
private static void listSwap(IList list, int i, int j)
{
object o = list;
list = list[j];
list[j] = o;
}
Procedure ShellSort(first,n:integer;InOrder:CompareFunc;
Swap:SwapProc);
var i,j,incr,last:integer;
Begin
incr:=longint(n)*10 div 17;
last:=n-1+first;
while incr>0 do begin
for i:=first to last-incr do begin
j:=i;
while (j>=first) and Not InOrder(j,j+incr) do begin { Short
circuit! }
Swap(j,j+Incr);
dec(j,incr);
End
End;
incr:=longint(incr)*10 div 17;
End;
End;
just in case somebody needs a shellsort in c#, I rewrote the pascal
code that I found in another newsgroup. Here are both. For more
explanation on the pascal code you can search for the post on google.
I was interested in the shell sort because I needed to sort long lists
of data that may already be in order. For that reason I didn't want to
use the arraylist's sort method, which uses quick sort (and has a
worst case for lists that are already in order). However, I found out
that the shell sort performs slower than the arraylist's sort method,
even for ordered lists with 1000000 members. I guess this is because
the sort method is hard wired into c#, but I'm not sure.
Anyway, here it is:
public static void shellSort(IList list, int first, int n, IComparer
comparer)
{
int dummyRemainder; // not needed but required by System.Math.DivRem
int incr = System.Math.DivRem((n * 10), 17, out dummyRemainder);
int last = n - 1 + first;
while(incr > 0)
{
for(int i = first; i <= (last - incr); i++)
{
int j = i;
while((j >= first) &&
(comparer.Compare(list[j], list[j + incr]) > 0))
{
listSwap(list, j, j + incr);
j -= incr;
}
}
incr = System.Math.DivRem((incr * 10), 17, out dummyRemainder);
}
}
private static void listSwap(IList list, int i, int j)
{
object o = list;
list = list[j];
list[j] = o;
}
Procedure ShellSort(first,n:integer;InOrder:CompareFunc;
Swap:SwapProc);
var i,j,incr,last:integer;
Begin
incr:=longint(n)*10 div 17;
last:=n-1+first;
while incr>0 do begin
for i:=first to last-incr do begin
j:=i;
while (j>=first) and Not InOrder(j,j+incr) do begin { Short
circuit! }
Swap(j,j+Incr);
dec(j,incr);
End
End;
incr:=longint(incr)*10 div 17;
End;
End;