Shell sort for c#

[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[i];
list[i] = 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;

[Nicholas Paldino [.NET/C# MVP]]

Manju,

Your implementation is subject to a lot of boxing, so that could be part
of the perf degredation. You might get better results using a generic
method in .NET 2.0.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

"Majnu" <sp**@majnu.net> wrote in message
news:59**************************@posting.google.c om...

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[i];
list[i] = 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;

[Mike Kitchen]

Hi Manju

I have a few sort routines on my site that you may wish to look at. These
are tried and tested, and ported from C.
They include a shell sort routine which can be found at the following link
http://www.publicjoe.f9.co.uk/csharp/sort07.html

Hope this helps

Publicjoe
C# Tutorial at http://www.publicjoe.f9.co.uk/csharp/tut.html
C# Snippets at http://www.publicjoe.f9.co.uk/csharp/snip/snippets.html
C# Ebook at http://www.publicjoe.f9.co.uk/csharp/samples/ebook.html
VB Ebook at http://www.publicjoe.f9.co.uk/vbnet/samples/ebook.html

"Majnu" <sp**@majnu.net> wrote in message
news:59**************************@posting.google.c om...

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[i];
list[i] = 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;

[Jon Skeet [C# MVP]]

Majnu <sp**@majnu.net> wrote:

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.
The sort method is in no way hard wired into C#.
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);

If you don't need the remainder, why don't you just use

int incr = (n*10)/17;

That's unlikely to be the bottleneck, but it would be a good starting
point.

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

[Majnu]

Thanks for your input. How would a generic method look like in this
example? I do want to be able to sort ArrayLists of objects.

Greetings,
Majnu

"Nicholas Paldino [.NET/C# MVP]" <mv*@spam.guard.caspershouse.com> wrote in message news:<uP**************@tk2msftngp13.phx.gbl>...

Manju,

Your implementation is subject to a lot of boxing, so that could be part
of the perf degredation. You might get better results using a generic
method in .NET 2.0.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

[Jon Skeet [C# MVP]]

Majnu <sp**@majnu.net> wrote:

Thanks for your input. How would a generic method look like in this
example? I do want to be able to sort ArrayLists of objects.

If they're objects, it should be fine - there'll be no boxing involved.

(Your code itself doesn't do any boxing or unboxing, as far as I can
see.)

However, the fact that you're using IList might be causing performance
problems - ArrayList can just use its own internal array directly. Have
you tried (just for testing purposes) changing your parameter to be
object[] and measuring the performance in that situation?

--
Jon Skeet - <sk***@pobox.com>
http://www.pobox.com/~skeet
If replying to the group, please do not mail me too

[Majnu]

Thanks, I will give it a try.

Jon Skeet [C# MVP] <sk***@pobox.com> wrote in message news:<MP************************@msnews.microsoft. com>...

Majnu <sp**@majnu.net> wrote:

Thanks for your input. How would a generic method look like in this
example? I do want to be able to sort ArrayLists of objects.

If they're objects, it should be fine - there'll be no boxing involved.

(Your code itself doesn't do any boxing or unboxing, as far as I can
see.)

However, the fact that you're using IList might be causing performance
problems - ArrayList can just use its own internal array directly. Have
you tried (just for testing purposes) changing your parameter to be
object[] and measuring the performance in that situation?

[Majnu]

Mike,
Your sort methods look very useful. If I run into problems with quick
sort and already sorted lists I will try to use heap sort.

Majnu

"Mike Kitchen" <pu*******@hotmail.com> wrote in message news:<#W**************@TK2MSFTNGP10.phx.gbl>...

Hi Manju

I have a few sort routines on my site that you may wish to look at. These
are tried and tested, and ported from C.
They include a shell sort routine which can be found at the following link
http://www.publicjoe.f9.co.uk/csharp/sort07.html

Hope this helps

Publicjoe
C# Tutorial at http://www.publicjoe.f9.co.uk/csharp/tut.html
C# Snippets at http://www.publicjoe.f9.co.uk/csharp/snip/snippets.html
C# Ebook at http://www.publicjoe.f9.co.uk/csharp/samples/ebook.html
VB Ebook at http://www.publicjoe.f9.co.uk/vbnet/samples/ebook.html