Results 1 to 4 of 4

Thread: Javascript Array Sort method is "random" (NOT STABLE) within sort

Hybrid View

  1. #1

    Thread Starter
    MS SQL Powerposter szlamany's Avatar
    Join Date
    Mar 2004
    Location
    Connecticut
    Posts
    18,263

    Javascript Array Sort method is "random" (NOT STABLE) within sort

    The Javascript array sort method (at least in Firefox) is apparently random within the sort.

    If I have an ARRAY of OBJECTS and I sort on a particular element in the object - one that has lots of duplicates - the original order is not maintained in the final sort.

    It appears random - but after a couple of clicks to sort asc and desc it does come around - so there is a pattern.

    Has anyone ever dealt with this - and come up with a real solution.

    I'm thinking of doing some kind of "sub-sort" on the original ordinal position prior to sort - but don't want to re-invent the wheel so that say...

    Code:
    function sortArray(arrSort, e, args) {
        switch (e.cssClass || "") {
            case "acs-cell-money":
                arrSort.sort(sortNumber);
                break;
            case "acs-cell-number":
                arrSort.sort(sortNumber);
                break;
            case "acs-cell-date":
                arrSort.sort(sortDate);
                break;
            default:
                arrSort.sort(comparer);
                break;
        }
        if (!args.sortAsc) {
            arrSort.reverse();
        }
        for (var i = 0; i < arrSort.length; i++) {
            //alert(i);
            arrSort[i].acsSortBits = undefined;
        }
        arrSort.lastMultiSort = "";
    }
    
    function comparer(a, b) {
        var x = (a[sortcol.field] || "").toUpperCase();
        var y = (b[sortcol.field] || "").toUpperCase();
        return (x == y ? 0 : (x > y ? 1 : -1));
    }
    Last edited by szlamany; Jan 27th, 2012 at 10:40 AM.

    *** Read the sticky in the DB forum about how to get your question answered quickly!! ***

    Please remember to rate posts! Rate any post you find helpful - even in old threads! Use the link to the left - "Rate this Post".

    Some Informative Links:
    [ SQL Rules to Live By ] [ Reserved SQL keywords ] [ When to use INDEX HINTS! ] [ Passing Multi-item Parameters to STORED PROCEDURES ]
    [ Solution to non-domain Windows Authentication ] [ Crazy things we do to shrink log files ] [ SQL 2005 Features ] [ Loading Pictures from DB ]

    MS MVP 2006, 2007, 2008

  2. #2

    Thread Starter
    MS SQL Powerposter szlamany's Avatar
    Join Date
    Mar 2004
    Location
    Connecticut
    Posts
    18,263

    Re: Javascript Array Sort method is "random" (NOT STABLE) within sort

    Well - I went out on a limb here and tried this - seems to work - but I'm really not sure if I'm doing this correctly...

    I added an object pair to each object in the array - only the FIRST time the array is sorted.

    .acsStable will get a number from 0 to the length of the array.

    Code:
    function sortArray(arrSort, e, args) {
        if (arrSort.length > 0) {
            if (typeof arrSort[0].acsStable == "undefined") {
                for (var i = 0; i < arrSort.length; i++) {
                    arrSort[i].acsStable = i;
                }
            }
        }
        switch (e.cssClass || "") {
            case "acs-cell-money":
                arrSort.sort(sortNumber);
                break;
            case "acs-cell-number":
                arrSort.sort(sortNumber);
                break;
            case "acs-cell-date":
                arrSort.sort(sortDate);
                break;
            default:
                arrSort.sort(comparer);
                break;
        }
        if (!args.sortAsc) {
            arrSort.reverse();
        }
        for (var i = 0; i < arrSort.length; i++) {
            //alert(i);
            arrSort[i].acsSortBits = undefined;
        }
        arrSort.lastMultiSort = "";
    }
    Then I use the .acsStable as a tie-breaker in the comparer() function

    Code:
    function comparer(a, b) {
        var x = (a[sortcol.field] || "").toUpperCase();
        var y = (b[sortcol.field] || "").toUpperCase();
        //return (x == y ? 0 : (x > y ? 1 : -1));
        return (x == y ? (a.acsStable > b.acsStable ? 1 : -1) : (x > y ? 1 : -1));
    }
    This seems to work. But this is sorting an ARRAY that is in a jQuery slickgrid - and I'm not so comfortable that "storing" the original sequence works when clicking different columns - looks ok - but I'm just not fully comfortable with this.

    Has anyone ever run into this issue???

    I need an R&D meeting with a big whiteboard a half-a-dozen other coders to flesh this out properly...

    Why can't JS SORT be STABLE!!!

    *** Read the sticky in the DB forum about how to get your question answered quickly!! ***

    Please remember to rate posts! Rate any post you find helpful - even in old threads! Use the link to the left - "Rate this Post".

    Some Informative Links:
    [ SQL Rules to Live By ] [ Reserved SQL keywords ] [ When to use INDEX HINTS! ] [ Passing Multi-item Parameters to STORED PROCEDURES ]
    [ Solution to non-domain Windows Authentication ] [ Crazy things we do to shrink log files ] [ SQL 2005 Features ] [ Loading Pictures from DB ]

    MS MVP 2006, 2007, 2008

  3. #3
    Frenzied Member
    Join Date
    Apr 2009
    Location
    CA, USA
    Posts
    1,516

    Re: Javascript Array Sort method is "random" (NOT STABLE) within sort

    I don't think I really understand the problem you're trying to solve. Can you elaborate on what you're trying to sort, how you were trying to do it (using vanilla sort()), what you got as a result and why it wasn't what you expected?

  4. #4

    Thread Starter
    MS SQL Powerposter szlamany's Avatar
    Join Date
    Mar 2004
    Location
    Connecticut
    Posts
    18,263

    Re: Javascript Array Sort method is "random" (NOT STABLE) within sort

    With FF 9.0 - I am doing a SORT on an ARRAY of objects.

    Specifying one of the FIELDS in the OBJECT list as the SORT column (this is a data feed to a SlickGrid).

    Click the column of the slickgrid and it runs the sort. Click again and it sorts descending - by doing a .Reverse()

    Sort again and it runs ascending - but now when you look at the results any place where there was DUPLICATE data in the sort column - and you look at anothner column (one that has the person's names, for example) it reversed the order of names.

    Click again twice and the names are back to A-Z within the dups.

    I consider that a NOT STABLE sort - EXCEL does not do that, for example.

    And the web is alive with posts about non-STABLE JS sorts - as the spec for JS does not "require" stable sort - QUICKSORT is not stable - fix I read was to do a MERGESORT - yuk...

    So I slept on it last night and decided I would put my own "tie-breaker" column in the objects within the array - so that when the COMPARER function hits a DUPLICATE pair it uses that "sequential" number to break the tie.

    It doesn't get exactly the STABILITY that EXCEL shows - but at least it's consistent (EXCEL keeps a NAME column always "ASC" regardless of sorting DESC on a subsequent column).

    Look at the image - EXCEL first at top - original unsorted list - then sort on COLUMN A (retains order of column B within A) then sort on COLUMN A DESC (retains ASC ORDER of column B within A) - then sort again on COLUMN A ASC (still retains ASC ORDER of column B within A).

    Bottom is the BROKEN SORT prior to my fix - sort on the CAT column (asc first) - keeps EMPLOYEE name A-Z. Click CAT again - DESC sort - employees are reversed (as expected - I am calling .Reverse()). Click again - ASC CAT column - now names are Z-A! Click again - DESC CAT - but names are A - Z. Click again ASC CAT - now names are back to A - Z. That's really odd - since each click has exactly the same "presentation array".

    You would have expected one result - then another - then back to the first result - but it's not happening that way - it's being NOT STABLE.

    Customer expects SORT to be stable and not RANDOM.

    My fix of adding a SEQUENTIAL # field to the objects in the array - and using that as the tie-breaker for dups - is at least making it so that each time the CAT column is sorted ASC the EMPLOYEE NAME column appears the same.
    Attached Images Attached Images  

    *** Read the sticky in the DB forum about how to get your question answered quickly!! ***

    Please remember to rate posts! Rate any post you find helpful - even in old threads! Use the link to the left - "Rate this Post".

    Some Informative Links:
    [ SQL Rules to Live By ] [ Reserved SQL keywords ] [ When to use INDEX HINTS! ] [ Passing Multi-item Parameters to STORED PROCEDURES ]
    [ Solution to non-domain Windows Authentication ] [ Crazy things we do to shrink log files ] [ SQL 2005 Features ] [ Loading Pictures from DB ]

    MS MVP 2006, 2007, 2008

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width