Sorting QML ListModels

1. Introduction

This blog post discusses sorting the QML ListModel. It’s one of my favourite problems to solve. The blog also talks about a Sorting Cities sample app. That sample app implements and demonstrates the QML ListModel sort. The rest of the blog explains how the function works.

2. Sorting Cities sample app

The Sorting Cities sample app is an AppStudio 3.3 app. It comes with five U.S. cities. The user can sort them by city name or by distance to ESRI. The sort order can be either ascending or descending.

Item {
    ColumnLayout {
        anchors.fill: parent
        anchors.margins: 10 * AppFramework.displayScaleFactor

        spacing: 10 * AppFramework.displayScaleFactor

        ListView {
            id: listView
            Layout.fillWidth: true
            Layout.fillHeight: true
            model: ListModel {
                id: listModel
                Component.onCompleted: {
                    add( "Hawaii", 21.289373, -157.917480 )
                    add( "Los Angeles", 34.052235, -118.243683 )
                    add( "New York City", 40.730610, -73.935242 )
                    add( "Redlands", 34.0555700, -117.1825400 )
                    add( "Seattle", 47.608013, -122.335167 )
                }
                function add(city, lon, lat) {
                    const esri = QtPositioning.coordinate( 34.0572522, -117.1945814 )
                    const coord = QtPositioning.coordinate( lon, lat )
                    const distance = coord.distanceTo( esri )
                    append( { city, coord, distance } )
                }
            }

            delegate: ItemDelegate {
                text: `${city} ${(distance / 1000).toFixed(2)} km`
            }
        }

        Button {
            text: qsTr("  City  ")
            onClicked: listModelSort( listModel,
                                      (a, b) => a.city.localeCompare(b.city) )
        }

        Button {
            text: qsTr("  City (Desc)  ")
            onClicked: listModelSort( listModel,
                                      (a, b) => - a.city.localeCompare(b.city) )
        }

        Button {
            text: qsTr("  Distance to Esri  ")
            onClicked: listModelSort( listModel,
                                      (a, b) => (a.distance - b.distance) )
        }

        Button {
            text: qsTr("  Distance to Esri (Desc)  ")
            onClicked: listModelSort( listModel,
                                      (a, b) => - (a.distance - b.distance) )
        }
    }

    function listModelSort(listModel, compareFunction) {
        let indexes = [ ...Array(listModel.count).keys() ]
        indexes.sort( (a, b) => compareFunction( listModel.get(a), listModel.get(b) ) )
        let sorted = 0
        while ( sorted < indexes.length && sorted === indexes[sorted] ) sorted++
        if ( sorted === indexes.length ) return
        for ( let i = sorted; i < indexes.length; i++ ) {
            listModel.move( indexes[i], listModel.count - 1, 1 )
            listModel.insert( indexes[i], { } )
        }
        listModel.remove( sorted, indexes.length - sorted )
    }
}‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

View the full SortingCities.qml on Github Gist.

3. ListModel vs Array

If you compare the ListModel QML Type with the Javascript Array type, you’ll find that Array has better methods. In particular, Array has a sort method whilst ListModel does not.

When you assign an Array to a QML visual component, e.g. ListView, the Array behaves like a scalar value. If you were to push new records onto the Array the ListView will not update. There is no property binding between pushes to the Array and the ListView. To refresh the ListView you need to reassign the Array every time the Array changes. This will cause the ListView to repaint. This could lead to bad user experience. For instance, I may be writing an application that collates results from an online search. The results may arrive through a series of NetworkRequests to REST API end points. Each update will cause the ListView to repaint and scroll back to the top. This will be particularly annoying to the user if the user was already reading and scrolling through the results.

The experience is different with ListModels. When you assign a ListModel to a ListView you don’t need to assign it again. When you append new records to the ListModel, the ListView will receive sufficient change notification and will automatically update to reflect that new records have arrived. If the ListModel were to change whilst the user was reading and scrolling through the ListView, the current scrolled position and the selected item will be unchanged. The user would not experience any negative user experience with the ListView.

In short, for good user experience, we prefer ListModels over Arrays.

4. Compare Functions as Arrow Functions

Array sort (and QML ListModel sort) requires a compare function. A compare function takes any two elements from the Array (or ListModel) and returns an integer. It can be negative, zero or positive. For example, if one wanted to compare any two numbers, one could write the following compare function:

function compareNumbers( a, b ) {
    return a - b
}‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

If a was greater than b then the function would return a positive number.

If a was the same as b then the function would return zero.

If a was less than b then the function would return a negative number.

Then, you would use the compare function as follows:

function compareNumbers( a, b ) {
    return a - b
}‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

let numbers = [ 5, 2, 11, 3, 7 ]
numbers.sort( compareNumbers )
console.log( numbers ) // [ 2, 3, 5, 7, 11 ]‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

If your compare function is simple, you can inline it with your sort call, i.e.

let numbers = [ 5, 2, 11, 3, 7 ]
numbers.sort( function compareNumbers( a, b ) { return a - b } )
console.log( numbers ) // [ 2, 3, 5, 7, 11 ]‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

In AppStudio 3.3, Qt 5.12.1 you can use the ECMAScript 6 arrow function syntax, i.e.

let numbers = [ 5, 2, 11, 3, 7 ]
numbers.sort( (a,b) => a - b )
console.log( numbers ) // [ 2, 3, 5, 7, 11 ]‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

You’ll see the arrow function syntax allows us to omit the ‘function’ keyword, the function’s name and the ‘return’ keyword. We make this choice if we believe such a choice improves our code readability and maintainability.

In the Sorting Cities sample app, I used the arrow function syntax for all 4 buttons, e.g.

Button {
    text: qsTr("  City  ")
    onClicked: listModelSort( citiesListModel,
                              (a, b) => a.city.localeCompare(b.city) )
}‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍
‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

5. Implementing listModelSort

There are plentiful sorting algorithms out there. Whilst we can implement one in QML / Javascript, I don’t think this is a good idea. We would be implementing a sort algorithm that we would required to maintain. One of the best algorithms out there, Quicksort, is complex to transcribe correctly. Also such an implementation would be executing entirely in Javascript and will not be leveraging much from native code.

Instead, I wanted to leverage from Array sort’s implementation. In a nutshell, the algorithm would be:

1. Copy items from the QML ListModel to an Array

2. Perform an Array sort

3. Copy the resultant items from the sorted Array back to the QML ListModel

Turns out, we can optimized the above technique by not copying the items but linking to them via an index. i.e. The Array would be a set of integer indexes and we just be traversing it as a on the fly lookup into the QML ListModel.

Let’s begin by creating an indexes Array the exact same size as our ListModel with numbers ranging from 0 to N – 1:

let indexes = [ ...Array(listModel.count).keys() ]‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

Then, we use Array’s sort method to reorder the indexes Array. We use an arrow function to pick any two entries from the QML ListModel and feed them to the user supplied compare function:

indexes.sort( (a, b) => compareFunction( listModel.get(a), listModel.get(b) ) )‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

This reorders the indexes Array. We can now use this sorted Array to traverse the ListModel in sorted order.

Whilst we can stop here, I wanted to go further and use theses indexes to rearrange the QML ListModel.

for ( let i = 0; i < indexes.length; i++ ) {
    listModel.move( indexes[i], listModel.count - 1, 1 )
    listModel.insert( indexes[i], { } )
}
listModel.remove( 0, indexes.length )‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍‍

The above loop iterates through the items in the ListModel in sorted order. For each item, we move it to the end of the ListModel in sorted order. Once all the items have been moved, we delete the empty holes left behind by the move. It’s a heavy handed approach. In my final version I made an optimization that reduces the amount moving and deletion.

The animation above helps you visualize sorting the cities based on their distance to ESRI. We see it quickly identifies the sort order as Redlands, Los Angeles, Seattle, New York City and Hawaii. The records are tagged by an index 0…4. Next, the sorted records are moved, one by one, to the end, then the sorted records are moved back to the top deleting the temporary empty holes.

6. Closing Remarks

For good user interfaces I recommend storing your content in ListModels instead of Arrays. This is so that updates to the content will not interrupt the user experience.

Whenever you can, leverage from an existing implementation (e.g. Array sort) rather than implement your own. You minimize your coding effort and future maintenance efforts.

The ECMAScript 6 arrow function syntax can help you express simple sorting compare functions. Otherwise, if they’re complex, then, then you should use a named compare function.