AlmarM Posted September 27, 2010 Share 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. Link to comment Share on other sites More sharing options...
czardas Posted September 27, 2010 Share 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 Link to comment Share on other sites More sharing options...
AlmarM Posted September 27, 2010 Author Share 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. Link to comment Share on other sites More sharing options...
pierrotm777 Posted September 27, 2010 Share 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) Link to comment Share on other sites More sharing options...
pierrotm777 Posted September 27, 2010 Share 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") Link to comment Share on other sites More sharing options...
jaberwacky Posted September 27, 2010 Share 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? Link to comment Share on other sites More sharing options...
Achilles Posted September 27, 2010 Share 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] Link to comment Share on other sites More sharing options...
AlmarM Posted September 27, 2010 Author Share 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. Link to comment Share on other sites More sharing options...
BrewManNH Posted September 27, 2010 Share 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 Link to comment Share on other sites More sharing options...
AlmarM Posted September 27, 2010 Author Share 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. Link to comment Share on other sites More sharing options...
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