Super-Fast Sort an array [updated]

[Update: Fixed list not perfectly sorted]

Some of you  know about the InsertionSort function?

I created a little pluggin to this function that accelerate sorting large amount of lines by 1000%
Time for sorting 2000 lines:

InsertionSort: 2.65 seconds
Super-Fast Sort: 0.27 seconds

To run the script below you have to create a text file named "test.txt" and copy paste the text to sort, preferably with many many lines!
(And have this text file near the vbs file.)

My add-on is splitting the whole text into small ones, themselves sorted in an array after their first letter only.
Then it splits these small texts into small arrays and send these arrays for sorting with the InsertionSort function.
Only one small problem (the world is not perfect): It works only if the first letter of your items are different.
If you have a list in where all the items begin with the same letter
for example:

item1
item32
item75
item6
etc

It will take much more time!
Depending on the purpose of your script it can be an issue or not be an issue.


I also tried to recurse my SortArray function to do a complete sorting with this method but it didn't work.

 Title = "sort test super fast"
 Set fso = CreateObject("Scripting.FileSystemObject")
 Set ts = fso.GetFile("test.txt").OpenAsTextStream(1)
 MyArray = Split(ts.ReadAll, vbCrlf)
 ts.Close
 '-------------test sort-------
 time1 = Timer
 ArraySort MyArray
 time2 = Timer
 '------------write result------
 Set objOutputFile = fso.CreateTextFile("result.txt", True)
 objOutputFile.WriteLine Join(MyArray, VbCrlf)
 objOutputFile.Close
 MsgBox time2 - time1 & " seconds. Ok.",,Title
 '-------end of main script------
 '-----------sort function---------
 Function ArraySort(ArrY)
 ReDim TempArray(255)
 For Each Word in ArrY
 UCaseWord = UCase(Word) & "   "
 TempArrayNum = Asc(Left(UCaseWord,1))
 TempArray(TempArrayNum) = TempArray(TempArrayNum) & VBCrlf  & Word
 Next
 For Each SmallList In TempArray
 If SmallList <>"" Then
 SmallArray = Split( Mid(SmallList,2 ),VBCrlf)
 '--------use not-so-fast method for each small array-------
 InsertionSort SmallArray
 '------------------------
 BigList = BigList & Join(SmallArray,VbCrlf)
 End If
 Next
 ArrY = Split(BigList,VbCrlf)
 Erase SmallArray
 Erase TempArray
 End Function
 '---------------------------------
 '---------- old sort function---------
 Function InsertionSort(arrX)
 Dim nUB : nUB = UBound(arrX)
 Dim i, j, v
 For i=1 To nUB
     v=arrX(i)
     j=i
     Do While arrX(j-1) > v
        arrX(j) = arrX(j-1)
        j=j-1
        If j<=0 Then
        Exit Do
        End If
     Loop
     arrX(j) = v
 Next
 End Function
 '------------------------------------
 

Hi Fredledingue,

shouldn't

  TempArray(TempArrayNum) = TempArray(TempArrayNum)  & Word & VBCrlf
 
be

  TempArray(TempArrayNum) = TempArray(TempArrayNum)  & VBCrlf & Word
 
To match

  SmallArray = Split( Mid(SmallList,2 ),VBCrlf)
 
 

Fred,
 
First off... wow.
I am constantly amazed by the scripting prowess displayed by some of the folks in these forums.  if I ever had to write a sort routine by scratch, I don't think I could do it, especially not after seeing the code that you put together.  Insertion sorts, bubble sorts... meh... I look att that code for that function and just go 'duh'..... it doesn't make any sense to me.
 
But since I am pretty code-dumb, and can't write my own sort routines, I've always had to rely on the built-in ones that vbscript gives us:

 Function fSortArray(aSortThisArray)
  Dim oArrayList, iElement, oArrayDic
  Set oArrayDic = CreateObject("Scripting.Dictionary")
  Set oArrayList = CreateObject( "System.Collections.ArrayList" )
   For iElement = 0 To UBound(aSortThisArray)
    oArrayList.Add aSortThisArray(iElement)
   Next
  oArrayList.Sort
  set fSortArray = oArrayList
 End Function 
 

 
Now, the above code is pretty quick, and - I think - does a pretty good job of sorting text.  But, since I am always on the lookout for a better way of doing things, I gave your function a try.
I grabbed a copy of a log file and performed two different timings on it, and our GAL dump, removed the first two columns so that each line started with a different letter, and performed the final test on it.
 
31k file(486 lines) - log file
Super fast sort  = 0.046875
fSortArray = 0.03125
 
250K file(3888 lines) - log file
Super fast sort  = 3.6875
fsortarray = 0.140625
 
2meg file(7998 long lines) - GAL dump
Super fast sort = 7.265625
fSortArray = 0.28125

I still feel that my testing is not right, since I am getting such wildly varying results, so I would appreciate it if you and others would give this a try and post the results.
 

DigitalSkReam,
 
I couldn't test your function because wscript can't create the ActiveX component "System.Collections.ArrayList". :(
Probably because I run w98se. I thought I had some ActiveX update, but no.
 
Anyway if there is a pre-build ActiveX function that is called ".Sort" and used for sorting arrays, it's likely to be much faster than anything we could do in raw VBS.
It's very simple: in Excell you can insert realy huge amount of lines and it will sort them in a fraction of a hundred of second.
I'v been always wondering how is it possible. Hence my pasionate interrest for sort scripts.
 
Now it's surprising that you got so poor results with my function.
I tested it on 2000 lines and got no more than 0.27 sec.
 
Then I tested it on a divX log of 5000 lines:
InsertionSort: 9.7 seconds
Super-Fast Sort: 1.7 seconds
 
The DivX log (and maybe other log files) are not optimized for using with my function because each line starts with a number, so the big array can be split in only 10 smaller arrays. And "1" and "2" take the bulk of the text while "9" takes very little, so the division is not optimized neither.
Also it takes a lot of time to append lines to small arrays when they grow not that small. And the fast concatenation "flush" method with dictionary is not possible here.
 
ehvbs
 

 
Very well observed! I found it too yesterday and updated the code

Hi Fredledingue,

(1)  For "System.Collections.ArrayList" you need the dot.net runtime (1.1 is the one I'm sure
       about). You'll have to check/decide, whether you can/want to install it.

(2)  I think something went wrong with your update of the code; I still see the

          TempArray(TempArrayNum) = TempArray(TempArrayNum)  & Word & VBCrlf
  
       version.

Thanks ehvbs.
 I edited the script on my local file and maybe I forgot to do it here.
 
dot.net? No thanks.
I'm not going to install 20Mb of crap just for two or three vbs funstions I may need once in a while.
 
 

ORIGINAL: Fredledingue

My add-on is splitting the whole text into small ones, themselves sorted in an array after their first letter only.
Then it splits these small texts into small arrays and send these arrays for sorting with the InsertionSort function.

 
Based on this description it sounds sort of like a radix sort.  Yours is more of a hybrid since you're only sorting into "buckets" once then you sort what's in each "bucket".  With a radix sort the following list would take four passes:
Dog, Feet, Junk, Fun, Cat, Dirt, Fool
 
First Sort would be based on the least significant factor.
Group None: Dog, Fun, Cat
Group L: Fool
Group K: Junk
Group T: Feet, Dirt
 
Second Sort (next least significant):
Group G: Dog
Group E: Feet
Group N: Junk, Fun
Group O: Fool
Group R: Dirt
Group T: Cat
 
Third Sort (next least significant):
Group A: Cat
Group E: Feet
Group I: Dirt
Group O: Dog, Fool
Gruop U: Junk, Fun
 
Final Sort (most significant):
Group C: Cat
Group D: Dirt, Dog
Group F: Feet, Fool, Fun
Group J: Junk
 
Final List
Cat, Dirt, Dog, Feet, Fool, Fun, Junk
 
The radix sort is stable - meaning two items that are the same will not swap places - which is why, in this example, the final sort of "D" and "F" preserves the ordering from the previous sorts.
 
With your sort it would do the following:
Split into C, D, F, J lists.
Cat
Dog, Dirt
Feet, Fun, Fool
Junk
 
C is sorted
 
Sort D (one swap)
Dirt, Dog (swapped)
 
Sort F (one pass, one swap)
Feet (pass), Fool, Fun (swapped)
 
J - is sorted
 
Returns:
Cat, Dirt, Dog, Feet, Fool, Fun, Junk

Skie,
 
Interresting, when I will have time I'll try it with my "ABCD... array" method.
 

Due to the requirements of needing .NET installed to use the arraysort ActiveX component, I came up with a workaround.
This function will accept either an array or a string, and will sort it.  If the arraysort activex is available, it will use it for the array, but if it isn't it will use the DOS sort routine to perform the sort.  kinda kludgy, but...
I was able to sort a 40,000 line (750KB) list in 0.53125 seconds with this, using the DOS sort routine.
A 4.4MB file containing our company's GAL (8,000 lines, each line around 600 characters long) was sorted in 0.7 seconds.
I think that this is an acceptable amount of overhead for a sort routine, don't you?

You can modify the sort command based on your particular OS, as some have different switches/arguments.  This function has been tested on XP, 2003, and Windows NT 4.0.

 Function fSort(oSortThisObject)
 'This function will sort either a string or an array using an ActiveX sort routine, or 
 'if that is not available on the machine, a CLI SORT command.
 'If an array, then it will return a sorted array.
 'If a string, it will return a sorted string.
  Dim sSortTemp, sSortCmd, oArrayList, iErr, iElement
  Dim oFSO, oShell
  Set oFSO = CreateObject("Scripting.FileSystemObject")
  Set oShell = CreateObject("WScript.Shell")
  Dim aVerText, aOS, VerLine, sOSString
  sTmpFile1 = "c:\" & oFSO.GetTempName
  oShell.Run "%comspec% /c ver > " & sTmpFile1,0,True 
  aVerText = Split(oFSO.OpenTextFile(sTmpFile1,1).ReadAll,VbCrLf)
  oFSO.DeleteFile sTmpFile1, True 
  aOS = Array("Windows 95", "Windows 98", "Windows NT", "Windows 2000", "Windows XP", "Microsoft Windows [Version")
   For Each VerLine In aVerText
     For iElement = 0 To UBound(aOS)
       If InStr(VerLine, aOS(iElement)) <> 0 Then
         If aOS(iElement) = "Microsoft Windows [Version" Then 
          sOSString = "Windows 2003"
         Else
          sOSString = aOS(iElement)
         End If
       End If
     Next
   Next
 'Insert commands for your particular OS here in a new case.
  Select Case sOSString
   Case "Windows NT"
    sSortCmd = "%comspec% /c sort < "
   Case Else 
    sSortCmd = "%comspec% /c sort "
  End Select
  sSortTemp = "c:\" & oFSO.GetTempName
   If IsArray(oSortThisObject) Then
     On Error Resume Next
      Set oArrayList = CreateObject( "System.Collections.ArrayList" )
      iErr = Err.Number
     On Error GoTo 0
      If iErr = 0 Then 
        For iElement = 0 To UBound(oSortThisObject)
         oArrayList.Add oSortThisObject(iElement)
        Next
       oArrayList.Sort
        For iElement = 0 To UBound(oSortThisObject)
         oArrayDic.Add oArrayDic.Count,oArrayList(iElement)
        Next
       fSort = oArrayDic.Items
      Else
       oFSO.OpenTextFile(sSortTemp,8,True).WriteLine Join(oSortThisObject,VbCrLf)
       oShell.Run sSortCmd & sSortTemp & " > c:\tmpshellfile.txt",0,True 
       fSort = Split(oFSO.OpenTextFile("c:\tmpshellfile.txt",1).ReadAll,VbCrLf)
       oFSO.DeleteFile "c:\tmpshellfile.txt", True 
       oFSO.DeleteFile sSortTemp, True 
      End If 
   Else
    oFSO.OpenTextFile(sSortTemp,8,True).WriteLine oSortThisObject
    oShell.Run sSortCmd & sSortTemp & " > c:\tmpshellfile.txt",0,True 
    fSort = oFSO.OpenTextFile("c:\tmpshellfile.txt",1).ReadAll
    oFSO.DeleteFile "c:\tmpshellfile.txt", True 
    oFSO.DeleteFile sSortTemp, True 
   End If 
 End Function
 

Not to be facetious but....instead of going through all the trouble of using ActiveX controls and command prompt workarounds.....why not use JScript in part to do the  the dirty work? I'm able to read a 16mb textfile with 133,350 lines, sort it, and rewrite the result to a new file in an average of 9 seconds:

 var startTime=new Date().getTime();
 //function sortfile(Input file,outPutFile)
 
 function sortfile(x,y){
     var fso;
     fso = new ActiveXObject("Scripting.FileSystemObject");
     var ForReading = 1, ForWriting = 2;
     var objFile;
     var fulltext=fso.OpenTextFile(x, ForReading).ReadAll();
     fulltext=fulltext.split("\n");
     fulltext=fulltext.sort();
     fulltext=fulltext.join("\n");
     objFile=fso.CreateTextFile(y)
     objFile.Write(fulltext)
     objFile.Close();
 
 }
 
 sortfile("2ktest.txt","done.txt")
 var endTime=new Date().getTime();
 
 WScript.Echo("Complete\nTime: "+eval(endTime-startTime));

Now if you NEED/want to use as much vbscript as possible, maybe use a .wsf instead?

 <job id="j1">
 <script language="JScript">
     function SortVBArray(arrVBArray) {
         return arrVBArray.toArray().sort().join('\n');
     }
 </script>
 
 <script language="VBScript">
     Function SortArray(arrInput)
         SortArray = Split(SortVBArray(arrInput), vbNewLine)
     End Function
 </script>
 </job>

Just an idea for an alternative to activeX and other external additions. plus using the JScript .sort method will allow you a much easier way to custom sort your results

He said the J-word!

Lynch him!!

[sm=nahrung034.gif] <--- blame it on the alcohol, or lack thereof

ORIGINAL: TNO
Not to be facetious but....instead of going through all the trouble of using ActiveX controls and command prompt workarounds.....why not use JScript in part to do the  the dirty work? I'm able to read a 16mb textfile with 133,350 lines, sort it, and rewrite the result to a new file in an average of 9 seconds:

Now if you NEED/want to use as much vbscript as possible, maybe use a .wsf instead?

Just an idea for an alternative to activeX and other external additions. plus using the JScript .sort method will allow you a much easier way to custom sort your results

 
Yer right int hat the jscript .sort method would be "better" or at least integral to the language.  However, in my case, I am limited to vbs as the 'standard' scripting language and cannot deviate.
Also, I owuldn't know HOW to go about writing a .vbs file that includes a jscript command.  I know that it can be done in ASP, but as I am writing in pure .vbs for CLI execution, I don't think it is possible.  It would be great if you could prove me wrong, as there are a number of things that jscript does faster than vbs.

...However, in my case, I am limited to vbs as the 'standard' scripting language and cannot deviate.
Also, I owuldn't know HOW to go about writing a .vbs file that includes a jscript command.  I know that it can be done in ASP, but as I am writing in pure .vbs for CLI execution, I don't think it is possible.  It would be great if you could prove me wrong, as there are a number of things that jscript does faster than vbs.

Back when I was playing with script components and such for DHTML behaviors I learned about the Windows Script Components (*.wsc). Though with my new JScript library extensions I can avoid using these files, I can see such cases where it would still be a good idea, such as this.  This will allow you to treat a pure scripting file as an ActiveX component that can be used in any COM enabled language (talk about deployability )

Now heres how we make our component:

First make a text file with the wsc extension in this case I'm going to call it sort.wsc

I'm also going to make my vbs file: monkeys.vbs

Next, inside my wsc file I'm going to put the following, which is the most basic format for a single JScript method:

<?XML version="1.0"?>
<package>
   <component id="component1">
      <registration progid="MyComponent.Sort"/>
      <public>
         <method name="FileSort">
            <parameter name="fin"/>
            <parameter name="fout"/>
         </method>
      </public>
      <script language="JScript">
         <![CDATA[
         ....
         ]]>
         </script>
   </component>
</package>

Explanation: MyComponent.Sort is the name of my component when I reference it in my vbscript, it can be pretty much whatever I want it to be. FileSort is the method of the MyComponent.Sort (simply put, the name of the function I will be calling). And the parameters of my function are fin & fout. Since XML is used to define a wsc file, its obvious that throwing any kind of script inside of it would screw up the XML parser with its special charcters (&, {,}, etc.. ), so a  <![CDATA[ ... ]]> section is included so it doesn't go psycho when it encounters a special character.

So now lets throw in the JScript that does all the dirty work for the sorting:

<?XML version="1.0"?>
<package>
   <component id="component1">
      <registration progid="MyComponent.Sort"/>
      <public>
         <method name="FileSort">
            <parameter name="fin"/>
            <parameter name="fout"/>
         </method>
      </public>
      <script language="JScript">
         <![CDATA[

         function FileSort(fin,fout){
            var fso;
            fso = new ActiveXObject("Scripting.FileSystemObject");
            var ForReading = 1, ForWriting = 2;
            var objFile;
            var fulltext=fso.OpenTextFile(fin, ForReading).ReadAll();
            fulltext=fulltext.split("\n");
            fulltext=fulltext.sort();
            fulltext=fulltext.join("\n");
            objFile=fso.CreateTextFile(fout)
            objFile.Write(fulltext)
            objFile.Close();
         }

         ]]>
         </script>
   </component>
</package>

So now in our vbs file I'll put this:

' Creates instance of my script component.
Set obj = CreateObject("MyComponent.Sort")

'Sort the file FileSort("File To Be Sorted","Sorted File")
Call obj.FileSort("M94503VD.txt","Sorted.txt")
MsgBox("Complete")

Now the final step is to register our wsc file so we can use it: Right Click on the wsc file and hit Register so we can reference it from anywhere regardless of the wsc file's location.

Now save the vbs file, double click it and let the magic begin

This was just a crash course on what is possible now to "Extend" the life and functionality of your scripts in a zero-deployable, zero-plugin, zero-third-party environment. Now you can rely on nothing but your current version of WSH to accomplish your tasks.

I almost forgot to mention the alternative, one that will allow you to use multiple languages in a single file without having to register anything:

  <job>
     <object progid="Shell.Application" id="shellApplication" />
     <reference object="ADODB.Recordset" />
     <script language="JScript" src="MyFile.js" />
     <script language="JScript">
        shellApplication.FindFiles();
     </script>
     <script language="VBScript" src="MyFile.vbs" />
     <script language="VBScript">
        MsgBox "adOpenStatic = " + CStr(adOpenStatic)
     </script>
  </job>

This one I think is pretty self explanatory at what you can do, just save it as .wsf

More info on this method here: http://www.microsoft.com/mind/0999/cutting/cutting0999.asp

<grovel>That just rules!  That xml has to be used kinda sucks, but the rest... awesome!</grovel>

Function InsertionSort(arrX)
Dim nUB : nUB = UBound(arrX)
Dim i, j, v
For i=1 To nUB
   v=arrX(i)
   j=i
   Do While arrX(j-1) > v
      arrX(j) = arrX(j-1)
      j=j-1
      If j<=0 Then
      Exit Do
      End If
   Loop
   arrX(j) = v
Next
End Function

I was wondering if someone could point out what this function is actually doing, or point me to where i can find out. I know that it sorts an array, which is what I want, and I have succesfully adapted it to work in the modified script engine in the program i need it for, But, I want to know what its actually doing. I dont want to just take code and use it i want to learn how to write it myself. Any help would be greatly apreciated.

Hi DarkStar,

There are lot's of web site dedicated to sorting algorithms. Just google for something
like "sort bubble insertion quick". Add "demo" if you want some kind of visualisation.

I like:

http://www.softpanorama.org/Algorithms/sorting.shtml

but that recommendation is based on random picking, not evaluation.

TNO,
where this come from and why this is not working in plain vbs?
 
var fulltext=fso.OpenTextFile(fin, ForReading).ReadAll();
           fulltext=fulltext.split("\n");
           fulltext=fulltext.sort();
           fulltext=fulltext.join("\n");
 
like, say,
 
 fulltext=fso.OpenTextFile(fin, ForReading).ReadAll.split("\n").sort().join("\n")

Thats javascript and it treats everything as an object so you can treat everything like a method/property instead of Functions.

correction for your 2nd line:


 fulltext=fso.OpenTextFile(fin, ForReading).ReadAll().split("\n").sort().join("\n")