Inverse of a SORT is that possible ?

[DeXtr0]

Hey everybody,

I'm not sure if this question can be posted here (however I do hope so).

I got the following issue and I have no clue how to start coding it:

I got 1 sorted numeric array with values from 1 to 100.
I want this array to be mixed or mangled or how do you call this. So actually the opposite of a sort.

However each element may only appear 1 time. Therefor I tried with the random function but this does not work here.

What I would like to get back is 1 array where all the values are in a random order.

Does anybody has an idea or can shed me a light on this one ?


All help is welcome.

Cheers,
DeXtr0

[srod]

Here's one way, probably not very efficient but is all I have time for right now and is not very well tested :

Code: Select all

#ArrayUpperBound = 99

;Set up a sorted array
  Dim Array(#ArrayUpperBound)
  For i = 0 To #ArrayUpperBound
    Array(i) = i+1
  Next

;Now randomize the bugger.
  ;Copy the entire array to a temp array.
    Dim temp(#ArrayUpperBound)
    CopyMemory(Array(), temp(), (#ArrayUpperBound+1)*SizeOf(Long))
  For i = #ArrayUpperBound To 0 Step -1
    pos = Random(i)
    Array(i) = temp(pos)
    If pos<i
      MoveMemory(@temp(pos+1), @temp(pos), (#ArrayUpperBound-pos)*SizeOf(Long))
    EndIf
  Next
  ;Clear the temporary array.
    Dim temp(0)
  ;Have a look at the new array.
  For i = 0 To #ArrayUpperBound
    Debug Array(i)
  Next

[akj]

This is not the most efficient way, but it works:

Code: Select all

; Unsort  AKJ  05-Nov-07

; Create and fill the array
Define i
Dim a(100)
For i= 0 To 100
  a(i)=i
Next i

; Unsort the array by randomly swapping elements
RandomSeed(ElapsedMilliseconds())
For i=1 To 300
  Swap a(1+Random(99)), a(1+Random(99)) ; Each random number is 1..100
Next i

; Display the unsorted array
For i= 1 To 100
  Debug a(i)
Next i

End

[srod]

Hi akj,

I was thinking of using a similar method but I reckon that in order to approach a true randomisation you'll need a lot more swaps - about 10000 for 100 elements (100*100).

For 1000 elements you should ideally use 1000000 (1000*1000) swaps.

Still, it's probably no slower than my method!

[DeXtr0]

Hey Guys,

thank you both for the answers. They both worked great !

Really appreciated your help !

Cheers,
DeXtr0

[Trond]

This is not exactly what you asked for, but I can't see why it can't be used:

Code: Select all

Procedure Shuffled(Array.l(1), L)
  Dim Slots(L)
  For I = 0 To L
    Repeat
      Value = Random(L)
    Until Slots(Value) = 0
    Slots(Value) = 1
    Array(I) = Value
  Next
EndProcedure

Dim A(100)

Shuffled(A(), 100)
For i= 0 To 100
  Debug a(i)
Next

SortArray(A(), 0)
For i= 0 To 100
  Debug a(i)
Next

[rsts]

Very nice Trond.

cheers

[DeXtr0]

Yeps works too,

Thanks trond, appreciate your solution as well

Regards,
DeXtr0

[srod]

Aye, very nice.

In theory though, this method could lock up, forever in seach of that last 'free' element!

That fact that it doesn't lock up is quite surprising; down to the shear speed of today's processors I reckon! Kind of like the following which I would expect to run for a long long time before finishing :

Code: Select all

Repeat
Until Random(100000000) = 10

Debug "Located 10 !"

[Derek]

down to the shear speed of today's processors I reckon!

Code: Select all

Repeat
Until Random(100000000) = 10

Debug "Located 10 !"

Still took 20 seconds on my fast processor.

[DoubleDutch]

This should be fast enough...

Code: Select all

Structure unsort
	number.l
	random.l
EndStructure

Dim Array.unsort(99)

For loop=0 To 99
	Array(loop)\number=loop+1
	Array(loop)\random=Random(100000)
Next

SortStructuredArray(Array(),0,OffsetOf(unsort\random),#PB_Sort_Long)

For loop=0 To 99
	Debug("["+Str(loop)+"] = "+Str(Array(loop)\number))
Next

[srod]

Very nice method; wouldn't have thought of that!

Still of quadratic order though because of the sort structured array, like all the algorithms here.

[DoubleDutch]

But the speed of the sort routine more than makes up for it.

It's a lot faster than doing it direct in PB. I use the PB sort routines for loads of things, they are great.

[citystate]

I've always used a similar approach to AKJ...

Code: Select all

; Create and fill the array 
Define i 
Dim a(100) 
For i= 0 To 100 
  a(i)=i 
Next i 

; Unsort the array by randomly swapping elements 
RandomSeed(ElapsedMilliseconds()) 
For i=0 To 100 
  Swap a(i), a(Random(100)) 
Next i 

; Display the unsorted array 
For i= 1 To 100 
  Debug a(i) 
Next i 

End

[blueznl]

down to the shear speed of today's processors I reckon!

Code: Select all

Repeat
Until Random(100000000) = 10

Debug "Located 10 !"

Still took 20 seconds on my fast processor.

I shouldn't do these things, but I actually did a number of runs in the background, debugger on, and doing some forum browsing at the same time... and they average out at 11 seconds here