Sign in to follow this  
Followers 0
AlmarM

1D Array sorting algorithms

10 posts in this topic

#1 ·  Posted (edited)

Hiya,

I found these 1D Array sorting algorithms on Wiki and decided to translate them into AutoIt.

I've included a speedtest.

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

Share this post


Link to post
Share on other sites



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

Share this post


Link to post
Share on other sites

#3 ·  Posted (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 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.

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

#6 ·  Posted (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 by jaberwocky6669

Share this post


Link to post
Share on other sites

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]

Share this post


Link to post
Share on other sites

#8 ·  Posted (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! :shocked:

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

Share this post


Link to post
Share on other sites

@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 Gude
How 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

Share this post


Link to post
Share on other sites

@AlmarM

All the tests have the same line in them. Not to mention they all have the timerinit in them twice for some reason.

Whoops. XD

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

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