Array sorting

So I need to implement a method to sort an array. The array itself is pretty small (only 6 values) but I need to sort many of these per frame, up to possibly 50 or more per frame. A couple of quesitons:

1. Is this a situation where the type of sort would make a difference?

2. Are there any examples of good sorting algorithms implemented with events floating around? I'd appreciate one, as I find coding with Events very unintuitive when it comes to this sort of stuff, unless it's the most basic of algorithms.

1) Yes, but it's about microseconds with such small range of values, so you don't need to take it into account.

2) I never stopped pointing towards my example game "Verve!". It covers so much and of course it also shows how to sort an array. It uses a more complex but time-stable algorithm. http://www.scirra.com/forum/example-verve-a-mini-game-of-skill_topic41461.html

You could do a simple bubble sort as well. It will get slower the higher the count of values to sort, but that's negligible with the count you have in mind.

Thanks for the reply!

I'll take a look at Verve when I get home from work. If your algorithm is faster I'll try to implement it as a general function, since I may later need it to sort something else of larger size. Best to futureproof stuff I implement as much as possible :) Just out of curiosity, what is a time-stable algorithm?

English is not my native language, so I might have chosen an inaccurate expression.

With time-stable I mean that the presented "divide&conquer" algorithm in Verve always needs the same amount of time to sort per cycle, no matter if there are, e.g. 100 or 100000 elements to sort, while bubble sort uses much more time per cycle if there are more elements.

EDIT: For example, with 100000 elements the algorithm in Verve always needs about 8 cycles to sort, while bubble sort in the worst case needs 99999 cycles.

I cannot for the life of me figure out that example haha. I'm not sure which of those events I actually need. Seems some are resizing arrays, and I'm not sure if that's part of the sort. And I'm not quite sure what the 'ScoreCard' is doing. The array being sorted is pPoints right? Seems to me this searches for a spot to insert the value rather than sorting a bunch of values, right? But what if I have a pre-existing array with values already in it that I need to sort? Do I need to create another array and pull values from the first array to the second array one by one in order to sort?

If this isn't too much to ask, do you think you can maybe show me an example of this that just accepts an existing array and sorts it? Is it possible to make it general so that you can somehow pass the array to a sorting function, and have it sorted, or is this not possible? E.g. if you put all the arrays in a family, then call the function on that family and pick the array by name.

Maybe events is not the right approach for this. Is this something that can be done simply in python so I can copy-paste it? :P

To the first paragraph: Everything is heavily commented and all the questions are answered in the explanation of the sort algorithm. Yes, the array grows as more and more elements are added to the hiscore. But the algorithm doesn't care about the size of the array. All it needs is a value to find the correct position for. Works just the same on static arrays, too.

An easier way is the bubble sort algorithm. I already linked to it.

When you are willing to use Python it gets even easier for you (but I'm nt sure about speed issues with larger iterables). Just use the built-in function sorted() or the list's built-in method sort(). They both work the same. Here's an example using sorted():

+ System: Start of layout

++ Python script: a = sorted([5, 1, 3, 2, 4])

++ System: For "" from 0 to 4

--> Text: Set text to .Text & Python("a[" & LoopIndex & "]") & NewLine

It will output

1

2

3

4

5

Yeah I read the comments, and even though I sort of get the theory, I guess I was just (still am) confused as to how I would use this in a static array, I'll try to for a bit more to figure it out, and then I'll probably resort to python :) Thanks!

Just don't get irritated by the resizing of the arrays. The algorithm itself does nothing else than loop through the array to match a position based on a value given. So, to sort a pre-existing array, you would need to call the sorting again and again, for every value. Just retrieve the value to sort, replace the cell with a value that won't normally occur (e.g. -1 in an array that only stores positive values, or a string in an array that stores numbers) and add an exception condition that ignores such replaced cell. The position value you get, is the exact position (no need to +1 it). Copy the cell at that position to the replaced one and enter the current value at the new position.

I will try to do an example for pre-existing arrays, but I'm very busy with a project right now, so please be patient (Or maybe you figure it out for yourself? Would like to hear it then, so I wouldn't need to do the example)

Happy developing :)

EDIT: I just read a bit more about Timsort, the algorithm used in Python. It actually is a quite clever one, recognizing already sorted parts and working only on subsets that need to be sorted. Not a bad choice to use it.

Does that work? I think I'm misunderstanding the algorithm. It seemed to me that it is based on having the array into which you insert a value already sorted.

E.g. if I have these values 4 8 9 3 5

If I have an empty array A into which these will be placed, then when I loop through, A = 4, and sorted since only 4 is there. Then on the next loop, A = [4 8] and sorted. THen when I try to put in 9, again, it's going into a sorted array A = [4 8 9] and so on and so on.

With your suggestion, every value goes into a jumbled array, on the first iteration, A = [-1 8 9 3 5] = [8 9 3 5] and I'm trying ot put 4 into this unsorted array. This is why I'm confused. I can't tell whether the algorithm will work the same in both situations. My thought is that I need to have another Array B, and then do something like loop through all values of A, and sort them over in B (then copy B to A).

Since you're busy and the python algorithm is good (I looked it up it compares favorably to most others) I think I'll go ahead and use that since it's really easy to use. Thanks for showing me how and figuring out what sort it is :)

On a related note, can I access Construct arrays in python in a standard way or do I have to assign their values to a python array?

E.g. if I have an array SortArray in construct, can I do this:

sorted(range(len(SortArray)), key=lambda k: SortArray[k])

to get the indices of the sort, or will this fail? (For one, COnstruct arrays are 1 based and python are 0 based etc).

Juryiel

For python you'd have to convert them to a python array:

pyArray = map(lambda k:Array(k+1), range(Array.SizeX))

pyArray.sort()

for x,val in pyArray:
   Array.SetAtX(x+1,val)

Here's my second attempt (actually using S and not arrays), but it fails on a syntax error on the first line. I guess I'm not using S correctly in python:

AggroSortArrayPy = map(lambda k:S.n{"NPCHatelist",str(SOL.Enemy1spawn.UID,k), range(S.sule({"NPCHatelist",str(SOL.Enemy1spawn.UID)})))

AggroOrderPy=sorted(range(len(AggroSortArrayPy)), key=lambda k: AggroSortArrayPy[k])

You can't access array expressions in Construct like {"NPCHatelist",str(SOL.Enemy1spawn.UID)} or Sprite.XY from python. You'll have to do a hybrid approach with events and python.

Ok, I'll just transfer the {"NPCHatelist",str(SOL.Enemy1spawn.UID)} contents to a standard Array I suppose, then run the code on the array.

Thanks guys :)

Hmm the map function is giving me an IndexError :(

EDIT: Nevermind, forgot to make the array global