vbScript Implementation of QuickSort

6 Years Ago Updated 6 Years Ago Reverend Jim 1 2K Views

Over the years I've seen a lot of discussion (and several implementations) of the Quicksort algorithm. Most of what I have seen, unfortunately, lacks sufficient commenting as well as meaningful variable names. Hopefully the following vbScript code will more clearly show how Quicksort actually works.

A couple of incidental notes:

I use PrimalScript for editing and I have comments set to display with a silver-grey background and black text. This makes comments very distinct from code (and is also why I have a closing single quote at the end of lines).
The test code section at the end executes only if I run the QuickSort.vbs file directly (a trick I learned from Python).

I keep all my common code in an include folder D:\Include with an envorment variable, %INCLUDE% set to that location. That way, the only code I have to duplicate is

Function Include ( ByVal file )
Dim wso: Set wso = CreateObject("Wscript.Shell")
Dim fso: Set fso = CreateObject("Scripting.FileSystemObject")
ExecuteGlobal(fso.OpenTextFile(wso.ExpandEnvironmentStrings(file)).ReadAll)
End Function

in any script that needs library code. I can do

Include "%INCLUDE%\QuickSort.vbs"

<edit>The sample code was edited to correct a bug, not in the actual quicksort algorithm, but in the comparison test passed to quicksort. The original test was "X1 <= X2" and it has been corrected to "X1 < X2".

ddanbe commented: Indeed, nicely commented +15

.
	''#region Header                                                                        '
    ''                                                                                      '
    ''  Name:                                                                               '
    ''                                                                                      '
    ''      QuickSort.vbs                                                                   '
    ''                                                                                      '
    ''  Description:                                                                        '
    ''                                                                                      '
    ''      Sort an array using the QuickSort algorithm.                                    '
    ''                                                                                      '
    ''  Usage:                                                                              '
    ''                                                                                      '
    ''      QuickSort(array,compare)                                                        '
    ''                                                                                      '
    ''          array:      a one dimensional array of data                                 '
    ''          compare:    one line of vbscript code which will evaluate to True           '
    ''                      if the first item of a pair <= the second item                  '
    ''                                                                                      '
    ''          Because QuickSort can be used to sort any type of data, you must provide    '
    ''          the smarts for how to compare two items. QuickSort can then create the      '
    ''          test function at run time. Your only restriction is that you must refer     '
    ''          to the two comparison values as X1 and X2.                                  '
    ''                                                                                      '
    ''  Example:                                                                            '
    ''                                                                                      '
    ''      arr = Array(19,3,17,42,-9)                                                      '
    ''      QuickSort arr, "X1 <= X2"                                                       '
    ''                                                                                      '
    ''  Audit:                                                                              '
    ''                                                                                      '
    ''      2018-02-15  rj  original code                                                   '
    ''                                                                                      '
    ''#endregion                                                                            '

    Sub QuickSort(arr(), Compare)

        'Create test function then call QuickSort2 to sort

        ExecuteGlobal "Function Test(X1, X2): Test = " & Compare & ": End Function"
        QuickSort2 arr, LBound(arr), UBound(arr)

    End Sub

    ''                                                                                      '
    Sub QuickSort2 (arr, arrMin, arrMax)

        Dim middle      'value of the element in the middle of the range    '
        Dim swap        'temporary item for the swapping of two elements    '
        Dim arrFrst     'index of the first element in the range to check   '
        Dim arrLast     'index of the last element in the range to check    '
        Dim arrMid      'index of the element in the middle of the range    '

        If arrMax <= arrMin Then Exit Sub

        'Start the checks at the lower and upper limits of the Array

        arrFrst = arrMin
        arrLast = arrMax

        'Find the midpoint of the region to sort and the value of that element

        arrMid = (arrMin + arrMax) \ 2
        middle = arr(arrMid)

        Do While (arrFrst <= arrLast)

            'Find the first element > the element at the midpoint

            Do While Test(arr(arrFrst), middle)
                arrFrst = arrFrst + 1
                If arrFrst = arrMax Then Exit Do
            Loop

            'Find the last element < the element at the midpoint

            Do While Test(middle, arr(arrLast))
                arrLast = arrLast - 1
                If arrLast = arrMin Then Exit Do
            Loop

            'Pivot the two elements around the midpoint if they are out of order

            If (arrFrst <= arrLast) Then
                swap = arr(arrFrst)
                arr(arrFrst) = arr(arrLast)
                arr(arrLast) = swap
                arrFrst = arrFrst + 1
                arrLast = arrLast - 1
            End If

        Loop

        'Sort sub-regions (recurse) if necessary

        If arrMin  < arrLast Then QuickSort2 arr, arrMin,  arrLast
        If arrFrst < arrMax  Then QuickSort2 arr, arrFrst, arrMax

    End Sub

    ''Test code                                                                             '
    If Lcase(Wscript.ScriptName) = Lcase("QuickSort.vbs") Then
        arr = Array(1,99,5,2,73,23,18,92,63,52,52,12,6)
        WScript.Echo Join(arr,vbTab)
        QuickSort arr, "X1 < X2"
        WScript.Echo Join(arr,vbTab)
    End If

tinstaafl 1,176 Posting Maven

6 Years Ago

There appears to be a bug in your code. When I run it as is the second line of output, isn't properly sorted. One of the 52's is swapped with the 63 and the 92 is swapped with the 73.

1   99  5   2   73  23  18  92  63  52  52  12  6
1   2   5   6   12  23  18  52  63  52  92  73  99

Edited 6 Years Ago by tinstaafl

Reverend Jim commented: Nice catch. +15

Reverend Jim 4,968 Hi, I'm Jim, one of DaniWeb's moderators.

6 Years Ago

Curious. I'll have a look.

Found the culprit. The problem was not in the actual Quicksort algorithm but in the test code used for the comparison. It was originally "X1 <= X2" but should have been "X1 < X2".

As they say, garbage in, garbage out.

Edited 6 Years Ago by Reverend Jim

tinstaafl 1,176 Posting Maven

6 Years Ago

Yep that works better now.

Also, you mentioned a reason for adding the closing single quote on the comment lines. Just an FYI the algorithm Dani is using doesn't color them properly unless it has the closing quote.

One other thing, have you tried vscode to edit/run your vbscripts?

Edited 6 Years Ago by Reverend Jim because: typo (changed clopsing to closing)

Reverend Jim 4,968 Hi, I'm Jim, one of DaniWeb's moderators.

6 Years Ago

Before I retired I developed a lot of infrastructure code as a domain/db admin for the corporate network at our control centre as well as a lot of "plumbing" code. I had to control fetching and piping information between dozens of data source/sinks. I also had to write a system of monitoring apps. vbScript seemed to be a better choice than a compiled language because

All the code had to be maintainable by the person who was on call on any given night. There was no special development environment needed (just a text editor).
There was never any question determining which version of the source code matched the running executable. The source code was the executable.
Emergency patches could be quickly implemented at 3:00 in the morning.
vbScript is a non-complex language.

That's why I developed a style that is hopefully uncomplicated, visually appealing and easy to read. I had to develop with the maintenance programmer in mind. I was frequently scoffed at by the mainstream corporate IT (the control centre was a small, isolated group outside of the corporate structure), but in the end when corporate IT had to replicate my functionality they adopted my code.

Having rambled on irrelevently, I'll now point out that at the timme I used an excellent product, PrimalScript. Unfortunately, my boss wouldn't pay for it so I just bought it myself. When I retired in 2008 I left it behind (or so I thought). Since then I had been using TextPad but a few weeks ago while doing some digital house-cleaning I came upon my PrimalScript install file and started using it again. I'd like to upgrade but at $350 it's not justifiable for personal use. Anyway, the old version does what I need. But I will look up vscode. I'm always open to new ideas.

BTW: I have always found Dani's syntax colouring to be iffy. Here's a sample of what the above looks like in TextPad (similar looking in PrimalScript)

Edited 6 Years Ago by Reverend Jim

Reverend Jim 4,968 Hi, I'm Jim, one of DaniWeb's moderators.

6 Years Ago

Ah. I see vscode is a stand-alone editor from the Visual Studio IDE. I'll get the latest version and have a go at it. Thanks.

Reverend Jim 4,968 Hi, I'm Jim, one of DaniWeb's moderators.

6 Years Ago

Hmmmm. Support for everything but vbScript. MS seems to have abandoned vbScript in favour of PowerShell. It's only a matter of time until a W10 update removes it entirely, I suppose.

A lot of stuff seems to be implemented via plugins. And there doesn't seem to be one for debugging vbScript. Too bad.

I also don't really care how the options are all set via json strings. That's one of the things that helped kill OS/2. All the options had to be set by text editor at the timw Windows was using a GUI. And I have to choose between skins instead of setting my own colour options like FG/BG fort comments. I think I'll stick with PrimatScript and Visual Studio 2012 for debugging.

Yeah. I know. Bitch bitch bitch.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.