Talk:Quicksort (Visual Basic .NET)

From LiteratePrograms
Jump to: navigation, search

[edit] 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)

[edit] 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)
hijacker
hijacker
hijacker
hijacker