Randomly Sort an Array

[picea892]

Hi all

So, I'm considering my options for randomly sorting an array. _arraySort can sort ascending/descending.

I would have to utilize the random function. Except that continuously choosing random numbers between the array max and min seems to be a poor way of doing it. Does anyone have a thought on how to accomplish this?

Picea

[Melba23]

picea892,

I would do it this way - unless the array is seriously large, when all the Redims would slow it down unacceptably.

#include <Array.au3>

Global $aInput[9] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Global $aOutput[UBound($aInput)]

For $i = 0 To UBound($aInput) - 1

    _Get_Element($i)

Next

_ArrayDisplay($aOutput, "Output")

Func _Get_Element($iOutPutIndex)

    $iInputIndex = Random(0, UBound($aInput) - 1, 1)

    $aOutput[$iOutPutIndex] = $aInput[$iInputIndex]
    _ArrayDelete($aInput, $iInputIndex)

EndFunc

M23

[Yashied]

#Include <Array.au3>

Dim $Data[10] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

_ArrayDisplay($Data)
For $i = 1 To 100
    $A = Random(0, UBound($Data) - 1, 1)
    $B = Random(0, UBound($Data) - 1, 1)
    $Temp = $Data[$A]
    $Data[$A] = $Data[$B]
    $Data[$B] = $Temp
Next
_ArrayDisplay($Data)

[picea892]

Wow...great examples guys....And the solutions appear to be random....no solution is duplicated. I think that Melba23's example seems more random somehow.

Thanks again for these excellent solutions

[kaotkbliss]

isn't that kind of an oxymoron? randomly sort? random=chaotic, sort=to put in order

lol

[Melba23]

picea892,

Yashied's code is much faster if you are looking to randomise really large arrays - it is the _ArrayDelete (running ReDim internally) which is the killer. For a 10000 element array, my code takes around 90 sec, Yashied's a mere 1 sec. No contest really!

Moral: try to avoid ReDim if you can - particularly for large arrays!

M23

[Malkey]

picea892,

Yashied's code is much faster if you are looking to randomise really large arrays - it is the _ArrayDelete (running ReDim internally) which is the killer. For a 10000 element array, my code takes around 90 sec, Yashied's a mere 1 sec. No contest really!

Moral: try to avoid ReDim if you can - particularly for large arrays!

M23

Melba23

Yashied's code will not randomize large arrays.

The For-Next loop loops 100 times. The possible maximum number of elements that could be randomized is 200. For a 10,000 element array, 9,800 elements would remain the same, untouched.

[Melba23]

Malkey,

I had, of course, modified his code to run the loop 10 times the number of elements in the array.

He still won!

M23

P.S. If you are interested:

expandcollapse popup

#include <Array.au3>

Global $aInput[10000]
For $i = 0 To 9999
    $aInput[$i] = $i
Next

ConsoleWrite("Yashied starts" & @CRLF)

$iBegin = TimerInit()

For $i = 1 To UBound($aInput) * 10
    $A = Random(0, UBound($aInput) - 1, 1)
    $B = Random(0, UBound($aInput) - 1, 1)
    $Temp = $aInput[$A]
    $aInput[$A] = $aInput[$B]
    $aInput[$B] = $Temp
Next

ConsoleWrite("Yashied: " & TimerDiff($iBegin) & @CRLF)

ConsoleWrite("M23 starts" & @CRLF)

$iBegin = TimerInit()

Global $aOutput[UBound($aInput)]

For $i = 0 To UBound($aInput) - 1

    _Get_Element($i)

Next

ConsoleWrite("M23: " & TimerDiff($iBegin) & @CRLF)

Func _Get_Element($iOutPutIndex)

    $iInputIndex = Random(0, UBound($aInput) - 1, 1)

    $aOutput[$iOutPutIndex] = $aInput[$iInputIndex]
    _ArrayDelete($aInput, $iInputIndex)

EndFunc

[Yashied]

This is correct.

For $i = 1 To 2 * UBound($Data)

[Melba23]

Yashied,

Makes you even faster!

M23

[Yashied]

No, just x2 is the minimum required value for a satisfactory result.

[Melba23]

Yashied,

[serious]

I believe your statement as it seems quite reasonable from a common-sense point of view, but do you have a mathematical basis for saying 2*array_size is the minimum?

[/serious]

M23

[MvGulik]

whatever Edited February 7, 2011 by MvGulik

[Yashied]

I believe your statement as it seems quite reasonable from a common-sense point of view, but do you have a mathematical basis for saying 2*array_size is the minimum?

IMHO

#Include <Array.au3>

Dim $Data[1000]

For $i = 0 To UBound($Data) - 1
    $Data[$i] = $i
Next

For $i = 1 To 9
    $Count = 0
    $Temp = $Data
    _ArraySortRandom($Temp, $i)
    For $j = 0 To UBound($Temp) - 1
        If $Temp[$j] = $Data[$j] Then
            $Count += 1
        EndIf
    Next
    ConsoleWrite('x' & $i & ' => ' & (100 * $Count / UBound($Data)) & '% matches' & @CR)
Next

Func _ArraySortRandom(ByRef $aArray, $iMultiplier = 2)

    Local $A, $B, $Temp

    For $i = 1 To $iMultiplier * UBound($aArray)
        $A = Random(0, UBound($aArray) - 1, 1)
        $B = Random(0, UBound($aArray) - 1, 1)
        $Temp = $aArray[$A]
        $aArray[$A] = $aArray[$B]
        $aArray[$B] = $Temp
    Next
EndFunc   ;==>_ArraySortRandom

~2% (20 of 1000) matches for 1k points with x2 multiplier. More than x4 does not make sense to choose.

Edited February 21, 2010 by Yashied

[dani]

Why is the match % at x1 always so much higher than the rest? Result always looks like this:

x1 => 14.5% matches
x2 => 2.2% matches
x3 => 0.1% matches
x4 => 0.1% matches
x5 => 0.1% matches
x6 => 0.1% matches
x7 => 0.2% matches
x8 => 0.1% matches
x9 => 0.1% matches

Very strange right? $Temp always gets initialized back to $Data, which doesn't change, but still the % matches is extremely high (relatively) @ x1 compared to x2 and up...

~ edit

Oh lol nvm, I thought you were just running it 9 times with multiplier 2 but you use a different multiplier ($i from 1 To 9)

Edited February 21, 2010 by d4ni

[Yashied]

Add the following line in the beginning of the script:

SRandom(@AutoItPID)

[Melba23]

Yashied,

Thanks.

M23

[MvGulik]

whatever Edited February 7, 2011 by MvGulik

[jchd]

There is no need to scan the array multiple times as it can be done in O(N) instead of O(kN).

Durstenfeld variant of the Fisher–Yates algorithm works in a single pass, uses only one call to Random() and guarantees randomness not worst than the one provided by Random(). (And AutoIt Random is very good.)

#Include <Array.au3>

;;;;;; SRandom(@AutoItPID) don't use that.

Local Const $limit = 10000
Dim $Data[$limit]

For $i = 0 To $limit - 1
    $Data[$i] = $i
Next
_ArrayDisplay($Data)

For $i = UBound($Data) - 1 To 1 Step -1
    $j = Random(0, $i, 1)
    $Temp = $Data[$j]
    $Data[$j] = $Data[$i]
    $Data[$i] = $Temp
Next
_ArrayDisplay($Data)

EDIT: I didn't mean to actually use SRandom() at all. To be honest I don't remember why it was left there...

Edited July 21, 2014 by jchd

[GEOSoft]

Here's one that I got from SmOke_N several months back that might do what you want.

Func _ArrayRandomShuffle($av_array, $i_lbound = 0)
    Local $i_ubound = UBound($av_array) - 1
    Local $icc, $s_temp, $i_random
    
    For $icc = $i_lbound To $i_ubound
        $s_temp = $av_array[$icc]
        $i_random = Random($i_lbound, $i_ubound, 1)
        $av_array[$icc] = $av_array[$i_random]
        $av_array[$i_random] = $s_temp
    Next
    
    Return $av_array
EndFunc