Monday, September 20, 2010

Implementing Quicksort to sort a list of SelectOptions

A common task when building Visualforce pages is displaying a dropdown list that is populated by a list of SelectOptions, and making sure the values in the dropdown are ordered alphabetically. The most efficient ways to sort in Force.com are to either ask the SoQL database to do it for you by using ORDER BY, or by using the List object's .sort() function. Unfortunately .sort() only supports primitive datatypes, which SelectOption is not. And if the list didn’t come from a simple SoQL query that you can tweak the ORDER BY statement on, or if you just want to save a query, then it's time to bite the bullet and sort the list yourself.

Sorting a list is one of the most fundamental problems in computer science, and there are many ways to do it. We chose to use one of the most popular algorithms, Quicksort, because it doesn’t require a lot of memory, has high performance, and is easy to implement. To us, that means our sorting won't use up too many script statements and we wont' need to spend 4 days writing and testing the sorting code.

Below is the implementation of Quicksort that we use to sort out SelectOption lists. Note that this implementation does not do a true in-place sort, so the memory usage is a bit higher than it could be, but it has served our purposes very well.

You should be able to simply drop this in a class and use it as is!

    //  This is a simple quicksort algorithm to sort a SelectOption list (dropdown) 
    // by label alphabetically.
    global static List<SelectOption> SortOptionList(List<SelectOption> ListToSort)
    {
        if(ListToSort == null || ListToSort.size() <= 1)
            return ListToSort;
            
        List<SelectOption> Less = new List<SelectOption>();
        List<SelectOption> Greater = new List<SelectOption>();
        integer pivot = ListToSort.size() / 2;
          
        // save the pivot and remove it from the list
        SelectOption pivotValue = ListToSort[pivot];
        ListToSort.remove(pivot);
        
        for(SelectOption x : ListToSort)
        {
            if(x.getLabel() <= pivotValue.getLabel())
                Less.add(x);
            else if(x.getLabel() > pivotValue.getLabel()) Greater.add(x);   
        }
        List<SelectOption> returnList = new List<SelectOption> ();
        returnList.addAll(SortOptionList(Less));
        returnList.add(pivotValue);
        returnList.addAll(SortOptionList(Greater));
        return returnList; 
    }  

No comments:

Post a Comment