Array sorting (listview related)

[LazyCoder]

Here is my modified version of _ArraySort. This is the one I use to manage the data I display in a listview. This way I can easily sort my list according to the column header the user clicked on (represented here by $i_SortIndex).

I changed the name to quickly know which algorithm is used.
I work on an other sort algorithm implementation as I'm not satisfied with this shell sort... (but that's personal)

Maybe this can help others:
 

expandcollapse popup

;===============================================================================
;
; Function Name:    _ArrayShellSort()
; Description:      Sort a multi dimentional Array on a specific index using
;                   the shell sort algorithm
; Parameter(s):     $a_Array      - Array
;                   $i_Descending - Sort Descending when 1
;                   $i_Base       - Start sorting at this Array entry.
;                   $I_Ubound     - End sorting at this Array entry
;                   $i_Dim        - Number of dimentions
;                   $i_SortIndex  - The Index to consider (for multi-dimensional
;                                   arrays only)
; Requirement(s):   None
; Return Value(s):  On Success - 1 and the sorted array is set
;                   On Failure - 0 and sets @ERROR = 1
; Author(s):        Jos van der Zande  / LazyCoder
;
;===============================================================================
;
Func _ArrayShellSort(ByRef $a_Array, $i_Decending = 0, $i_Base = 0, $i_Ubound = 0, $i_Dim = 1, $i_SortIndex = 0)
   Local $A_Size, $Gap, $Count, $Temp
   Local $b_ExchangeValues = 0
   Local $IsChanged = 0

   If UBound($a_Array) < $i_Ubound Or Not IsNumber($i_Ubound) Then
      SetError(1)
      Return 0
   EndIf
  ; Set to ubound when not specified
   If $i_Ubound < 1 Then $i_Ubound = UBound($a_Array) - 1
  ; Shell sort array
   $A_Size = $i_Ubound
   $Gap = Int($A_Size / 2)
   $b_ExchangeValues = 0
   $IsChanged = 0
  ;
   While $Gap <> 0
      $IsChanged = 0
      For $Count = $i_Base To ($A_Size - $Gap)
         $b_ExchangeValues = 0
         If $i_Dim = 1 Then
            If $i_Decending <> 1 Then; sort array Ascending
               If $a_Array[$Count] > $a_Array[$Count + $Gap] Then
                  $b_ExchangeValues = 1
               EndIf
            Else  ; sort array Descending
               If $a_Array[$Count] < $a_Array[$Count + $Gap] Then
                  $b_ExchangeValues = 1
               EndIf
            EndIf
            If ($b_ExchangeValues) Then
               $Temp = $a_Array[$Count]
               $a_Array[$Count] = $a_Array[$Count + $Gap]
               $a_Array[$Count + $Gap] = $Temp
               $IsChanged = 1
            EndIf
         Else
            If $i_Decending <> 1 Then; sort array Ascending
               If $a_Array[$Count][$i_SortIndex] > $a_Array[$Count + $Gap][$i_SortIndex] Then
                  $b_ExchangeValues = 1
               EndIf
            Else  ; sort array Descending
               If $a_Array[$Count][$i_SortIndex] < $a_Array[$Count + $Gap][$i_SortIndex] Then
                  $b_ExchangeValues = 1
               EndIf
            EndIf
            If ($b_ExchangeValues) Then
               For $C_DIM = 0 To $i_Dim - 1
                  $Temp = $a_Array[$Count][$C_DIM]
                  $a_Array[$Count][$C_DIM] = $a_Array[$Count + $Gap][$C_DIM]
                  $a_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
   Return 1
EndFunc  ;==>_ArrayShellSort

Edited October 21, 2013 by Jos

[Jos]

Here is my modified version of _ArraySort. This is the one I use to manage the data I display in a listview. This way I can easily sort my list according to the column header the user clicked on (represented here by $i_SortIndex).

I changed the name to quickly know which algorithm is used.

I work on an other sort algorithm implementation as I'm not satisfied with this shell sort... (but that's personal)

Maybe this can help others:

<{POST_SNAPBACK}>

I will copy this version to the Array.au3 replacing _ArraySort() ... tnx

Edit have updated the array.au3 and Doc Page ..

Edited December 28, 2004 by JdeB

[LazyCoder]

Still for those interested, I finally produced my sort: one using the QuickSort method.

Moreover I modified again the ShellSort function to manage a different way the Gap, saving some more time.

Finally I rewrote a 1D/2D _ArrayReverse functions to suit my needs.

To do this I created a usefull exchange function but I needed to set dimension and number of sub-elements as optional parameters because of a slow down I encoutered using UBound in my innermost function.

So if all this can interest anyone, I'm still happy to share.

ArrayLC.au3

[LazyCoder]

As soon as the internal pb "with Ubound" will be solved, I'll update these functions.

[tylo]

I posted this at one time. It works for 1D arrays.

/Add: with 5000 element, it is actually about twice as fast as LazyCoder's.

expandcollapse popup

;=============================================================================
; 
; Synopsis:
;   _ArrayQuickSort() - sorts an array of data in ascending order
;        
; Function Description:
;     Sorts an array of data using the QuickSort / InsertSort algorithm.
;     Note that this implementation is also fast on already sorted arrays.
;     The speed is about twice of the SortShell by Brian Keene.
;
; Parameter(s):
;     $array = The array to be sorted.
;     $left   = first index
;     $right  = last index
;
; Version:
;     1.1 Added Then to If
;     1.0
; Author:
;     Tylo <tylo@start.com>
;=============================================================================

Func _ArrayQuickSort(ByRef $array, $left = 0, $right = -1)
   If ($right = -1) Then $right = UBound($array) - 1
   If ($right - $left <= 10) Then
     ; InsertSort - fastest on small segments (= 25% total speedup)
      Local $i, $j, $t
      For $i = $left + 1 To $right
         $t = $array[$i]
         $j = $i
         While ($array[$j - 1] > $t)
            $array[$j] = $array[$j - 1]
            $j = $j - 1
            If ($j <= $left) Then ExitLoop
         Wend
         $array[$j] = $t
      Next
   Else
     ; QuickSort - fastest on large segments
      Local  $pivot, $L, $R, $t
      $pivot = $array[ ($left + $right)/2 ]
      $L = $left
      $R = $right
      While (1)
         While ($array[$L] < $pivot)
            $L = $L + 1
         Wend
         While ($array[$R] > $pivot)
            $R = $R - 1
         Wend
         While ($L <> $R) And ($array[$L] = $array[$R])
             $L = $L + 1
         Wend
         If ($L = $R) Then ExitLoop
         ; Swap
         $t = $array[$L]
         $array[$L] = $array[$R]
         $array[$R] = $t
      Wend
      $L = $L - 1
      If ($left < $L) Then _ArrayQuickSort($array, $left, $L)
      $R = $R + 1
      If ($right > $R) Then _ArrayQuickSort($array, $R, $right)
   EndIf      
EndFunc


;=============================================================================
;Ex. Usage:

$SZ = 2000
If $CmdLine[0] > 0 Then $SZ = $CmdLine[1]

Dim $DATA[ $SZ ]
For $i = 0 To $SZ - 1
   $DATA[ $i ] = Random()
Next

$time = TimerInit()
_ArrayQuickSort($DATA)
MsgBox(0, "QuickSort", "Seconds used on " & $SZ & " items: " & Round(TimerDiff($time)/1000, 2))

ShowArray($DATA, $SZ/2 - 3, $SZ/2 + 3)
EXIT

Func ShowArray( ByRef $DATA, $l, $r )
   $MSG = ""
   For $i = $l To $r
      $MSG = $MSG & "$DATA[ " & $i & " ] = " & $DATA[ $i ] & @CR
   Next
   MsgBox(0, "Sorted Data", $MSG)
EndFunc

Edited December 31, 2004 by tylo

[Jos]

Ahh, our speed monster at it again i feel another competition coming

Seriously, you are correct it is about 2 times faster than the current one in the Array.au3 include file so think we should consider using it.

It only needs to be changed to be able to use the multiple dimensions and be able to select the dimension to sort on.....

So what do you think ?

Edited December 31, 2004 by JdeB

[Jon]

Heh, every single time somebody posts something that mentions the words "speed" or "fast" then it's taken as a challenge. Programmers are funny.

[SumTingWong]

Heh, every single time somebody posts something that mentions the words "speed" or "fast" then it's taken as a challenge.  Programmers are funny.

<{POST_SNAPBACK}>

Speed and size

It's not just me then

[Valik]

Heh, every single time somebody posts something that mentions the words "speed" or "fast" then it's taken as a challenge.  Programmers are funny.

<{POST_SNAPBACK}>

Freud would say its a "My e-penis is bigger than your e-penis" thing.

[LazyCoder]

Here is my version, adapted from Tylo's.

I added 2D arrays management and sort criterium (on the 2nd dimension).

Otherwise, just three points:

1) To tylo: I couldn't verify that your version was twice as fast my previous one (QuickSort algorithm, not ShellSort, otherwise, I'm OK)

Anyway, the melting of InsertSort/QuickSort is a benefic one I should not have forgotten... this version is a bit quicker than mine, I fully agree!

2) I knew my algorithm was not the better (if you look at my QuickSort code you'll read

; Should be better to choose an other place BUT would have to read
; from both ends...

But as I'm a lazy coder (incredible, isn't it?) and needed to deal quickly with such a pb, I just did not take time to write it any better... Now it's done thanks to Tylo!

3) I've no pb with my e-penis being the smallest on the e-planet, I'm too pragmatic to mind such competitions

[Edit: File removed...]

Edited January 3, 2005 by LazyCoder

[LazyCoder]

I removed the file I added in my previous message because I encountered a little pb with the recursive version of the algorithm...

Try Tylo's code but change:

$DATA[ $i ] = Random()

for

$DATA[ $i ] = 11

and you'll see what I mean...

I'm working on it. In the meantime, I'll stuck to my old version (that also encounters this pb, I know!).

Edited January 3, 2005 by LazyCoder

[LazyCoder]

Here we are, finally!

I finally rewrote the whole damn thing to have it behave a stable way even in the worst cases.

Indeed, I wrote 5 different versions and finally found that Larry had already given the same algorithm implementation (more than one month ago BUT minus the InsertSort enhancement). So, if had known this any sooner...

Anyway, you'll find the following main functions for 1D and 2D arrays:

_ArrayExchangeValues

_ArrayShellSort

_ArrayInsertSort

_ArrayQuickSort

_ArrayReverse (to avoid sorting in both orders... )

Enjoy!

ArrayLC.au3

Edited January 7, 2005 by LazyCoder

[GaryFrost]

Here's a couple of UDF's (attachment) you might find interesting LazyCoder

Feel free to improve on them, the sort is based on using your sort routines

also here's an example of using the sort

expandcollapse popup

#include <GUIConstants.au3>
#include "ArrayLC.au3"
#include "ListViewUDFs.au3"

GUICreate("listview items",220,250, 100,200,-1,$WS_EX_ACCEPTFILES)
GUISetBkColor (0x00E0FFFF) ; will change background color

$listview = GuiCtrlCreateListView ("col1  |col2|col3  ",10,10,200,150);,$LVS_SORTDESCENDING)
$button = GuiCtrlCreateButton ("Value?",75,170,70,20)
$item1=GuiCtrlCreateListViewItem("item2|col22|col23",$listview)
$item2=GuiCtrlCreateListViewItem("............item1|col12|col13",$listview)
$item3=GuiCtrlCreateListViewItem("item3|col32|col33",$listview)
$input1=GuiCtrlCreateInput("",20,200, 150)
GuiCtrlSetState(-1,$GUI_ACCEPTFILES)  ; to allow drag and dropping
GuiSetState()
GUICtrlSetData($item2,"|ITEM1",)
GUICtrlSetData($item3,"||COL33",)
GUICtrlDelete($item1)
#cs
========================================
    The following declartiong creates an array using the number
    of columns in the ListView
========================================
#ce
Dim $b_Descending[_GUICtrlGetListViewColsCount($listview)]

Do
  $msg = GuiGetMsg ()
     
   Select
      Case $msg = $button
         MsgBox(0,"listview item",GUICtrlRead(GUICtrlRead($listview)),2)
      Case $msg = $listview
;        MsgBox(0,"listview", "clicked="& GuiCtrlGetState($listview),2)
        _SortListView($listview,$b_Descending,GuiCtrlGetState($listview))
   EndSelect
Until $msg = $GUI_EVENT_CLOSE

Edited February 16, 2005 by gafrost

[tylo]

I removed the file I added in my previous message because I encountered a little pb with the recursive version of the algorithm...

Try Tylo's code but change:

$DATA[ $i ] = Random()

for

$DATA[ $i ] = 11

and you'll see what I mean...

I'm working on it. In the meantime, I'll stuck to my old version (that also encounters this pb, I know!).

<{POST_SNAPBACK}>

Here's a QuickSort that fixes the above problem. On my machine I can sort 5000 floats in about 2.7 seconds.

(With the new Variant class updates i submitted to Jon, it takes about 2.2 secs. - about 20% faster).

expandcollapse popup

Func _ArrayQuickSort(ByRef $array, $left = 0, $right = -99)
   If $right = -99 Then $right = UBound($array) - 1
   
   If $right - $left <= 10 Then
    ; InsertSort - fastest on small segments (= 25% total speedup)
      Local $i, $j, $t
      For $i = $left + 1 To $right
         $t = $array[$i]
         $j = $i
         While $array[$j - 1] > $t
            $array[$j] = $array[$j - 1]
            $j = $j - 1
            If ($j <= $left) Then ExitLoop
         Wend
         $array[$j] = $t
      Next
      Return
   EndIf
   
  ; QuickSort - fastest on large segments
   Local $pivot, $L, $R, $t, $k
   $pivot = $array[ ($left + $right)/2 ]
   $L = $left
   $R = $right
   Do
      While $array[$L] < $pivot
         $L = $L + 1
      Wend
      While $array[$R] > $pivot
         $R = $R - 1
      Wend
      $k = $L
      While $L <> $R And $array[$L] = $array[$R]
          $L = $L + 1
      Wend
      If $L = $R Then ExitLoop
     ; Swap
      $t = $array[$L]
      $array[$L] = $array[$R]
      $array[$R] = $t
   Until 0
      
   _ArrayQuickSort($array, $left, $k - 1)
   _ArrayQuickSort($array, $R + 1, $right)  
EndFunc

[Guest Guidosoft]

Freud would say its a "My e-penis is bigger than your e-penis" thing.

<{POST_SNAPBACK}>

Freud was a moron.

He said that when I go to sleep, everything I dream is about sex. He is retarded. LOL. HAHAHA!

[tylo]

A post of this drop-in replacement of _ArraySort() passed without any comments in the idea lab section, although the speedup is remarkable compared to the current implementation. It is now stable on any input (including all equal elements). EDIT: Did a simplification.

Test arrays: $Array1[2000], $Array2[2000][3]

Sort time $Array1: Current: 50 secs, New: 2.5 secs. Speedup: 20X
Sort time $Array2: Current: 60 secs, New: 4.6 secs. Speedup: 13X

expandcollapse popup

;===============================================================================
;
; Function Name:    _ArraySort()
; Description:    Sort an 1 or 2 dimensional Array on a specific index
;                  using the quicksort/insertsort algorithms.
; Parameter(s):  $a_Array     - Array
;                  $i_Descending - Sort Descending when 1
;                  $i_Base     - Start sorting at this Array entry.
;                  $I_Ubound     - End sorting at this Array entry.
;                                  Default UBound($a_Array) - 1
;                  $i_Dim       - Elements to sort in second dimension
;                  $i_SortIndex  - The Index to Sort the Array on.
;                                  (for 2-dimensional arrays only)
; Requirement(s):   None
; Return Value(s):  On Success - 1 and the sorted array is set
;                  On Failure - 0 and sets @ERROR = 1
; Author(s):        Jos van der Zande
;                  LazyCoder - added $i_SortIndex option
;                  Tylo - implemented stable QuickSort algo
;
;===============================================================================
;
Func _ArraySort(ByRef $a_Array, $i_Decending = 0, $i_Base = 0, $i_UBound = 0, $i_Dim = 1, $i_SortIndex = 0)
; Set to ubound when not specified
    If $i_UBound < 1 Then $i_UBound = UBound($a_Array) - 1
    
    If UBound($a_Array) <= $i_UBound Or Not IsNumber($i_UBound) Then
        SetError(1)
        Return 0
    EndIf

    If $i_Dim = 1 Then
        _ArrayQuickSort1D($a_Array, $i_Decending, $i_Base, $i_UBound)
    Else
        _ArrayQuickSort2D($a_Array, $i_Decending, $i_Base, $i_UBound, $i_Dim - 1, $i_SortIndex)
    EndIf
    Return 1
EndFunc ;==>_ArraySort


Func _ArrayQuickSort1D(ByRef $array, $decend, $left, $right)
    If $right - $left < 10 Then
    ; InsertSort - fastest on small segments (= 25% total speedup)
        Local $i, $j, $t
        For $i = $left + 1 To $right
            $t = $array[$i]
            $j = $i
            If $decend Then
                While $j > $left And $array[$j - 1] < $t
                    $array[$j] = $array[$j - 1]
                    $j = $j - 1
                Wend
            Else
                While $j > $left And $array[$j - 1] > $t
                    $array[$j] = $array[$j - 1]
                    $j = $j - 1
                Wend
            EndIf
            $array[$j] = $t
        Next
        Return
    EndIf
    
    ; QuickSort - fastest on large segments
    Local $pivot, $L, $R, $t
    $pivot = $array[($left + $right)/2]
    $L = $left
    $R = $right
    Do
        If $decend Then
            While $array[$L] > $pivot
                $L = $L + 1
            Wend
            While $array[$R] < $pivot
                $R = $R - 1
            Wend
        Else
            While $array[$L] < $pivot
                $L = $L + 1
            Wend
            While $array[$R] > $pivot
                $R = $R - 1
            Wend
        EndIf
    ; Swap
        If $L <= $R Then
            $t = $array[$L]
            $array[$L] = $array[$R]
            $array[$R] = $t
            $L = $L + 1
            $R = $R - 1
        EndIf
    Until $L > $R
        
    _ArrayQuickSort1D($array, $decend, $left, $R)
    _ArrayQuickSort1D($array, $decend, $L, $right)   
EndFunc


Func _ArrayQuickSort2D(ByRef $array, $decend, $left, $right, $bound2, $sortIdx)
    If $left >= $right Then Return
    Local $pivot, $L, $R, $t
    $pivot = $array[($left + $right)/2][$sortIdx]
    $L = $left
    $R = $right
    Do
        If $decend Then
            While $array[$L][$sortIdx] > $pivot
                $L = $L + 1
            Wend
            While $array[$R][$sortIdx] < $pivot
                $R = $R - 1
            Wend
        Else
            While $array[$L][$sortIdx] < $pivot
                $L = $L + 1
            Wend
            While $array[$R][$sortIdx] > $pivot
                $R = $R - 1
            Wend
        EndIf
        If $L <= $R Then
            For $x = 0 To $bound2
                $t = $array[$L][$x]
                $array[$L][$x] = $array[$R][$x]
                $array[$R][$x] = $t
            Next        
            $L = $L + 1
            $R = $R - 1
        EndIf
    Until $L > $R
        
    _ArrayQuickSort2D($array, $decend, $left, $R, $bound2, $sortIdx)
    _ArrayQuickSort2D($array, $decend, $L, $right, $bound2, $sortIdx)    
EndFunc

Edited October 21, 2013 by Jos

[SlimShady]

Does it also work that fast using the current version (3.1)?

I'll use it anyways.

Great job.

[tylo]

Does it also work that fast using the current version (3.1)?

I'll use it anyways.

Great job.

<{POST_SNAPBACK}>

Yep, I tested with 3.1.0.14.

Note that I simplified it a little (edited). It now works slightly faster with unsorted arrays, but slightly slower if you have long sequences with equal elements. No big deal. This is the very original quicksort algorithm with insertsort optimalization.

[Jos]

Will update the UDF lib. with this version...

[spiderblues]

Hi,

thanks for the listview sorting function. But how can I catch an event when selecting an item?

By clicking on the listview header, its sorting. When I click on an item, I want to run the code that's now on the edit button.

-> the item data should be shown in the input fields...

My next problem: how can i update the data oft the listview item when I changed the input fields???

...oh my god, I have to learn al lot!! :">

Can anybody help me?

spider

Here's the code:

expandcollapse popup

#include <GUIConstants.au3>
#include "ArrayLC.au3"
#include "ListViewUDFs.au3"

$LVM_DELETEITEM = 0x1008

Dim $filename = @ScriptDir & "\products.csv"
Dim $pgm_name = "Products"

If $CmdLine[0] > 0 Then $filename = $CmdLine[1]

$GUI = GUICreate($pgm_name,1000, 700, -1, -1,$WS_THICKFRAME + $WS_OVERLAPPEDWINDOW + $WS_VISIBLE + $WS_CLIPSIBLINGS)
Global $listview = GUICtrlCreateListView ("Product|Description|ItemNr.|Type|Date",10,40,600,500)
Global $inp_lv_1 = GuiCtrlCreateInput("", 10, 10, 80, 20); Edit
Global $inp_lv_2 = GuiCtrlCreateInput("", 100, 10, 80, 20); Edit
Global $inp_lv_3 = GuiCtrlCreateInput("", 190, 10, 80, 20); Edit
Global $inp_lv_4 = GuiCtrlCreateInput("", 280, 10, 80, 20); Edit
Global $inp_lv_5 = GuiCtrlCreateInput("", 370, 10, 80, 20); Edit

$btn_edit = GuiCtrlCreateButton ("Edit",10,550,70,20)

$file = FileOpen($filename, 0)

; Check if file opened for reading OK
If $file = -1 Then
    MsgBox(0, "Error", "Unable to open specified search results file...")
    Exit
EndIf
; Read in lines of text until the EOF is reached
While 1
    $line = FileReadLine($file)
    If @error = -1 Then ExitLoop
    GUICtrlCreateListViewItem(StringReplace($line,@TAB,"|"),$listview)
Wend
FileClose($file)

GUISetState()

Dim $b_Descending[_GUICtrlGetListViewColsCount($listview)]

Do
    $msg = GUIGetMsg ()
    Select
        Case $msg = $listview
        _SortListView($listview,$b_Descending,GuiCtrlGetState($listview))

        Case $msg = $btn_edit
        $strSelFile = StringSplit(GUICtrlRead(GUICtrlRead($listview)),"|")
        If $strSelFile[0] > 1 Then
            GUICtrlSetData ($inp_lv_1, $strSelFile[1])
            GUICtrlSetData ($inp_lv_2, $strSelFile[2])
            GUICtrlSetData ($inp_lv_3, $strSelFile[3])
            GUICtrlSetData ($inp_lv_4, $strSelFile[4])
            GUICtrlSetData ($inp_lv_5, $strSelFile[5])
        Else
            MsgBox(0, "Error", "Please select line to edit!")
        EndIf
    EndSelect
Until $msg = $GUI_EVENT_CLOSE

The products.csv:

Product 1    first description    123    Controller    8/29/2002 3:41 AM    
Product 2    description 2    65    Video    8/4/2004 12:56 AM    
Product 3    what's this?    987    Case         8/4/2004 12:56 AM

listview.au3

Edited April 14, 2005 by spiderblues