15 Replies Latest reply: Jul 18, 2013 5:50 AM by huangxinghui RSS

    Is Array.sort unstable?

    huangxinghui

      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

        • 1. Re: Is Array.sort unstable?
          jfb00 Community Member

          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-ArrayCollection-By-Multipl e-Fields-and-Filter-An-ArrayCollection-By-Multiple-Fields-In-Flex

          Best,

          • 2. Re: Is Array.sort unstable?
            pauland Community Member

            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.

            • 3. Re: Is Array.sort unstable?
              huangxinghui Community Member

              @pauland, yes, in other language, Array.sort will not change the order when they are equal.

               

              so, in flex, you set mx:DataGrid dataProvider=ac and create two columns, one is name, the othe is age. then click the age column, it will change the content order and it always happened in the first time click.(the user cannot accept this, they said the age column value are equal, why you change the elements order?)

               

              this is the example code:

              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
                                            {
                                                      datagrid.dataProvider = ac;
                                            }
              
              
              
              <mx:DataGrid id="datagrid" width="400" height="300">
                                  <mx:columns>
                                            <mx:DataGridColumn dataField="name"/>
                                            <mx:DataGridColumn dataField="age"/>
                                  </mx:columns>
                        </mx:DataGrid>
              
              
              • 4. Re: Is Array.sort unstable?
                pauland Community Member

                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.

                • 5. Re: Is Array.sort unstable?
                  huangxinghui Community Member

                  Thank you for your reply, @jb00. i do not want to sort a array with multiple fields.

                   

                  I don't know why Array.sort change the elements order, when two elements are equals.

                   

                  the array [new Student(ST1, 21), new Student(ST2, 21), new Student(ST3, 21), new Student(ST4, 21)]

                   

                  when order by age field, it should be no change, because the four elments age field value all are 21.

                   

                  but the result is ST1 has swap to ST3。

                   

                  In JavaScript, it's not.

                  • 6. Re: Is Array.sort unstable?
                    pauland Community Member

                    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.

                    • 7. Re: Is Array.sort unstable?
                      huangxinghui Community Member

                      yes, you are right. it doesn't actually matter

                       

                      but it was not a good user experience when first time click the age column, the order has changed.

                       

                      and how to expalin it?

                      • 8. Re: Is Array.sort unstable?
                        pauland Community Member

                        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.

                        • 9. Re: Is Array.sort unstable?
                          huangxinghui Community Member

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

                           

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

                          • 10. Re: Is Array.sort unstable?
                            pauland Community Member

                            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.

                            • 11. Re: Is Array.sort unstable?
                              huangxinghui Community Member

                              click the datagrid column header, the grid component will sort by itself.

                               

                              when click the age column header the grid will do this steps:

                               

                              1, create sortfield var f:SortField = new SortField("age");

                               

                              2, check datasource have sort or not, if not create one

                               

                              var s:Sort = new Sort();

                               

                              3, set sortfield to the sort

                               

                              s.fields = [f];

                               

                              4,set sort to the datasource

                               

                              ac.sort = s;

                               

                              then datasource call refresh (collection.refresh();)

                               

                              so we can't write sort function.

                              • 12. Re: Is Array.sort unstable?
                                Flex harUI Adobe Employee

                                See http://stackoverflow.com/questions/3026281/array-sort-sorting-stability-in-different-brows ers

                                 

                                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-collections/src/main/ actionscript/org/as3commons/collections/utils/ArrayUtils.as

                                • 13. Re: Is Array.sort unstable?
                                  huangxinghui Community Member

                                  Thanks, alex

                                   

                                  The DataGrid sort use Array.sort, maybe i should sort by myself by using mergesort.

                                  • 14. Re: Is Array.sort unstable?
                                    Flex harUI Adobe Employee

                                    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

                                    • 15. Re: Is Array.sort unstable?
                                      huangxinghui Community Member

                                      OK, thank you for reminding. Good help for me.