Talk:Quicksort (Visual Basic .NET)

From LiteratePrograms

Pivot choice

Although median-of-3 is a popular pivot choice, I'd really recommend pseudo-random pivots. They're simpler to compute (just a CLR call) and are much less likely to encounter worst-case data, especially under an intentional attack. Deco 12:52, 6 June 2006 (PDT)

Ok, I have changed it to random. Ahy1 13:50, 6 June 2006 (PDT)

A bug in the partition algorithm showed up when I changed this. It seems like it doesn't work when using the first element as pivot. It would be nice if anyone could find out what is wrong. Ahy1 13:54, 6 June 2006 (PDT)

Actually the bug is in quicksort, believe it or not. I fixed it. Deco 14:07, 6 June 2006 (PDT)

Thanks. I don't know why I thought it was in partition. Ahy1 14:14, 6 June 2006 (PDT)

For some reason, this algorithm didn't work for me (I used it so sort Objects). I had to change it because the right element was not getting sorted at each iteration of quicksort(). To do that I change several two (right-1) to (right) and the (right-2) to (right-1). Then, I also had to change the element comparison criterion from "<=" to "<" to avoid infinite loops. I could post my new code or at least submit it for review...Let me know. And thanks anyways for this great help. Est 17:22, 22 March 2007 (ET)

The right argument to quicksort is supposed to be an index to the first element not in the range to be sorted. This means that if we do quicksort(a, 0, 5), the elements at indexes 0 to 4 are sorted and the one at 5 is not. This is the way algorithms are handled in C++, but it might not be the VB.NET way of doing it. So, should we change this or maybe just make it more clear in the article text? Any opinions? Ahy1 23:55, 22 March 2007 (PDT)

Randomisation pass

A problem with Quicksort is that performance can fall off considerably if the input is sorted or nearly sorted. In order to avoid this people often begin with a randomisation pass which just switches the items to random positions. That ensures that the algorithm sorts quickly in all cases albeit a little more slowly for the normal case. -- Derek Ross | Talk 21:27, 14 August 2006 (PDT)

Yes, this should probably be included in the code, or at least mentioned in the article. Ahy1 11:25, 15 August 2006 (PDT)

I have made an attempt at the randomisation code, but I don't currently have access to a Windows machine for testing. The code should be inserted in the beginning of the quicksort sub-routine.

       Dim i
       Dim ii
       For i=left to right-1
           ii=New System.Random().Next(left, right - 1)
           If i<>ii Then
               swap(a(i), a(ii))
           End If
       Next

Anyone care to test it? Ahy1 11:35, 15 August 2006 (PDT)

That was of course wrong. It should stay in qsort and look like this:

       Dim i
       Dim ii
       For i=0 to a.Length()-1
           ii=New System.Random().Next(0, a.Length()-1)
           If i<>ii Then
               swap(a(i), a(ii))
           End If
       Next

Ahy1 12:23, 15 August 2006 (PDT)

Looks good. Unfortunately I can't test it either because I only have VB6. -- Derek Ross | Talk 19:34, 15 August 2006 (PDT)

I finally got my hands on a Windows PC with VB.NET. The randomisation worked, and I have added it to the article. Ahy1 10:36, 17 August 2006 (PDT)

If anyone wants to work with VB.NET but can't afford Visual Studio, they should take a look at the SharpDevelop IDE. It is GPL and it handles C# and VB.NET. While Visual Studo has more features, SharpDevelop Version 2.x handles all the essentials. Definitely worth a look if you haven't come across it yet. -- Derek Ross | Talk 20:35, 23 March 2007 (PDT)