Skip navigation
Currently Being Moderated

Is Array.sort unstable?

Jul 16, 2013 11:05 PM

use Array.sort, when the compareFunction always retrun 0, it will change the array elements order.(in javascript it's not)

 

is the Array.sort use quick sort which is unstable?

 

and how to solve this not change the elements order.

 

Thank you for any help.

 

following is the testing code:

 

Student.as

package
{
          public class Student
          {
                    public function Student(name:String, age:int)
                    {
                              this.name = name;
                              this.age = age;
                    }
  
                    public var age:int;
  
                    public var name:String;
  
                    public function toString():String
                    {
                              return "[name=" + name + " age=" + age + "]";
                    }
          }
}
 

 

Applicatoin.mxml

 

<?xml version="1.0" encoding="utf-8"?>
<mx:Application xmlns:mx="http://www.adobe.com/2006/mxml"
                                        creationComplete="application1_creationCompleteHandler(event)">
          <mx:Script>
                    <![CDATA[
                              import mx.events.FlexEvent;
  
                              private var ac:Array = [
                                        new Student(ST1, 21),
                                        new Student(ST2, 21),
                                        new Student(ST3, 21),
                                        new Student(ST4, 21)
                              ];
  
                              protected function application1_creationCompleteHandler(event:FlexEvent):void
                              {
                                        ac.sort(function(a:Object, b:Object):int
                                        {
                                                  if (a.age > b.age)
                                                            return 1;
                                                  else if (a.age < b.age)
                                                            return -1;
                                                  return 0;
                                        });
                                        trace(ac);
                              }
  
                    ]]>
          </mx:Script>
  
</mx:Application>

 

then the result is :

 

[name=ST3 age=21],[name=ST2 age=21],[name=ST1 age=21],[name=ST4 age=21]

 

Array.sort has change the array elements order

 
Replies
  • Currently Being Moderated
    Jul 17, 2013 4:59 AM   in reply to huangxinghui

    Hi,

    You are sorting base on "age" only not touching the "name".

    The name field can come in any way.

    Example of how to do sort array with multiple fields.

    http://www.brucephillips.name/blog/index.cfm/2006/11/23/Sort-An-ArrayC ollection-By-Multiple-Fields-and-Filter-An-ArrayCollection-By-Multiple -Fields-In-Flex

    Best,

     
    |
    Mark as:
  • Currently Being Moderated
    Jul 17, 2013 5:14 AM   in reply to jfb00

    I think the point was that it's unexpected to see that the order has changed, even though there was no need to swap any entries.

     

     

    I was surprised by the result, but in other circumstances (as pointed out) you would normally write a sort function that sorted on the basis of multiple fields, or as in this case accept that the sort order of unsorted fields, is unpredictable.

     
    |
    Mark as:
  • Currently Being Moderated
    Jul 17, 2013 6:17 AM   in reply to huangxinghui

    I've seen the code - no need to repeat it.

     

    I don't know why the order has changed, but it doesn't actually matter - the sort is as you specified. If you wanted to sort the items on two fields you could. By sorting on only one field, you essentially say that the order of the unsorted field doesn't matter.

     

    I didn't expect the order of the array to change, but it's still consistent with the sort function.

     
    |
    Mark as:
  • Currently Being Moderated
    Jul 17, 2013 6:32 AM   in reply to huangxinghui

    It doesn't matter that it's differrent in javascript and if you don't wish to sort on multiple fields, then you have to live with the re-ordering.

     

    I understand what you are saying, I also did not expect the order to change, but it  did and it's still consistent with your ordering function.

     

    What we are seeing is not evidence of an unstable sort routine, just a very odd one.

     
    |
    Mark as:
  • Currently Being Moderated
    Jul 17, 2013 6:37 AM   in reply to huangxinghui

    You don't need to explain it, you need to amend the routine to sort on both fields, not just one.

     

    ac.sort(function(a:Object, b:Object):int
                    {
                        if (a.age > b.age){
                                  return 1;
                        } else if (a.age < b.age){
                                 return -1;

                                                }

                                                // ages are equal, now sort the names

     

                        if (a.name > b.name){
                                  return 1;
                        } else if (a.name < b.name){
                                 return -1;

                                                }

                                      

                        return 0;
                     });

     

    Something like that.

     
    |
    Mark as:
  • Currently Being Moderated
    Jul 17, 2013 7:00 AM   in reply to huangxinghui

    huangxinghui wrote:

     

    this just sort the array by multiple field. first sort age then sort name.

     

     

    That's what you need to do.

     

     

    maybe we can prevent the datagrid default sort behavior, and then sort by ourself

     

    Maybe you can write the sort function correctly.

     
    |
    Mark as:
  • Currently Being Moderated
    Jul 17, 2013 9:48 AM   in reply to huangxinghui

    See http://stackoverflow.com/questions/3026281/array-sort-sorting-stabilit y-in-different-browsers

     

    Array.sort is not required to be stable according to ECMA.  Looks like recent browsers have implemented stable sorting, but Flash has not.

     

    AS3Commons claims to have a stable sort.  See http://code.google.com/p/as3-commons/source/browse/trunk/as3-commons-c ollections/src/main/actionscript/org/as3commons/collections/utils/Arra yUtils.as

     
    |
    Mark as:
  • Currently Being Moderated
    Jul 17, 2013 8:12 PM   in reply to huangxinghui

    Yes, if you need stable sort you will have to implement a custom sort.  Remember that it will be faster to work with the raw Array  and then set the source of the ArrayCollection instead of manipulating the wrapping ArrayCollection or ArrayList

     
    |
    Mark as:

More Like This

  • Retrieving data ...

Bookmarked By (0)

Answers + Points = Status

  • 10 points awarded for Correct Answers
  • 5 points awarded for Helpful Answers
  • 10,000+ points
  • 1,001-10,000 points
  • 501-1,000 points
  • 5-500 points