Happyfaces archetype tutorial. Easy JSF with custom components!

If you want to create a new JSF project from scratch it would really take significant amount of time. All the configurations, problem solving and learning takes more time than we would like. Maven archetypes are great solution to this problem. Lets try my new project – happyfaces maven archetype.

To get started you will need: My Sql database, Maven, Tomcat and of course Java and some IDE (I use Eclipse). Archetype creates JSF 2.2/Spring/Tomcat/Mysql project for you. It already contains small sample application. The reason it is not removed is because of time constraint I do not provide very good documentation and it’s best to learn by doing and copying 🙂 After project is created take a look at readme.txt to see what files you need to remove if you don’t want an example.

Project creation

Maven is really cool. Archetype is already in maven central so you simply need to run this command:

  mvn archetype:generate -DarchetypeGroupId=com.github.happyfaces -DarchetypeArtifactId=happyfaces-archetype -DarchetypeVersion=1.0.2 -DgroupId=com.test -DartifactId=MyTestApp

Open eclipse, Import -> Maven -> Existing Maven Projects and select your newly created project. Open Servers view add your tomcat server and add project MyTestApp to tomcat. Open filter-dev.properties and enter your database name (need to create it in MySql of course) and db username/password.

And that’s almost it! We would be already starting up tomcat and enjoying our awesome project. However I decided to use QueryDSL with spring-data as another layer for database access and it needs to generate some code. For some reason it doesn’t work out of box in eclipse. If you know how to do it let me know! So lets go to the project’s root dir and run this maven command:

  mvn generate-sources

Now there should be bunch of source files in target/generated-sources/java. You should add it to build path (left click on this directory in eclipse -> Build path -> Use as source folder). And that’s it! You can start tomcat and go to http://localhost:8080/MyTestApp now. In case you get some errors on startup try to Project -> Clean.

P.S. If you see annoying You need to run build with JDK or have tools.jar on the classpath. error in pom, take a look here. I swear I wanted to kill somebody while trying to solve it and was really sorry I started with this querydsl thing 🙂

Sample application

Lets review what do we have now. After project start up you should see login screen like this.

login

You can login with user=admin password=admin. Application already has spring security configured. On top right corner you can change language and logout. There are few sample windows: Customers, Accounts, Operations where user can view list of those entities, delete them, view details, edit details, export list and of course search by various properties. Also it has REST webservices exposed. In the next chapter we will see how the code for all this looks.

account_edit

accounts_search

rest

Getting familiar with code base

It is easy if you are familiar with JSF. Lets take an Account window as an example and figure out how it is implemented. For all pages template.xhtml is used. It also provides countdown dialog before logging out user if session is running out. Template is like this: top header.xhtml, bottom – footer.xhtml, left – menu.xhtml and in the center is content where accounts.xhtml content will be put. Its pretty standard facelets templating and of course you can modify it according to your needs. If you open accounts.xhtml you will notice how little code there are(especially if you remove comments). Everything is implemented using custom JSF components. You will find custom components in webapp/resources/tags directory and taglibs in webapp/taglib directory.

Now on the Java side backing bean is implemented in AccountBean.java. It is surprisingly short for a backing bean which is doing so much. However it does extend BaseBean.java and that’s how custom JSF components are able to do their magic. In simplest CRUD cases you basically don’t need to do anything – simply extend BaseBean.java! AccountBean also has Spring service injected – AccountService.java. It also extends BaseService.java which provides all the required transactional methods for searching, loading, deleting etc. That’s why AccountService does not contains any code! And you can search lists, delete and edit entities without writing any code at all – simply use custom components and extend from base classes!

Spring-data repositories is used for data access and in case you need some custom query you don’t even need to write hql. Take a look at repository UserRepository.java for example. Other repositories are in the same package, but they don’t have any custom queries for this example.

Application configurations can be found under WEB-INF directory. Security uses spring security framework and is configured in applicationContext-security.xml. Login logic is done in UserService.java. REST webservices are configured in springREST-servlet.xml and example can be viewed at CustomerRestController.java. And of course standard configurations: applicationContext.xml for Spring, faces-config.xml for JSF and web.xml for servlets.

After reviewing code base its time to get our hands dirty. Lets try to implement a new CRUD window for a new entity – Issue.java.

Implementing new window

Lets say users of our sample application needs to solve some issues time to time. Of course the best way to do that is incorporate issue management into already existing application. Lets say simple issue has Title, Description, Status, Date and Account for which it is created.

Lets create simple CRUD for it. Starting with Issue.java and IssueStatus.java enum.


public enum IssueStatus {
    
    NEW(1, "IssueStatus.NEW"),
    WORKING(2, "IssueStatus.WORKING"),
    SOLVED(3, "IssueStatus.SOLVED");
    
    private Integer id;
    
    private String label;
    
    private IssueStatus(Integer id, String label) {
        this.id = id;
        this.label = label;
    }
    public Integer getId() {
        return id;
    }
    public String getLabel() {
        return label;
    }
}

@Entity
@Table(name = "ISSUE")
public class Issue extends BaseEntity {

    private static final long serialVersionUID = 1L;

    @Column(name = "TITLE", nullable = false)
    private String title;

    @Column(name = "DESCRIPTION", length = 5000)
    private String description;
    
    @ManyToOne(fetch = FetchType.LAZY)
    @JoinColumn(name = "ACCOUNT_ID")
    private Account account;
    
    @Temporal(TemporalType.TIMESTAMP)
    @Column(name = "ISSUE_DATE")
    private Date issueDate;
    
    @Enumerated(value = EnumType.STRING)
    @Column(name = "ISSUE_STATUS")
    private IssueStatus status;

    // getters setters skipped
}

Don’t forget to run mvn generate-sources after adding/editing entity and also don’t forget to add translatable messages to messages.properties:

IssueStatus.NEW=New issue
IssueStatus.WORKING=Working
IssueStatus.SOLVED=Solved

Now we need to create spring service and jsf backing bean for Issue entity:

// Add spring data repository. Required for service.
public interface IssueRepository extends GenericRepository<Issue, Long> {
}

public interface IIssueService extends IService<Issue> {
}

// simply extend BaseService
@Service("issueService")
public class IssueService extends BaseService<Issue> implements IIssueService {
    private static final long serialVersionUID = 1L;
    @Autowired
    private IssueRepository repository;
    
    @SuppressWarnings({ "unchecked", "rawtypes" })
    @Override
    protected JpaRepository<Issue, Long> getRepository() {
        return (JpaRepository) repository;
    }
}

@ManagedBean(name = "issueBean")
@ViewScoped
public class IssueBean extends BaseBean<Issue> {

    private static final long serialVersionUID = 1L;
    
    @ManagedProperty(value = "#{issueService}")
    private IIssueService issueService;

    public IssueBean() {
        super(Issue.class);
    }

    @Override
    protected IService<Issue> getPersistenceService() {
        return issueService;
    }
    public void setIssueService(IIssueService issueService) {
        this.issueService = issueService;
    }
    
    /**
     * Fetch account field so no LazyInitialize exception is thrown when
     * we access it from account list view.
     *
     * @see com.test.beans.base.BaseBean#getListFieldsToFetch()
     */
    @Override
    protected List<String> getListFieldsToFetch() {
        return Arrays.asList("account");
    }
    
    /**
     * Fetch customer field so no LazyInitialize exception is thrown when
     * we access it from account edit view.
     *
     * @see com.test.beans.base.BaseBean#getFormFieldsToFetch()
     */
    @Override
    protected List<String> getFormFieldsToFetch() {
        return Arrays.asList("account");
    }
}

As you can see we are barely writing any code – simply creating classes that extend something. One exception is overridden getFormFieldsToFetch() and getListFieldsToFetch() methods which does nothing more than select * from Issue i join fetch i.account. That way we don’t need to use eager fetch on domain object and simply fetch account on select. If we wouldn’t fetch an account and would like to show its name we would get LazyInitializeException. When overriding those methods we simply let BaseBean to take care of fetching (take a look at BaseBean.initEntity() method for example).

So from Java part that’s it. Pretty cool huh? 🙂 Now lets add xhtmls and enjoy our new window 🙂 We need to add issues.xhml for issue list, issueEdit.xhtml for edit and view and of course modify menu.xhtml and faces-config.xml.

Append this navigation case to faces-config.xml:


<navigation-case>
<from-outcome>issues</from-outcome>
<to-view-id>/pages/issues.xhtml</to-view-id>
</navigation-case>

Add this sub menu to menu.xhtml:


<p:submenu label="#{messages['menu.issues']}">
<p:menuitem value="#{messages['menu.issues']}" outcome="issues" />
</p:submenu>

Create new issues.xhtml in pages dir:


<ui:composition xmlns="http://www.w3.org/1999/xhtml" xmlns:h="http://xmlns.jcp.org/jsf/html" xmlns:f="http://xmlns.jcp.org/jsf/core"
    xmlns:p="http://primefaces.org/ui" xmlns:ui="http://xmlns.jcp.org/jsf/facelets" xmlns:hftl="http://hftl.org" xmlns:hf="http://xmlns.jcp.org/jsf/composite/tags"
    template="../templates/template.xhtml">

    <ui:param name="pageTitle" value="#{messages['issue.search']}" />

    <ui:define name="content">
        <hf:searchPanel id="searchPanel" columns="3" backingBean="#{issueBean}">
            <hf:searchField label="#{messages['issue.title']}" field="title" />
            <hf:searchField label="#{messages['issue.status']}" field="status" />
            <hf:searchField label="#{messages['issue.issueDate']}" field="issueDate" rangeSearch="true" />
            <hf:searchField id="accountField" label="#{messages['issue.account']}" field="account" childField="accountNumber" popup="true" />
        </hf:searchPanel>
        <hftl:dataList label="#{messages['issue.search.results']}" backingBean="#{issueBean}">
            <hftl:column label="#{messages['issue.title']}" field="title" />
            <hftl:column label="#{messages['issue.status']}" field="status" childField="label" isMessage="true" sort="false" />
            <hftl:column label="#{messages['issue.issueDate']}" field="issueDate" isDate="true" />
            <hftl:column label="#{messages['issue.account']}" field="account" childField="accountNumber" />
            <hftl:actionsColumn />
        </hftl:dataList>
        <hftl:entityPopup id="accountsPopup" header="#{messages['account.search']}" updateField=":searchPanel:searchForm:accountField:account_child" selection="#{issueBean.filters['account']}"
            backingBean="#{accountBean}" searchField1Label="#{messages['account.accountNumber']}" searchField1="accountNumber"
            column1Label="#{messages['account.accountNumber']}" column1="accountNumber" />
    </ui:define>
</ui:composition>

Create new issueEdit.xhtml in pages dir:


<ui:composition xmlns="http://www.w3.org/1999/xhtml" xmlns:h="http://xmlns.jcp.org/jsf/html" xmlns:f="http://xmlns.jcp.org/jsf/core"
    xmlns:p="http://primefaces.org/ui" xmlns:ui="http://xmlns.jcp.org/jsf/facelets" xmlns:hf="http://xmlns.jcp.org/jsf/composite/tags" xmlns:hftl="http://hftl.org"
    template="../templates/template.xhtml">
    
    <ui:define name="metadata">
        <f:metadata>
            <f:viewParam name="edit" rendered="#{sessionPreferences.editAllowed}" value="#{issueBean.edit}" />
            <f:viewParam name="objectId" value="#{issueBean.objectId}" />
        </f:metadata>
    </ui:define>
    <ui:param name="pageTitle" value="#{messages['issue.page.title']}" />
    <ui:define name="content">
        <hf:formPanel id="formPanel" label="#{messages['issue.page.panel']}" backingBean="#{issueBean}" >
            <hf:formField label="#{messages['issue.title']}" field="title" />
            <hf:formField label="#{messages['issue.description']}" field="description" textArea="true" />
            <hf:formField label="#{messages['issue.status']}" field="status" />
            <hf:formField label="#{messages['issue.issueDate']}" field="issueDate" rangeSearch="true" />
            <hf:formEntityField id="account" label="#{messages['issue.account']}" field="account" childField="accountNumber" popup="true" />
        </hf:formPanel>
        <hftl:entityPopup id="accountsPopup" header="#{messages['account.search']}" updateField=":formPanel:formId:account:account" selection="#{issueBean.entity.account}"
            backingBean="#{accountBean}" searchField1Label="#{messages['account.accountNumber']}" searchField1="accountNumber"
            column1Label="#{messages['account.accountNumber']}" column1="accountNumber" />
    </ui:define>
</ui:composition>

And of course messages.properties:

menu.issues=Issues
issue.search=Issue search
issue.title=Title
issue.status=Status
issue.issueDate=Date
issue.account=Account
issue.description=Description
issue.search.results=Search results
issue.page.title=Issue
issue.page.panel=Issue edit

And that’s it! Now you can search issues by title, by date, by account, by status. Go on create 10 or 20 of issues. You will have lazy datatable with pagination and sorting. You can also delete them or edit them. Or simply view details. Basically without writing any code. You can still use regular JSF. You can mix custom components with regular JSF tags. You can also modify those components or code to fit your needs. It is not a black box framework – its simply maven archetype and you own all the code! Sure all those classes we had to create could have been easily generated. That would be cool. Maybe some time in the future 😉

New issues window should look something like this after you are done:

issueEdit

Custom search

Creating simple crud pages is really easy with happyfaces custom components. But most of the time we need to work on something more complicated. That is not problem here: you can still use your regular jsf, implement additional method in services and modify all base classes provided by archetype. One of the most used feature is search. Searching auto magically is really cool but sometimes it can be a little bit limited. Of course you can simply implement new methods or create more complex page from scratch, but sometimes it would be nice to mix it up – have custom components search and some customized search working together.

First of all I recommend you to read a little bit about QueryDSL and then understand the magic of how the search with custom components works. Take a look at BaseService.getPredicate() method for that. If I need to explain how it works in one sentence I would say that JSF search component simply puts filter key (which is property to search) and value into filters map and then it is processed in getPredicate() method.

So lets say we want to see only issues that are not yet solved. That means new and working issues is shown and solved ones are filtered out. Status search filter can select only single status so to solve this we have to add another non standard filter. Lets use checkbox for that. Your issues.xhtml search part should look like this:


<hf:searchPanel id="searchPanel" columns="3" backingBean="#{issueBean}">
   <hf:searchField label="#{messages['issue.title']}" field="title" />
   <hf:searchField label="#{messages['issue.status']}" field="status" />
   <hf:searchField label="#{messages['issue.issueDate']}" field="issueDate" rangeSearch="true" />
   <hf:searchField id="accountField" label="#{messages['issue.account']}" field="account" childField="accountNumber" popup="true" />
   <h:panelGrid columns="2">
      <p:outputLabel for="excludeSolved" value="#{messages['issue.excludeSolved']}" />
      <p:selectBooleanCheckbox id="excludeSolved" value="#{issueBean.filters['issue.notSolved']}" />
    </h:panelGrid>
</hf:searchPanel>

We’ve added custom filter. However it will not be processed by getPredicate() method because key “issue.notSolved” is not property of Issue. The good news getPredicate() invokes processNonStandardFilters() method before processing filters map. We can override this method in our IssueService.java and use it to filter out all solved issues. It should look like this:

    @Override
    @SuppressWarnings("unchecked")
    protected BooleanExpression processNonStandardFilters(Map<String, Object> filters, List<String> filtersToRemove,
            @SuppressWarnings("rawtypes") PathBuilder pathBuilder) {
        BooleanExpression expression = null;
        
        Boolean notClosedFilter = (Boolean) filters.get("issue.notSolved");
        if (notClosedFilter != null) {
            if (notClosedFilter) {
                expression = pathBuilder.get("status").ne(IssueStatus.SOLVED);
            }
            filtersToRemove.add("issue.notSolved");
        }

        return expression;
    }

This code returns predicate that shows only issues with status NOT equal to SOLVED. Also don’t forget to remove that filter (by adding it to filtersToRemove list) so it won’t be processed again.

Of course this is only one of the ways to solve such a problem. You are of course free to modify code as you like and as your project requires but for not too complicated searches this method really allows mixing standard and customized searches easily.

Here is what the end result with “not solved” filter looks like:

issues

The end

That is it. I hope you liked this tutorial. As you can see this archetype could save you quite some time. There are more stuff like unit tests and integration tests – they are pre configured with dbunit and load spring context! Also you can run mvn site:run and get maven site with various reports up and running in seconds! And for REST web services you just need to implement controller for it. Take a look at HappyFacesExceptionHandler.java for some centralized error handling for your application. There are much more 🙂 I hope you will find all of this useful.

You can find the project on github here. I’m really looking forward to feedback! Let me know what do you think.

Sorting algorithms

My first post will hardly be original. In fact it is probably most unoriginal post ever 🙂 I will implement and compare several sorting algorithms in Java. I’m not going into deep details on how each algorithm works but will try to explain big picture and provide nice clean Java code and some illustrations or links to more information. Also I will try to microbenchmark some of those algorithms.

First algorithm – Insertion sort.

Its probably simplest (and most inefficient O(n^2)) algorithm of the bunch I will discuss. We start from second element and compare it with the first one. If it is smaller we swap them. Now we have the first one smaller than the second one. Then we take element #3 and compare with the second and first ones. If element #3 is smaller than #2 but bigger than #1 – its new place is between #1 and #2.  If element is smaller than both – its new place is as #1. You probably see where it is going. We iterate through the list and find each element its new place. This gif from wiki is very clear illustration of how it works:

And here is JAVA implementation of this algorithm with some comments:

    public static int[] insertionSort(int[] data) {
        // run from second element to last
        for (int i = 1; i < data.length; i++) {
            int key = data[i];
            int j = i - 1;
            // take element and run back until smaller is found
            while (j >= 0 && data[j] > key) {
                data[j + 1] = data[j]; // move elements to make place for insert
                j--;
            }
            // insert element in position after a smaller element
            data[j + 1] = key;
        }
        return data;
    }

Quicksort

This is probably most used sorting algorithm as in practice it tends to be the fastest one. It is divide and conquer algorithm which selects some element called pivot and moves all elements that are smaller before it and all the greater ones after. Then it takes those 2 sub lists and do the same (recursion). Now we have 4 sub lists and first one contains elements that are smaller then second one which contains elements that are smaller than third one which contains elements smaller than fourth one. We divide and sort until we reach single element and get all the list sorted! Here is the image worth a thousand words:

And JAVA code:

    public static int[] quickSort(int[] data) {
        Sorter.quickSort(data, 0, data.length - 1);
        return data;
    }

    private static void quickSort(int[] data, int sublistFirstIndex, int sublistLastIndex) {
        if (sublistFirstIndex < sublistLastIndex) {
            // move smaller elements before pivot and larger after
            int pivotIndex = partition(data, sublistFirstIndex, sublistLastIndex);
            // apply recursively to sub lists
            Sorter.quickSort(data, sublistFirstIndex, pivotIndex - 1);
            Sorter.quickSort(data, pivotIndex + 1, sublistLastIndex);
        }
    }

    private static int partition(int[] data, int sublistFirstIndex, int sublistLastIndex) {
         // differently from gif example we take last element of list as pivot
        int pivotElement = data[sublistLastIndex];
        int pivotIndex = sublistFirstIndex - 1;
        for (int i = sublistFirstIndex; i < sublistLastIndex; i++) {
            if (data[i] <= pivotElement) {
                pivotIndex++;
                ArrayUtils.swap(data, pivotIndex, i);
            }
        }
        ArrayUtils.swap(data, pivotIndex + 1, sublistLastIndex);
        return pivotIndex + 1; // return index of pivot element
    }

Merge sort

If quicksort was dividing list into smaller and smaller sub lists, merge sort takes opposite approach. It merges sorted sub lists into larger and larger list until it reaches the result of full sorted list. Smallest possible sub list is single element (which can be considered sorted). So we take first an second elements compare them and swap if second one is smaller than first one. Do same with #3 and #4, #5 and #6 etc. Now we have sorted sub lists each containing 2 elements. Do same with those. Sub list with now sorted elements #1 and #2 is merged with sub list with elements #3 and #4 and result is 4 element sorted sub list. And same operation is repeated until we have only single sorted list.

JAVA code:

    public static int[] mergeSort(int[] data) {
        mergeSort(data, 0, data.length - 1);
        return data;
    }
    private static void mergeSort(int[] data, int firstSublistStartIndex, int secondSublistEndIndex) {
        if (firstSublistStartIndex < secondSublistEndIndex) {
            int firstSublistLastElementIndex = (firstSublistStartIndex + secondSublistEndIndex) / 2;
            // recursively reach sub lists that has only one element
            Sorter.mergeSort(data, firstSublistStartIndex, firstSublistLastElementIndex);
            Sorter.mergeSort(data, firstSublistLastElementIndex + 1, secondSublistEndIndex);
            // then start merging them
            Sorter.merge(data, firstSublistStartIndex, firstSublistLastElementIndex, secondSublistEndIndex);
        }
    }
    private static void merge(int[] data, int firstSublistStartIndex, int firstSublistLastElementIndex,
            int secondSublistEndIndex) {
        int firstArrayLenght = firstSublistLastElementIndex - firstSublistStartIndex + 1;
        int secondArrayLenght = secondSublistEndIndex - firstSublistLastElementIndex;
        int[] firstArray = new int[firstArrayLenght + 1];
        int[] secondArray = new int[secondArrayLenght + 1];
        // copy first sub array to separate array
        for (int i = 0; i < firstArrayLenght; i++) {
            firstArray[i] = data[firstSublistStartIndex + i];
        }
        // copy second sub array to separate array
        for (int i = 0; i < secondArrayLenght; i++) {
            secondArray[i] = data[firstSublistLastElementIndex + 1 + i];
        }
        // optimization. because last element is maximum, we don't need to check
        // if current index is not out of bounds
        firstArray[firstArrayLenght] = Integer.MAX_VALUE;
        secondArray[secondArrayLenght] = Integer.MAX_VALUE;

        int firstCurrentIndex = 0;
        int secondCurrentIndex = 0;

        // merge firstArray and second array to data[p..r]
        for (int i = firstSublistStartIndex; i <= secondSublistEndIndex; i++) {
            // compare current values from sub arrays (both values are smallest
            // in each array) and move smaller one to data[p..r]
            if (firstArray[firstCurrentIndex] <= secondArray[secondCurrentIndex]) {
                data[i] = firstArray[firstCurrentIndex];
                firstCurrentIndex++;
            } else {
                data[i] = secondArray[secondCurrentIndex];
                secondCurrentIndex++;
            }
        }
    }

Heap sort

What would be naive sort algorithm that comes to mind as first idea to inexperienced programmer? I guess it would be something like run through the list, find smallest element and put it first, then run from second element to the end and again find smallest element and put it to second place etc – until we sort everything. This not very efficient algorithm (O(n^2) is called selection sort. Heap sort is more efficient variation of selection sort. It too selects smallest (largest) element and puts it to beginning (end) of the list. However to select smallest/largest element it uses data structure called heap which make algorithm much more efficient. Heap is binary tree-like data structure whose every node is always smaller(larger) than its children nodes. So in order to select smallest/largest element we just take it from the root node. The algorithm then basically is 2 step process. First heap is built from data. Simple array is enough for that (element #1 becomes root node, #2 and #3 its children, #4 and #5 elements becomes #2’s children etc…). Second step is remove smallest(largest) element from the root node of the heap and place it first(last). Of course after removal heap must be updated so its root is again smallest. Continue until all the list is sorted. Here is gif which hopefully make it more clear:

JAVA code:

    public static int[] heapSort(int[] data) {
        // build heap
        HeapUtils.buildMaxHeap(data);
        int heapSize = data.length;
        for (int i = data.length - 1; i > 0; i--) {
            // move largest element to the end
            ArrayUtils.swap(data, 0, i);
            // rebuild heap with smaller size by 1 (last element already sorted)
            HeapUtils.maxHeapify(data, 0, --heapSize);
        }
        return data;
    }
    public static void buildMaxHeap(int[] data) {
        for (int i = data.length / 2; i >= 0; i--) {
            maxHeapify(data, i);
        }
    }
    public static void maxHeapify(int[] data, int index) {
        maxHeapify(data, index, data.length);
    }
    // build heap structure &quot;in place&quot; where index is root node and heapSize is number of elements
    public static void maxHeapify(int[] data, int index, int heapSize) {
        int leftLeaf = getLeftLeaf(index);
        int rightLeaf = getRightLeaf(index);
        int largest = index;
        if (leftLeaf < heapSize && data[leftLeaf] > data[largest]) {
            largest = leftLeaf;
        }
        if (rightLeaf < heapSize && data[rightLeaf] > data[largest]) {
            largest = rightLeaf;
        }
        if (largest != index) {
            ArrayUtils.swap(data, index, largest);
            HeapUtils.maxHeapify(data, largest, heapSize);
        }
    }

OK time to do some benchmarks. For that I used JMH micro benchmark framework. I will simply measure sorting of 100 000 random integers. Of course you can clone the project from github (link at the end of the article) and try different variations. How algorithms act with less elements or with more? Is there a problem when array is already sorted (hint see quicksort)? However for now I will simply post results of 100000 random elements sorting. Here we go:

Benchmark Score Score error Units
Heap sort 20.789 0.657 ms/op
Insertion sort 2381.962 38.257 ms/op
Arrays.sort 11.203 0.218 ms/op
Merge sort 27.680 0.713 ms/op
Quicksort 12.726 0.207 ms/op

We could have expected somewhat similar results. Of course slowest was insertion sort. Fastest optimized and well implemented JDK sort algorithm. JDK sort algorithm is variation of quicksort so no surprise that custom quicksort implementation was just a little bit slower than JDK version. And then somewhat similar performance of heapsort and mergesort with heapsort being a bit faster.

Those are main and most popular sorting methods. There are various variations and hybrid methods as well. For example Timsort – hybrid of merge and insertion sort which is now used in JDK 7 for sorting non primitive types (take a look at source code of Arrays.java). And for primitive types it looks like JDK use some sophisticated quick sort algorithm with double pivots. Why is the difference? I don’t know, but I guess the reason is that merge sort (and Timsort) is stable algorithm meaning that after sorting even if elements were equal they still maintain same sequence as it was in input (for example sorting people by age, both John and Peter is 25 after sorting John still is before Peter like it was before sorting in input). Quicksort does not have this guarantee, but probably is faster in practice and though preferred method for primitive types. So we can see that library developers already is thinking for us and its probably best just to use standard tools and not reinvent the wheel unless you really know what you are doing and really can get better performance. So lets review algorithms and compare them.

Algorithm Average Worst case Best case Stable Memory Best use cases
Insertion sort O(n^2) O(n^2) O(n) Yes O(1) (in place) Quite efficient for small lists. Sometimes used in hybrid implementation to sort very small sub lists. It can also sort a list at the same time as it receives it.
Quicksort O(n log(n)) O(n log(n)) O(n log(n)) No O(log n) In practice tends to be faster algorithm than others.
Merge sort O(n log(n)) O(n log(n)) O(n log(n)) Yes O(n) With RAM based arrays tends to be slower than quicksort, but can be more efficient with slower media. Needs more memory, but is stable.
Heap sort O(n log(n)) O(n log(n)) O(n log(n)) No O(1) It’s performed in place and has very close performance to quicksort, so its good choice when memory is the issue.

OK so those were so called comparison sorting algorithms. And we can’t really do much better than that. Of course there are various improvements as I mentioned. For example quicksort with dual pivots (interesting read here) but still they are no better than O(n logn). But are we sure we can’t do better? And the answer is it depends! Under some circumstances we could. Imagine we know that we need to sort some numbers with range 0 to 99 and each number can appear only once. Yes we could use insertion sort or quicksort for this task. But if you think a bit – a much quicker version would be simply create a new boolean array with 100 elements and then just run through the input and set value in that helper array with key = input element to true. This way we simply need to print all the indexes that has it true in helper array. And that is very quick. That kind of sorting is called distribution sorting. It can be really fast but you need to know range of possible values of elements and of course need additional memory for a helper array. Lets review some distribution sorting algorithms.

Counting sort

This is slightly more sophisticated algorithm than the one I described above. The main difference is that we use integers instead of boolean in helper array and counting the number of element occurrences. This allows input to have equal elements because we are “counting” them.

JAVA CODE

    public static int[] countingSort(int[] data, int upperBound) {
        int dataLenght = data.length;
        int tempArrayLength = upperBound + 1;
        int[] tempArr = new int[tempArrayLength];
        // count how much of each element (index - element, value - count)
        for (int i = 0; i < dataLenght; i++) {
            tempArr[data[i]]++;
        }
        // count how much of less or equal elements exists
        for (int i = 1; i < tempArrayLength; i++) {
            tempArr[i] += tempArr[i - 1];
        }

        int[] sortedData = new int[dataLenght];
        // put each element to its place in sorted array
        for (int i = dataLenght - 1; i >= 0; i--) {
            int place = tempArr[data[i]] - 1; // element place in result array
            sortedData[place] = data[i];
            tempArr[data[i]]--; // decrease count less or equal elements count
        }

        return sortedData;
    }

Radix sort
In radix sort we are sorting by comparing individual digits from the last one to the first one. In essence radix sort is like this: sort elements by last digit. Then sort elements by second to last digit up till we reach first digit and after that all elements are in sorted order.
The sorting can be done by having buckets for each number and putting elements into each bucket (like in this explanation) or as in implementation provided here reuse counting sort.
As you can see for this method to work you need to know largest number of digits that elements in your data set might contain (or you will need to determine that dynamically which cost time too). Complexity of algorithm is O(kn) where k is number of digits and n is number of elements. If k is very big this sort might be not as efficient as even comparison sorts.

JAVA code for radix sort:

    public static int[] radixSort(int[] data, int numberOfDigits) {
        int[] sortedData = data;
        for (int i = 0; i < numberOfDigits; i++) {
            sortedData = Sorter.countingSortByDigit(sortedData, i, 9);
        }
        return sortedData;
    }
    private static int[] countingSortByDigit(int[] data, int digitIndex, int upperBound) {
        int dataLenght = data.length;
        int tempArrayLength = upperBound + 1;
        int[] tempArr = new int[tempArrayLength];
        // count how much of each element (index - element, value - count)
        for (int i = 0; i < dataLenght; i++) {
            int digitFromNumber = MathUtils.getDigitFromNumber(data[i], digitIndex);
            tempArr[digitFromNumber]++;
        }
        // count how much of less or equal elements exists
        for (int i = 1; i < tempArrayLength; i++) {
            tempArr[i] += tempArr[i - 1];
        }

        int[] sortedData = new int[dataLenght];
        // put each element to its place in sorted array
        for (int i = dataLenght - 1; i >= 0; i--) {
            int digitFromNumber = MathUtils.getDigitFromNumber(data[i], digitIndex);
            int place = tempArr[digitFromNumber] - 1; // element place in result
                                                      // array
            sortedData[place] = digitFromNumber;
            tempArr[digitFromNumber]--; // decrease count less or equal elements
                                        // count
        }

        return sortedData;
    }

Bucket sort
Bucket sort is method that is taking advantage that small lists are faster to sort than very big ones. So it simply splits input into “buckets” and then uses another sorting algorithm to sort those buckets. It is also possible to use bucket sort recursively too. Elements in each bucket is not overlapping so after each bucket is sorted they can be simply joined into the sorted result list. For example lets say we have 3 buckets and put into first elements 3 and 1, into second elements 5 and 8 and into third 11 9 and 12. After sorting each bucket and joining them into a list we get 1 3 5 8 9 11 12 sorted output. In fact bucket sort could be viewed as generalized version of counting sort. Take a look at explanation here The implementation of bucket sort here is efficient way to sort double numbers with range 0 to 1.

JAVA code:

   public static double[] bucketSort(double[] data) {
        int numberOfBuckets = data.length;
        double[][] buckets = new double[numberOfBuckets][];
        int[] bucketListIndices = new int[numberOfBuckets];
        for (int i = 0; i < data.length; i++) {
            int bucketIndex = (int) ((double) numberOfBuckets * data[i]);
            if (buckets[bucketIndex] == null) {
                buckets[bucketIndex] = new double[1];
            } else {
                // increase bucket size by 1 (maybe better redo with linked list)
                double[] bucket = buckets[bucketIndex];
                buckets[bucketIndex] = Arrays.copyOf(bucket, bucket.length + 1);
            }
            buckets[bucketIndex][bucketListIndices[i]++] = data[i];
        }

        double[] sortedData = new double[data.length];
        int nextIndex = 0;
        // sort all buckets with insertion sort and merge them into result.
        for (int bucketIndex = 0; bucketIndex < numberOfBuckets; bucketIndex++) {
            if (buckets[bucketIndex] != null) {
                int bucketLength = buckets[bucketIndex].length;
                System.arraycopy(sortedData, nextIndex, Sorter.insertionSort(buckets[bucketIndex]), 0, bucketLength);
                nextIndex = nextIndex + bucketLength - 1;
            }
        }

        return sortedData;
    }

So these are all algorithms I wanted to review here. Keep in mind those are only introductions here and my benchmarks are quite naive. Wikipedia is great starting point if you are interested into deeper understanding of the algorithms and learning all the subtleties and tricks that can improve performance. Hope you enjoyed this article!
You can find all the algorithms and benchmarks in the github project here.