Sign in to follow this  
Followers 0
ezzetabi

Sorting. Better ideas?

18 posts in this topic

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.

Share this post


Link to post
Share on other sites



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".

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

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 by ezzetabi

Share this post


Link to post
Share on other sites

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

Visit the SciTE4AutoIt3 Download page for the latest versions        Beta files                                                          Forum Rules
 
Live for the present,
Dream of the future,
Learn from the past.
  :)

Share this post


Link to post
Share on other sites

#5 ·  Posted (edited)

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?

;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 by ezzetabi

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

#8 ·  Posted (edited)

@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 by ezzetabi

Share this post


Link to post
Share on other sites

#9 ·  Posted (edited)

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 by ezzetabi

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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)

?


Visit the SciTE4AutoIt3 Download page for the latest versions        Beta files                                                          Forum Rules
 
Live for the present,
Dream of the future,
Learn from the past.
  :)

Share this post


Link to post
Share on other sites

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

Larry's way, an other time. :)

Share this post


Link to post
Share on other sites

#13 ·  Posted (edited)

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 by randallc

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

#15 ·  Posted (edited)

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 by JdeB

Visit the SciTE4AutoIt3 Download page for the latest versions        Beta files                                                          Forum Rules
 
Live for the present,
Dream of the future,
Learn from the past.
  :)

Share this post


Link to post
Share on other sites

#16 ·  Posted (edited)

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 by randallc

Share this post


Link to post
Share on other sites

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....


Visit the SciTE4AutoIt3 Download page for the latest versions        Beta files                                                          Forum Rules
 
Live for the present,
Dream of the future,
Learn from the past.
  :)

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0