Sorting. Better ideas?

[ezzetabi]

I have to sorts strings in array for their lenght.

This is my code, it works, but in big arrays (like 2000 elements) it is very slow.

Maybe does exist a better way?

Do
      $bSort = 0
      For $c = 1 to $aFiles[0] - 1
         if StringLen($aFiles[$c]) < StringLen($aFiles[$c + 1]) Then
            $sT = $aFiles[$c +1]
            $aFiles[$c + 1] = $aFiles[$c]
            $aFiles[$c] = $sT
            $bSort = 1
         EndIf
      Next
   Until $bSort = 0

Thanks.

[Jon]

That's a bubble sort. Slowest sort there is (But nice and simple)

Can't remember what it is called but instead of comparing element 1 and 2, then 2 and 3, then 3 and 4 start off comparing like:

10 elements

compare 1 and 6

compare 2 and 7

...

compare 5 and 10

Next time around reduce the "distance":

compare 1 and 5

compare 2 and 6

compare 3 and 7

Keep reducing the "distance" each loop until you are comparing 1 and 2, 2 and 3 - after this final loop the list will be sorted. It's quicker than a bubble sort when the initial list is completely random as an item can get from the end of the list to the start much more quickly.

Also look up "shell sort".

[ezzetabi]

When Jon Himself answers, you see it. :">

The Jon's way is something like this I guess.

It is in fact almost twice as fast.

$c = 1
$iDist = Round($aFiles[0]/2)
While $iDist >= 1
   Do 
      If StringLen($aFiles[$c]) < StringLen($aFiles[$c + $iDist]) Then
         $sT = $aFiles[$c + $iDist]
         $aFiles[$c + $iDist] = $aFiles[$c]
         $aFiles[$c] = $sT
      EndIf
      $c = $c + 1
   Until ($c + $iDist) > $aFiles[0]
   $iDist = $iDist - 1
   $c = 1
WEnd

Edited November 6, 2004 by ezzetabi

[Jos]

try this version to see if thats faster:

=====================================================
; Sort an Array with multiple dimentions
;=====================================================
Func Sort_Array(ByRef $I_ARRAY,$I_DIM,$I_UBOUND)
  ;shell sort array 
   $A_SIZE = $I_UBOUND
   $GAP = Int($A_SIZE / 2)
  ;
   While $GAP <> 0
      $ISCHANGED = 0
      For $COUNT = 1 TO($A_SIZE - $GAP)
         If $I_DIM = 1 Then
            If $I_ARRAY[$COUNT] > $I_ARRAY[$COUNT + $GAP] Then
               $TEMP = $I_ARRAY[$COUNT]
               $I_ARRAY[$COUNT]=$I_ARRAY[$COUNT + $GAP]
               $I_ARRAY[$COUNT + $GAP] = $TEMP
               $ISCHANGED = 1
            EndIf
         Else
            If $I_ARRAY[$COUNT][0] > $I_ARRAY[$COUNT + $GAP][0] Then
               For $C_DIM = 0 To $I_DIM -1
                  $TEMP = $I_ARRAY[$COUNT][$C_DIM]
                  $I_ARRAY[$COUNT][$C_DIM]=$I_ARRAY[$COUNT + $GAP][$C_DIM]
                  $I_ARRAY[$COUNT + $GAP][$C_DIM] = $TEMP
                  $ISCHANGED = 1
               Next
            EndIf
         EndIf
      Next
     ;if no changes were made to array, decrease $Gap size
      If $ISCHANGED = 0 Then
         $GAP = Int($GAP / 2)
      EndIf
   Wend
EndFunc  ;==>Sort_Array

[ezzetabi]

I tried implementing a QuickSort in Autoit, but when the Func call itself a second time it gives Array variable subscript badly formatted.:

Here the code, any idea?

expandcollapse popup

;As is it should order by value.
Func _QuickSort($aArray)
  ; This Func assumes the Autoit standard of the
  ; size in the position 0. and 1 to [0] the elements
   If Not IsArray($aArray) Then Return 0
   _q_sort($aArray, 1, $aArray[0])
EndFunc  ;==>_QuickSort

Func _q_sort($aArray, $iLeft, $iRight)
   Local $vPivot, $iR, $iL
   
   $iR = $iRight
   $iL = $iLeft
   $vPivot = $aArray[$iLeft]
   While $iRight < $iLeft
      While ($aArray[$iRight] >= $vPivot) And ($iLeft < $iRight);Check here
         $iRight = $iRight - 1
      Wend
      If $iLeft <> $iRight Then
         $aArray[$iLeft] = $aArray[$iRight]
         $iLeft = $iLeft + 1
      EndIf
      
      While ($aArray[$iLeft] <= $vPivot) And ($iLeft < $iRight);Check here
         $iLeft = $iLeft + 1
      Wend
      If $iLeft <> $iRight Then
         $aArray[$iRight] = $aArray[$iLeft]
         $iRight = $iRight - 1
      EndIf
   Wend
   
   $aArray[$iLeft] = $vPivot
   $vPivot = $iLeft
   $iLeft = $iL
   $iRight = $iR
   
   If $iLeft < $iRight Then
      _q_sort($aArray, $iLeft, $vPivot - 1)
   EndIf
   If $iRight > $iLeft Then
      _q_sort($aArray, $vPivot + 1, $iRight)
   EndIf
EndFunc  ;==>_q_sort

Edit: changed a - to +. Thanks SlimShady

Edited November 6, 2004 by ezzetabi

[SlimShady]

I have a feeling that it goes wrong here:

If $iLeft < $iRight Then
     _q_sort($aArray, $iLeft, $vPivot - 1)
  EndIf
  If $iRight > $iLeft Then
     _q_sort($aArray, $vPivot - 1, $iRight)
  EndIf

The function calls itself again.

Let me see...

I'm not sure what's wrong the function.

I'm sure someone can help you.

[Josbe]

Try the Shell sort suggested by JdeB...(I think that it's a faster algorithm)

[ezzetabi]

@SlimShady

Quicksort is famous for being a recursive Func. There is a mistake anyway. Fixed, but it does not solve the problem...

more info there http://linux.wku.edu/~lamonml/algor/sort/quick.html

@josbe

In few test, the JdeB was a little slower than mine. But in fact they follow the same idea.

Edited November 6, 2004 by ezzetabi

[ezzetabi]

OPS... Sorry to everyone. I tested the JdeB idea vs mine in two totally different arrays. His is actually faster.

Still, anyone have a idea about the Quicksort Func problem?

Edited November 6, 2004 by ezzetabi

[ezzetabi]

I thanks you Larry, but I'd like to understand where was the problem in my version.

[Jos]

I thanks you Larry, but I'd like to understand where was the problem in my version.

<{POST_SNAPBACK}>

should this line :

Func _q_sort($aArray, $iLeft, $iRight)

be:

Func _q_sort(byref $aArray, $iLeft, $iRight)

?

[ezzetabi]

Yes JdeB. But even that don't solves. Well. I guess it is a useless scrap of code.

Larry's way, an other time.

[randallc]

got this quicksort from the google...Hi, Larry,

If you change your string to split, though, this does not sort either;

Oh - Sorry, I see you were sorting by length of strings; where is the code for sorting by value which is quickest?

Thanks, Randall

Edited April 2, 2005 by randallc

[randallc]

I had though AutoIt might do a quicsort as quickly as vbscript, but a file of 50000 words takes 76 secs instead of 8 secs. Are there better file/ in/out commands, or is this what you would expect in native AutoIt?

Randall

[Jos]

Did you try the _ArraySort() UDF included in the Autoit Installer ?

Also create a Variable with the output and do a FileWite() in stead of doinf a FileWriteLine() for each record.

Edited April 2, 2005 by JdeB

[randallc]

Did you try the _ArraySort() UDF included in the Autoit Installer ?

<{POST_SNAPBACK}>

Yes, its so slow, that's why I was looking for a "quickSort"

Also create a Variable with the output and do a FileWrite() in stead of doing a FileWriteLine() for each record.

<{POST_SNAPBACK}>

Usually with large strings (eg in vbscript), environment slows things down in the end; that's why i've tried to stick to sorting within the files?

I have not specifically tried large strings in AutoIt; any reason to think otherwise?

Randall

PS I have checked using variables now, too; way slower if for a string 500Kb!

Edited April 2, 2005 by randallc

[Jos]

Yes, its so slow, that's why I was looking for  a "quickSort"

<{POST_SNAPBACK}>

try the latest one available here .

i believe it contains another Sort routine which is a lot faster....

[randallc]

try the latest one available here .

i believe it contains another Sort routine which is a lot faster....

<{POST_SNAPBACK}>

Yes, it's probably 10% faster, but 2000 rows of 200 characters; 1.1 sec vbs, 16secs AutoIt? - I may still not have the program efficient in AutIt; I need to see where the slow points are.

Randall