Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

sorting arrays

Discussion in 'Scripting' started by beansly jones, May 15, 2012.

  1. beansly jones

    beansly jones

    Joined:
    Apr 7, 2012
    Posts:
    7
    Thanks in advance for the help,

    When I pull the help file for the Sort command for unityScript it only shows a basic use. Can someone post a detailed use of Sort?

    I would like to sort a Gameobject array without splitting the name and vector3 into two arrays which seems like a bigger can of worms. I have read about dictionary

    My goal is to create an array of the nearest 4 GameObjects by sorting the array by the vector3 like..,

    go.Sort(vector3)

    This seems do able but I dont know the correct operation.

    Thanks,

    Beansly Jones
     
  2. Tseng

    Tseng

    Joined:
    Nov 29, 2010
    Posts:
    1,217
    What you are looking is an implementation if IComparar.

    http://support.microsoft.com/kb/320727

    That's one way doing it, by creating IComparar helper classes and pass them to sort.

    The other way is to use Linq or Lambda expressions

    Lambda
    Code (csharp):
    1.  
    2.     GameObject[] array = ...;
    3.  
    4.     array.Sort( (a, b) => {
    5.         // Do compare code here. a and b are two objects being compared to
    6.         // the result must be
    7.         // 1, if a > b
    8.         // 0, if a == b
    9.         // -1, if a < b
    10.         Vector3 distanceA = ((GameObject)a).transform.position - transform.position;
    11.         Vector3 distanceB = ((GameObject)b).transform.position - transform.position;
    12.  
    13.         if(distanceA.sqrMagnitude > distanceB.sqrMagnitude) {
    14.             return 1;
    15.         } else if(distanceA.sqrMagnitude < distanceB.sqrMagnitude) {
    16.             return -1;
    17.         }
    18.  
    19.         return 0;
    20.     } );
    21.  
    Linq
    Code (csharp):
    1.  
    2. using System.Linq;
    3. ...
    4.  
    5.     array.OrderBy( x => x.name); // sorts by name.
    6.  
    though, I think Linq only works with objects which implement IComparable interface and I think Vector3 doesn't do it.
     
  3. Eiznek

    Eiznek

    Joined:
    Jun 9, 2011
    Posts:
    374
    Here's an actual sorting algorithm. I believe its just selection sort. So if you have less then 1000 elements it should be pretty fast.

    (Example from my project)
    Code (csharp):
    1.  
    2. public void SortArmorList()
    3.     {
    4.         GameObject holder;
    5.        
    6.         for(int i = 1; i < armorItems.Count; i++)
    7.         {
    8.             int j = i;
    9.             while(j > 1)
    10.             {
    11.                 if(GetItem(armorItems[j-1]).itemScore < GetItem(armorItems[j]).itemScore)
    12.                 {
    13.                     holder = armorItems[j-1];
    14.                     armorItems[j-1] = armorItems[j];
    15.                     armorItems[j] = holder;
    16.                     j--;
    17.                 }
    18.                 else
    19.                     break;
    20.             }
    21.         }
    22.  
    You can use the distance calculation up above and then sort them in the area based on that. Then all you would need to do is return the top four positions.
     
  4. beansly jones

    beansly jones

    Joined:
    Apr 7, 2012
    Posts:
    7
    Very cool. Thanks, this is just what I was looking for.

    Beansly Jones
     
  5. beansly jones

    beansly jones

    Joined:
    Apr 7, 2012
    Posts:
    7
    Code (csharp):
    1.  
    2.     GameObject[] array = ...;
    3.  
    4.     array.Sort( (a, b) => {
    5.         // Do compare code here. a and b are two objects being compared to
    6.         // the result must be
    7.         // 1, if a > b
    8.         // 0, if a == b
    9.         // -1, if a < b
    10.         Vector3 distanceA = ((GameObject)a).transform.position - transform.position;
    11.         Vector3 distanceB = ((GameObject)b).transform.position - transform.position;
    12.  
    13.         if(distanceA.sqrMagnitude > distanceB.sqrMagnitude) {
    14.             return 1;
    15.         } else if(distanceA.sqrMagnitude < distanceB.sqrMagnitude) {
    16.             return -1;
    17.         }
    18.  
    19.         return 0;
    20.     } );
    21.  
    This is UnityScript right? I copied it in and am getting errors.
    Do I need to send an array with only 2 variables to be sorted? Currently I am sending a GameObject which has many.

    This part of the code I do not understand...
    ((GameObject)a).
    does there need to be a variable named "a" inside the Array passed to it?
     
  6. diablo

    diablo

    Joined:
    Jan 3, 2011
    Posts:
    736
    This is C#, not UnityScript.
     
  7. beansly jones

    beansly jones

    Joined:
    Apr 7, 2012
    Posts:
    7
    Aha!

    So how would one accomplish this in unityScript? use a javescript array?
     
  8. Tseng

    Tseng

    Joined:
    Nov 29, 2010
    Posts:
    1,217
    a and b defined are in this line :
    Code (csharp):
    1.  
    2.     array.Sort( (a, b) => {
    3.  
    (a, b) => { .. } is actual lambda for anonymous methods/delegates.

    it's same as

    Code (csharp):
    1.  
    2.     array.Sort( delegate(object a, object b) { ... } );
    3.  
    This anonymous function is called every time, when the Sort method compares to objects. In UnityScript you can write delegates as (as far as i know):

    Code (csharp):
    1.  
    2.     array.Sort( function(a, b) {
    3.         // compare code here
    4.     } );
    5.  
    But do not use UnityScript Arrays (var blah : Array = new Array()), they are slow. Use .NET built-in arrays (the one with [])

    Normally, the IComparer.Compare interface defines takes two "objects"
    Code (csharp):
    1.  
    2.     int IComparer.Compare(object a, object b)
    3.  
    so you must cast them up to GameObject. Dunno anymore if this is necessary when using lambda.

    It's the same as

    GameObject gameObjectA = (GameObject)a;

    or

    GameObject gameObjectA = a as GameObject;
     
  9. tonyd

    tonyd

    Joined:
    Jun 2, 2009
    Posts:
    1,224
    This should work in UnityScript:

    Code (csharp):
    1. import System.Collections.Generic;
    2.  
    3. class DistanceSort implements IComparer.<GameObject>{
    4.     var transformPos : Vector3;
    5.     function DistanceSort(pos : Vector3){
    6.         transformPos = pos;
    7.     }
    8.     function Compare(go1 : GameObject, go2 : GameObject){
    9.         if (go1==null  go2==null) return 0;
    10.         if (go1==null) return -1;
    11.         if (go2==null) return 1;
    12.         var distance1 = Vector3.Distance(go1.transform.position, transformPos);
    13.         var distance2 = Vector3.Distance(go2.transform.position, transformPos);
    14.         if (distance1 < distance2) return -1;
    15.         if (distance1 > distance2) return 1;
    16.         return 0;  
    17.     }  
    18. }
    19.  
    20. function Start(){
    21.     var allObjects = GameObject.FindObjectsOfType(GameObject); 
    22.     System.Array.Sort(allObjects, new DistanceSort(transform.position));
    23.     for (obj in allObjects)
    24.         Debug.Log(String.Format("Name:{0}           Position:{1}", obj.name, obj.transform.position));    
    25. }
    Note that I had to pass transform.position as an argument, the IComparer class couldn't access it otherwise. Not sure if this is expected behavior or a bug in the UnityScript implementation.
     
  10. beansly jones

    beansly jones

    Joined:
    Apr 7, 2012
    Posts:
    7
    Tony thank you for converting this to unityScript. And thanks to everyon else posting also. I am trying to get to know sorting arrays intimently since they seem so integeral to scripting.

    Where I was/am getting lost was with "implements IComparer" I have searched the manual and there are no refrences internal to unity. So I was thinking they were for another launguage. Are these functions being enabled via the import.collections.generic;?
     
  11. tonyd

    tonyd

    Joined:
    Jun 2, 2009
    Posts:
    1,224
    I wouldn't say it is integral to scripting (I don't think I used Sort at all in my last 2 games), but it's quite useful when scripting certain things (such as inventories and databases).

    Honestly, I'm not sure why it uses implements rather than extends. And import simply imports the namespace, otherwise you would have to type System.Collections.Generic.IComparer rather than IComparer each time you used it.
     
    Last edited: May 17, 2012
  12. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
    It says implements because IComparer is an interface, not a class. Classes get extended, interfaces get implemented. In C# the colon is both implement and extend so it doesn't matter as much.
     
  13. tonyd

    tonyd

    Joined:
    Jun 2, 2009
    Posts:
    1,224
  14. KelsoMRK

    KelsoMRK

    Joined:
    Jul 18, 2010
    Posts:
    5,539
    Wow, that certainly was an "interesting" design decision. :)
     
  15. SwagGamez

    SwagGamez

    Joined:
    May 6, 2015
    Posts:
    5
    Ok I am completely lost. Can anyone help me please? I have just made the switch from GameSalad to Unity. I am almost finished my first game but I am stuck. Im not sure how this sorting works. I would like to create an onscreen list of 8 cars (Car 1, Car 2, etc). Each car has a script attached to it called Script 1, Script 2, etc. I would like to sort the list of names by variables (Variable 1, Variable 2, etc) from highest to lowest (ascending) during the game.

    Im looking at all these codes and what you guys are suggesting but its still looks Chinese lol

    PS. Car 1 has a script called Script 1 in it which contains a variable called Variable 1 in it.
    Car 2 has a script called Script 2 in it which contains a variable called Variable 2 in it.
    etc, etc

    Hope I provided enough info. Please & Thank You!
     
  16. Varaughe

    Varaughe

    Joined:
    Apr 22, 2013
    Posts:
    40
    It looks that Array.Sort from Unity, is not stable, probably the underlying algorithm is quicksort, despite in the C# documentation it states, that for small arrays, Insertion Sorting should be used, which is stable. Probably someone from Unity should explain more.
     
  17. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
    1) you revived a thread that hasn't been posted in for over 3 years

    2) Unity did not implement Array.Sort, nor does C#. It's up to the .net runtime used, and the one used by Unity comes from mono (well technically there's some gotchas to that even more in recent years), so it's really the mono implementation of Array.Sort you'd want to be looking into

    3) Usually mono tries to follow the defined functionality of .Net... and with that, the documentation does say that it uses insertion for small array (under 16), heapsort for special case arrays, and quick sort in all others. But not only does it say that, it also explicitly states that the sort is considered 'unstable':

    https://docs.microsoft.com/en-us/do...amework-4.7.2#System_Array_Sort_System_Array_
     
    Last edited: Dec 27, 2018
    SparrowGS likes this.
  18. Varaughe

    Varaughe

    Joined:
    Apr 22, 2013
    Posts:
    40
    Thanks for answer, but insertion sort algorithm is stable, while the sort in Unity is not stable,even if I've got an array with only 3 elements which are all equals, they are re-ordered, the "compare" delegate is called even to compare an element with itself. Something's very weird. Eventually I implemented the "insert sorting" myself to assure a stable sorting.
     
  19. lordofduct

    lordofduct

    Joined:
    Oct 3, 2011
    Posts:
    8,513
    While insertion sort may be considered stable.

    The documentation explicitly states that the Array.Sort method (not just quicksort) is to be considered unstable.

    So by definition, it's unstable.

    Which means that whatever implementation mono went with, it is allowed to be unstable, since the Microsoft definition of Array.Sort allows it to be unstable.

    Note, Unity uses mono. Not .Net. And mono doesn't need to use the same implementation as .Net (actually they technically aren't allowed to use the same exact implementation). All they have to do is successfully meet the definition of the API. Array.Sort defines itself as unstable, so whatever mono does for its implementation, it's allowed to be unstable.

    And at the end of the day... has nothing to do with Unity. Unity didn't create mono.

    Yes, it's called mono.

    If you need a stable sort, you'll need to implement it yourself. Since by definition Array.Sort is not stable.
     
    Last edited: Dec 28, 2018