AlmarM Posted September 27, 2010 Posted September 27, 2010 (edited) Hiya, I found these 1D Array sorting algorithms on Wiki and decided to translate them into AutoIt. I've included a speedtest. expandcollapse popup#include <Array.au3> #include <String.au3> Global $iTimer Global $iArraySize = InputBox("", "Array size?") Global $iNumTests = InputBox("", "Number of tests?") Global $myArray[$iArraySize], $avgArray[$iNumTests], $avgIndex = 0 _initArray() $GUI = GUICreate("Test results", 350, 360) $Edit = GUICtrlCreateEdit("", 0, 0, 350, 360) GUICtrlSetBkColor(-1, 0xFFFA9C) GUISetState() Sleep(100) _Debug("Bi-Directional Bubble Sort") For $i = 1 To $iNumTests $iTimer = TimerInit() _Array1D_BiDirectionalBubbleSort($myArray) $avgArray[$avgIndex] = TimerDiff($iTimer) $avgIndex += 1 _initArray() Next _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") $avgIndex = 0 _Debug(@CRLF & "Bubble Sort") For $i = 1 To $iNumTests $iTimer = TimerInit() _Array1D_BubbleSort($myArray) $avgArray[$avgIndex] = TimerDiff($iTimer) $avgIndex += 1 _initArray() Next _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") $avgIndex = 0 _Debug(@CRLF & "Comb Sort 11") For $i = 1 To $iNumTests $iTimer = TimerInit() _Array1D_CombSort11($myArray) $avgArray[$avgIndex] = TimerDiff($iTimer) $avgIndex += 1 _initArray() Next _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") $avgIndex = 0 _Debug(@CRLF & "Gnome Sort") For $i = 1 To $iNumTests $iTimer = TimerInit() _Array1D_GnomeSort($myArray) $avgArray[$avgIndex] = TimerDiff($iTimer) $avgIndex += 1 _initArray() Next _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") $avgIndex = 0 _Debug(@CRLF & "Heap Sort") For $i = 1 To $iNumTests $iTimer = TimerInit() _Array1D_HeapSort($myArray) $avgArray[$avgIndex] = TimerDiff($iTimer) $avgIndex += 1 _initArray() Next _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") $avgIndex = 0 _Debug(@CRLF & "Insertion Sort") For $i = 1 To $iNumTests $iTimer = TimerInit() _Array1D_InsertionSort($myArray) $avgArray[$avgIndex] = TimerDiff($iTimer) $avgIndex += 1 _initArray() Next _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") $avgIndex = 0 _Debug(@CRLF & "Selection Sort") For $i = 1 To $iNumTests $iTimer = TimerInit() _Array1D_SelectionSort($myArray) $avgArray[$avgIndex] = TimerDiff($iTimer) $avgIndex += 1 _initArray() Next _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") $avgIndex = 0 _Debug(@CRLF & "Selection Sort Ex (Modified by AlmarM)") For $i = 1 To $iNumTests $iTimer = TimerInit() _Array1D_SelectionSortEx($myArray) $avgArray[$avgIndex] = TimerDiff($iTimer) $avgIndex += 1 _initArray() Next _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") $avgIndex = 0 _Debug(@CRLF & "Shaker Sort") For $i = 1 To $iNumTests $iTimer = TimerInit() _Array1D_ShakerSort($myArray) $avgArray[$avgIndex] = TimerDiff($iTimer) $avgIndex += 1 _initArray() Next _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") $avgIndex = 0 _Debug(@CRLF & "AutoIt _ArraySort (Quick Sort)") For $i = 1 To $iNumTests $iTimer = TimerInit() _ArraySort($myArray) $avgArray[$avgIndex] = TimerDiff($iTimer) $avgIndex += 1 _initArray() Next _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") $avgIndex = 0 While 1 Switch GUIGetMsg() Case -3 Exit EndSwitch WEnd Func _Debug($sText) GUICtrlSetData($Edit, $sText & @CRLF, "|") EndFunc Func _initArray() For $i = 0 To UBound($myArray) - 1 $myArray[$i] = Chr(Random(97, 122, 1)) Next EndFunc ;Bi-Directional Bubble Sort (by James Gosling) Func _Array1D_BiDirectionalBubbleSort(ByRef $aArray, $iDescending = 0) Local $iLength = UBound($aArray) - 1 Local $iSt = -1 While ($iSt < $iLength) $bFlipped = False $iSt += 1 $iLength -= 1 For $j = $iSt To $iLength If (StringCompare($aArray[$j], $aArray[$j + 1]) > 0) Then _ArraySwap($aArray[$j], $aArray[$j + 1]) $bFlipped = True EndIf Next For $j = $iLength To $iSt Step -1 If (StringCompare($aArray[$j], $aArray[$j + 1]) > 0) Then _ArraySwap($aArray[$j], $aArray[$j + 1]) $bFlipped = True EndIf Next If (Not $bFlipped) Then ExitLoop WEnd If ($iDescending) Then _ArrayReverse($aArray) EndFunc ;Bubble Sort (by James Gosling and Jason Harrison) Func _Array1D_BubbleSort(ByRef $aArray, $iDescending = 0) Local $iLength = UBound($aArray) - 1 For $i = $iLength To 0 Step -1 $bFlipped = False For $j = 0 To $i - 1 If (StringCompare($aArray[$j], $aArray[$j + 1]) > 0) Then _ArraySwap($aArray[$j], $aArray[$j + 1]) $bFlipped = True EndIf Next If (Not $bFlipped) Then ExitLoop Next If ($iDescending) Then _ArrayReverse($aArray) EndFunc ;Comb Sort 11 (by Jason Harrison) Func _Array1D_CombSort11(ByRef $aArray, $iDescending = 0) Local $iShrink = 1.247330950103979 Local $bFlipped = True Local $iGap = UBound($aArray) Local $iTop, $j While ($bFlipped Or $iGap > 1) $iGap = Int($iGap / $iShrink) Switch ($iGap) Case 0 $iGap = 1 Case 9 To 10 $iGap = 1 EndSwitch $bFlipped = False $iTop = UBound($aArray) - $iGap For $i = 0 To $iTop - 1 $j = $i + $iGap If (StringCompare($aArray[$i], $aArray[$j]) > 0) Then _ArraySwap($aArray[$i], $aArray[$j]) $bFlipped = True EndIf Next WEnd If ($iDescending) Then _ArrayReverse($aArray) EndFunc ;Gnome Sort (Hamid Sarbazi-Azad) Func _Array1D_GnomeSort(ByRef $aArray, $iDescending = 0) Local $iPos = 1 While ($iPos < UBound($aArray)) If ($aArray[$iPos] >= $aArray[$iPos - 1]) Then $iPos += 1 Else _ArraySwap($aArray[$iPos], $aArray[$iPos - 1]) If ($iPos > 1) Then $iPos -= 1 EndIf EndIf WEnd If ($iDescending) Then _ArrayReverse($aArray) EndFunc ;Heap Sort (by Jason Harrison) Func _Array1D_HeapSort(ByRef $aArray, $iDescending = 0) Local $iLength = UBound($aArray) For $i = ($iLength / 2) To 1 Step -1 __HeapSort_DownHeap($aArray, $i, $iLength) Next While ($iLength > 1) _ArraySwap($aArray[0], $aArray[$iLength - 1]) $iLength -= 1 __HeapSort_DownHeap($aArray, 1, $iLength) WEnd If ($iDescending) Then _ArrayReverse($aArray) EndFunc ;Insertion Sort (by Jason Harrison) Func _Array1D_InsertionSort(ByRef $aArray, $iDescending = 0) For $i = 1 To UBound($aArray) - 1 $j = $i $aB = $aArray[$i] While (($j > 0) And $aArray[$j - 1] > $aB) $aArray[$j] = $aArray[$j - 1] $j -= 1 WEnd $aArray[$j] = $aB Next If ($iDescending) Then _ArrayReverse($aArray) EndFunc ;Selection Sort (by Jason Harrison) Func _Array1D_SelectionSort(ByRef $aArray, $iDescending = 0) For $i = 0 To UBound($aArray) - 1 $iMin = $i For $j = ($i + 1) To UBound($aArray) - 1 If (StringCompare($aArray[$j], $aArray[$iMin]) < 0) Then $iMin = $j EndIf Next _ArraySwap($aArray[$iMin], $aArray[$i]) Next If ($iDescending) Then _ArrayReverse($aArray) EndFunc Func _Array1D_SelectionSortEx(ByRef $aArray, $iDescending = 0) Local $iLength = UBound($aArray) - 1 Local $i = 0 While ($i <= $iLength) $iMin = $i For $j = ($i + 1) To $iLength If (StringCompare($aArray[$j], $aArray[$iMin]) < 0) Then $iMin = $j Next _ArraySwap($aArray[$iMin], $aArray[$i]) $i += 1 WEnd If ($iDescending) Then _ArrayReverse($aArray) EndFunc ;Shaker Sort (by Jason Harrison) Func _Array1D_ShakerSort(ByRef $aArray, $iDescending = 0) Local $i = 0 Local $iLength = UBound($aArray) -1 While ($i < $iLength) $iMin = $i $iMax = $i For $j = ($i + 1) To $iLength If (StringCompare($aArray[$j], $aArray[$iMin]) < 0) Then $iMin = $j EndIf If (StringCompare($aArray[$j], $aArray[$iMax]) > 0) Then $iMax = $j EndIf Next _ArraySwap($aArray[$iMin], $aArray[$i]) If ($iMax == $i) Then _ArraySwap($aArray[$iMin], $aArray[$iLength]) Else _ArraySwap($aArray[$iMax], $aArray[$iLength]) EndIf $i += 1 $iLength -= 1 WEnd If ($iDescending) Then _ArrayReverse($aArray) EndFunc ; +======================================= Extra Func __HeapSort_DownHeap(ByRef $aArray, $i, $iLength) Local $iTmp = $aArray[$i - 1] While ($i <= $iLength / 2) $j = $i * 2 If (($j < $iLength) And ($aArray[$j - 1] < $aArray[$j])) Then $j += 1 EndIf If (StringCompare($iTmp, $aArray[$j - 1]) >= 0) Then ExitLoop Else $aArray[$i - 1] = $aArray[$j - 1] $i = $j EndIf WEnd $aArray[$i - 1] = $iTmp EndFunc Func _Array1D_Average(ByRef $aArray) Local $aTotal = _Array1D_Total($aArray) Return ($aTotal[0] / $aTotal[1]) EndFunc Func _Array1D_Total(ByRef $aArray) Local $iTmp = 0, $iTmp2 Local $iLength = UBound($aArray) Local $aReturn[2] For $i = 0 To $iLength - 1 $iTmp2 = $iTmp $iTmp = $aArray[$i] + $iTmp2 Next $aReturn[0] = $iTmp $aReturn[1] = $iLength Return $aReturn EndFunc Edited September 27, 2010 by AlmarM Minesweeper A minesweeper game created in autoit, source available. _Mouse_UDF An UDF for registering functions to mouse events, made in pure autoit. 2D Hitbox Editor A 2D hitbox editor for quick creation of 2D sphere and rectangle hitboxes.
czardas Posted September 27, 2010 Posted September 27, 2010 I have to say this is quite interesting. I never heard of these algorithms before. Thanks for sharing. Next time I see bubbles in the bath I'll be thinking about this. operator64 ArrayWorkshop
AlmarM Posted September 27, 2010 Author Posted September 27, 2010 (edited) There are some more though, I didn't feel like translating all... yet. FIXED: Comb Sort 11, fixed the 56 array length limit Edited September 27, 2010 by AlmarM Minesweeper A minesweeper game created in autoit, source available. _Mouse_UDF An UDF for registering functions to mouse events, made in pure autoit. 2D Hitbox Editor A 2D hitbox editor for quick creation of 2D sphere and rectangle hitboxes.
pierrotm777 Posted September 27, 2010 Posted September 27, 2010 I have an error, D:\Program Files\Ride Runner\Skins\Carwings_Dynamic_pm_new\Scripts\GoogleMapsTrack\Google Maps UDF\1d array.au3(51,88) : ERROR: Debug(): undefined function. Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^ D:\Program Files\Ride Runner\Skins\Carwings_Dynamic_pm_new\Scripts\GoogleMapsTrack\Google Maps UDF\1d array.au3 - 1 error(s), 0 warning(s)
pierrotm777 Posted September 27, 2010 Posted September 27, 2010 Sorry, I have found the error on the line 51. i have modified, Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") by _Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms")
jaberwacky Posted September 27, 2010 Posted September 27, 2010 (edited) CombSort11 has a bug. Edit: my Array size was 1000 and the amount of tests was 5. ;Comb Sort 11 (by Jason Harrison) Func _Array1D_CombSort11(ByRef $aArray, $iDescending = 0) Local $iShrink = 1.247330950103979 Local $bFlipped = True Local $iGap = UBound($aArray) Local $iTop, $j While ($bFlipped Or $iGap > 1) $iGap = Int($iGap / $iShrink) Switch ($iGap) Case 0 $iGap = 1 Case 9 To 10 $iGap = 1 EndSwitch $bFlipped = False $iTop = UBound($aArray) - $iGap For $i = 0 To $iTop - 1 ; there was an off by one bug here, fixed by subtracting 1 from $iTop $j = $i + $iGap If (StringCompare($aArray[$i], $aArray[$j]) > 0) Then _ArraySwap($aArray[$i], $aArray[$j]) $bFlipped = True EndIf Next WEnd If ($iDescending) Then _ArrayReverse($aArray) EndFunc ;==>_Array1D_CombSort11 Edited September 27, 2010 by jaberwocky6669 Helpful Posts and Websites: AutoIt3 Variables and Function Parameters MHz | AutoIt Wiki | Using the GUIToolTip UDF BrewManNH | Can't find what you're looking for on the Forum?
Achilles Posted September 27, 2010 Posted September 27, 2010 Good job on these! I learned about sorts but never used them much.. It's nice to know that _ArraySort is the fastest (at least for what I tested on).. I also got a bug like pierrotm777, but adding a _ on line 51 fixed it... My Programs[list][*]Knight Media Player[*]Multiple Desktops[*]Daily Comics[*]Journal[/list]
AlmarM Posted September 27, 2010 Author Posted September 27, 2010 (edited) I have an error, D:\Program Files\Ride Runner\Skins\Carwings_Dynamic_pm_new\Scripts\GoogleMapsTrack\Google Maps UDF\1d array.au3(51,88) : ERROR: Debug(): undefined function. Debug("Average of " & $iNumTests & " tests: " & _Array1D_Average($avgArray) & " ms") ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^ D:\Program Files\Ride Runner\Skins\Carwings_Dynamic_pm_new\Scripts\GoogleMapsTrack\Google Maps UDF\1d array.au3 - 1 error(s), 0 warning(s) Fixed, indeed. CombSort11 has a bug. Edit: my Array size was 1000 and the amount of tests was 5. ;Comb Sort 11 (by Jason Harrison) Func _Array1D_CombSort11(ByRef $aArray, $iDescending = 0) Local $iShrink = 1.247330950103979 Local $bFlipped = True Local $iGap = UBound($aArray) Local $iTop, $j While ($bFlipped Or $iGap > 1) $iGap = Int($iGap / $iShrink) Switch ($iGap) Case 0 $iGap = 1 Case 9 To 10 $iGap = 1 EndSwitch $bFlipped = False $iTop = UBound($aArray) - $iGap For $i = 0 To $iTop - 1 ; there was an off by one bug here, fixed by subtracting 1 from $iTop $j = $i + $iGap If (StringCompare($aArray[$i], $aArray[$j]) > 0) Then _ArraySwap($aArray[$i], $aArray[$j]) $bFlipped = True EndIf Next WEnd If ($iDescending) Then _ArrayReverse($aArray) EndFunc ;==>_Array1D_CombSort11 Thanks for the fix! Array Size: 1000 Bi-Directional Bubble Sort Average of 5 tests: 2618.166464 ms Bubble Sort Average of 5 tests: 2734.759256 ms Comb Sort 11 Average of 5 tests: 108.901704 ms Gnome Sort Average of 5 tests: 3513.856176 ms Heap Sort Average of 5 tests: 90.228976 ms Insertion Sort Average of 5 tests: 786.640128 ms Selection Sort Average of 5 tests: 1170.004328 ms Shaker Sort Average of 5 tests: 1181.376272 ms AutoIt _ArraySort (Quick Sort) Average of 5 tests: 29.564184 ms Great results indeed. Watching the algorithms do their best while Comb Sort 11, Heap Sort and the AutoIt Quick Sort do it like a piece of cake is fun! EDIT: Hey hey hey! I just noticed I missed _initArray() $iTimer = TimerInit() Inside the _ArraySort test. That's why it was so rediculous fast. Edited September 27, 2010 by AlmarM Minesweeper A minesweeper game created in autoit, source available. _Mouse_UDF An UDF for registering functions to mouse events, made in pure autoit. 2D Hitbox Editor A 2D hitbox editor for quick creation of 2D sphere and rectangle hitboxes.
BrewManNH Posted September 27, 2010 Posted September 27, 2010 @AlmarM All the tests have the same line in them. Not to mention they all have the timerinit in them twice for some reason. If I posted any code, assume that code was written using the latest release version unless stated otherwise. Also, if it doesn't work on XP I can't help with that because I don't have access to XP, and I'm not going to.Give a programmer the correct code and he can do his work for a day. Teach a programmer to debug and he can do his work for a lifetime - by Chirag GudeHow to ask questions the smart way! I hereby grant any person the right to use any code I post, that I am the original author of, on the autoitscript.com forums, unless I've specifically stated otherwise in the code or the thread post. If you do use my code all I ask, as a courtesy, is to make note of where you got it from. Back up and restore Windows user files _Array.au3 - Modified array functions that include support for 2D arrays. - ColorChooser - An add-on for SciTE that pops up a color dialog so you can select and paste a color code into a script. - Customizable Splashscreen GUI w/Progress Bar - Create a custom "splash screen" GUI with a progress bar and custom label. - _FileGetProperty - Retrieve the properties of a file - SciTE Toolbar - A toolbar demo for use with the SciTE editor - GUIRegisterMsg demo - Demo script to show how to use the Windows messages to interact with controls and your GUI. - Latin Square password generator
AlmarM Posted September 27, 2010 Author Posted September 27, 2010 @AlmarMAll the tests have the same line in them. Not to mention they all have the timerinit in them twice for some reason.Whoops. XDUpdated first post, also added "_Array1D_SelectionSortEx". Minesweeper A minesweeper game created in autoit, source available. _Mouse_UDF An UDF for registering functions to mouse events, made in pure autoit. 2D Hitbox Editor A 2D hitbox editor for quick creation of 2D sphere and rectangle hitboxes.
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now