Sorting values in an int array

[Baguettator]

Hi !

I come with a new brain problem.

I have "stocked" some coordinates of objects (tokens for my game) into 3 arrays of int :

TypeZoneExp : indicates the type of the zone (it's an int, but I'm using an enum to not be lost with numbers...)
XZoneExp : the x-coordinate of the zone "i"
YZoneExp : the y-coordinate of the zone "i"

where i can be a number like 30 or 40 max, it depends of the map (the size of the arrays is changing according to the needs).

I want to sort the zones' coordinates from the top left to the down-right. So the first line of zones (YZoneExp = 0, for example), then the seconde line etc...

Is there any built-in function to do that ? Or useful functions ?

If not, I imagine using loops and loops, but maybe it can be done easier

EDIT : I just precise the situation :

In a chosen map, I want some tokens to be placed. I stock their coordinates so I can manipulate them later.
For example, five tokens :
t1(0, 100)
t2(0,250)
t3(100,150)
t4(50, 0)
t5(25, 100)

Each coordinate is stocked in an array, so : XZoneExp[0]=0, XZoneExp[1]=0, XZoneExp[2]=100, XZoneExp[3]=50, XZoneExp[4]=25 and YZoneExp[0]=100, YZoneExp[1]=250, YZoneExp[2]=250, YZoneExp[3]=0 and YZoneExp[4]=100;

What I want is to sort the tokens' coordinates from the top-left to the down-right. It would be : t4, t1, t5, t3, t2

And so their values "match" in the two arrays : XZoneExp[0]=50, YZoneExp[0]=0 ; XZoneExp[1]=0, YZoneExp[1]=100 etc...

[eri0o]

I don't understand what are your needs exactly - looks like a question that would be easier to understand with a drawing.

But here's a quicksort implementation in AGS script:

https://github.com/ericoporto/agsscript-algorithms/blob/master/quicksort/qsort.asc

The rest of the repository has an ags game project with it used that you can try.

Here's it's forum topic with a screen capture gif:

https://www.adventuregamestudio.co.uk/forums/index.php?topic=58293.0

[Baguettator]

Thanks ErioO ! I edited my post with more precisions (I was doing it when you answered )

I'm going to have a look to the links also !

[Baguettator]

I had a look to your algorythm. Very good job !

My problem is that I need to sort two arrays at the same time.

It would mean that when you find the lowest y-coordinates, you put it in the 1st place of the new array, while putting also the relative x-coordinate to the 1st place of the other new array.

[eri0o]

Instead of using three arrays, it's easier to make a struct and then make an array of that struct.

For sorting, you want to find a function that returns a "weight" that you can compare between two things, and then you will order by applying this "weight" function on your struct.

If your are not ordering many things or are not doing often, other algorithm that is really simple to implement (but very inefficient) is bubble sort, here's it in ags script: https://github.com/ericoporto/i_rented_a_boat/blob/41c1682a202e7fa49221eac9f13a4e961fec7a48/I_rented_a_boat/Flock.asc#L23

When you say top-left -> down-right, it's not clear if you want to calculate the length of the vector as your weight function (sqrt(x*x+y*y)) or if you have something else in mind.

[Baguettator]

When I say from top-left to down-right, I mean : if the map's top left corner has the (0, 0) coordinates, I want my zones to be sorted from the highest line (y=0) to the lowest, and also from left (x=0) to right (y=0). It means : between z1(0, 50), z2(20, 50) and z3(40, 0) , z3 is the first zone (y=0) and z1 is sorted before z2.

Well I'm not sure to understand what you expect me to do with the struct... could you explain me a bit more please ?

Thanks for the help, anyway !

[eri0o]

The idea of the struct is to group things that belongs to the same element:

https://adventuregamestudio.github.io/ags-manual/ScriptKeywords.html#struct

In your case, it would be a MapZone (I find a bit weird the usage of "zone" naming, but I guess each has a sprite which it would have a width and height too, right?) . Then this element would have the properties of X, Y positions and the Type.

With this, you can now make an array of MapZone.

This should help you to break down the goal you have in mind in smaller achievable tasks.

[Baguettator]

Hmm, the only thing I want to stock is the coordinates (it will help me to automatically place tokens on the map with dedicated functions, just by naming the "number" of the "zone" where I place "which" token).

I have a struct "Cartes", where I could stock these arrays if needed. But I don't understand how it will help to sort the variables ?

[Baguettator]

OK, so I tried something by using your algorythm EriOo. But when I launch AGS, and try the function, I have an error :

"Stack Overflow" on lines : "_swap(arr, i, j);" in "partition", then in "int p = _partition(arr, lo, hi)" and "_quicksort(arr, p+1, hi)" in "_quicksort".

What does it mean ?

[Baguettator]

It seems I can't sort an array that has a too great size.

So I'm still looking for a solution, if someone has an idea... Many thanks for helping !

[Baguettator]

Yes it seems I had to sort a smaller array, I managed to solve it.

By the way, I still have problems to script the sorting of my coordinates through the two arrays :S

Anyone has an idea please ?

(sorry for the multiposts...)

[eri0o]

You need to show your code, it's hard to give help with a script if you don't show it. It's also a good idea to explain why you are doing what you are doing.

[Khris]

You need something like this:

Code: ags

void SortArrays() {

  int items = 100; // 100 tokens
  int w = 300; // map width
  int swap;

  for (int i = 0; i < items - 1; i++) {
    for (int j = i + 1; j < items; j++) {
      if (YZoneExp[i] * w + XZoneExp[i] > YZoneExp[j] * w + XZoneExp[j]) {
        swap = TypeZoneExp[i];
        TypeZoneExp[i] = TypeZoneExp[j];
        TypeZoneExp[j] = swap;
        swap = XZoneExp[i];
        XZoneExp[i] = XZoneExp[j];
        XZoneExp[j] = swap;
        swap = YZoneExp[i];
        YZoneExp[i] = YZoneExp[j];
        YZoneExp[j] = swap;
      }
    }
  }
}

[Baguettator]

Hi !

Sorry for the delay, I was very busy with other things of life... I didn't take the time to answer.

I finally managed to do that, but it seems my script is a lot heavier than Khris's one, so maybe I'm going to update it.

Thanks for your help, and also, sorry for the late answer !!!

[Baguettator]

Hi there !

@Khris : I have re-read your solution, and I would like to implement it in my code. But first, I would like to understand what your code is doing...

Could you explain me what it is doing ? I'm not sure I have fully understood your code...

What is "map width" ?

[fernewelten]

What is "map width" ?

The highest value that your X coordinate can take, plus 1.

You say that you are working on a map. So each cell will have an X coordinate and a Y coordinate.
Let's say X coordinates run from 0 to (width - 1) (so that there are exactly 'width' coordinates)
and Y coordinates run from 0 to (height - 1) (so that there are exactly 'height' coordinates).

Let's make a specific example with five columns and four rows: So width is 5 and height is 4.
Let's give each cell (x, y) an index number: index_number(x, y) = y * width   x, as in the following picture



   X    0     1     2     3     4
Y      ----------------------
0     | 0     1     2     3     4
1     | 5     6     7     8     9
2     |10   11    12    13    14
3     |15    16    17    18    19


As you can see, if an index number a is smaller than an index number b, then either the cell corresponding to a has a lower row than the cell corresponding to b, or both cells are on the same row and the cell corresponding to a has a lower column than the cell corresponding to b.

For instance 1 < 10; the cell (x == 1, y == 0) corresponds to 1 and the cell (x == 0, y == 2) corresponds to 10.
(x == 1, y == 0)  has a lower row than (x == 0, y == 2)

For instance 1 < 2; the cell (x == 1, y == 0) corresponds to 1 and the cell (x == 0, y == 2) corresponds to 2.
(x == 1, y == 0) is on the same row as (x == 2, y == 0) and (x == 1, y == 0) has a lower column than (x == 2, y == 0).

We want to order a list of cells in such a way that the cells with lower rows or (equal rows and lower colums) come before the higher rows or (equal rows and higher columns).
So if we have two cells (x1, y1) and (x2, y2) where (x1, y1) is earlier in the list than (x2, y2) but the index number of (x1, y1) is higher than the index number of (x2, y2), then the cells are out of order.

Here's a simplified high-level overview of Khris' algo:

Line 7: The variable i shall run through all the positions of the list...
Line 8: The variable j shall run through all the positions of the list that come later than i ...
Line 9: if the cells in position i and j are out of order ...
Line 10 to 18: ... then swap their contents.

HTH

[Baguettator]

Hey there !

I come back to that thread, and I have to thank you a lot ! I  took me time to answer, sorry

I have another question about sorting an array : how could it be possible to sort an array of strings with alphabetical order ? I don't know how AGS could handle that...

[Crimson Wizard]

I have another question about sorting an array : how could it be possible to sort an array of strings with alphabetical order ?

String.Compare returns an integer which tells alphabetical relation between two strings: 0 if they are equal, negative if the first string is "earlier" and positive if the first string is "later".

Knowing this, you could use same algorithm as with integer array, only compare values using String.Compare.

------

Since AGS 3.5.0 there's an alternate solution: create a Set object of sorted type and ask it to return a sorted array of strings:

Code: ags

Set* set = Set.Create(eSorted, eCaseSensitive);
set.Add("string1");
set.Add("string2");
....
String items[] = mySet.GetItemsAsArray(); // this array will be sorted

[Baguettator]

OK Thanks Crimson !

I tried to make it working for strings, but it's a fail...

That's the code I tried :

Code: ags

void _swapalpha(String arr[], int p1, int p2){
  String temp = arr[p1];
  arr[p1] = arr[p2];
  arr[p2] = temp;  
}

int _partitionalpha(String arr[], int lo, int hi) {
  String pivot = arr[hi];
  int i = lo;
  int j;
  for (j = lo; j<hi; j++) {
    if(arr[j].CompareTo(pivot) < 0) {
      _swapalpha(arr, i, j);
      i = i + 1;
    }
  }
  _swapalpha(arr, i, j);  // *****
  return i;
}

void _quicksortalpha(String arr[], int lo, int hi){
  if( lo < hi) {
    int p = _partitionalpha(arr, lo, hi);  // *****
    _quicksortalpha(arr, lo, p-1);
    _quicksortalpha(arr, p+1, hi);  // *****
  }  
}

void qsortalpha(String arr[], int size) {
  _quicksortalpha(arr, 0, size-1);
}

When I use it, the game crashes and indicates the lines where I put some *****

Any idea ? I have to admit that I didn't really understand the algorythm...

[Crimson Wizard]

When I use it, the game crashes and indicates the lines where I put some *****

Does it stop during compilation or when running the game? Please tell the error message it sais...

I also posted the alternate solution using Sets, which should be much easier to code.

[Baguettator]

Oh ! I didn't see about the "Set" !!

Yes, the game crashes during the game, the compilation worked well. But no need to explore that problem : the "Set" solution is by far the best !

If I understand well, the "set" is automatically sorted ? Or do I need to copy it in a String [] ?

That's my code I'm going to try :

Code: ags

void Tri(this ListBox*)
{
  int t=this.ItemCount;
  Set* s=Set.Create(eSorted, eCaseSensitive);
  for (int i=0 ; i<t ; i++)
  {
    if (this==ListeEquipementsColo || this==ListeEquipementsExp)
    {
      int p=this.Items[i].IndexOf(" ");
      s.Add(this.Items[i].Substring(p+1, this.Items[i].Length));
    }
    else s.Add(this.Items[i]);
  }
  String c[]=s.GetItemsAsArray();
  this.Clear();
  for (int i=0 ; i<t ; i++)
  {
    this.AddItem(c[i]);
  }
}

EDIT : this code worked perfectly, and I think I have understood very well how to manipulate Sets. Thanks a lot !