August232011

Sorting algorithms round-up

Testing the previously posted sorting algorithms.

public static void main(String[] args) {
    // TODO Auto-generated method stub
    for(int j=0; j < 6; j++) {
        // generate random sequence
        Random rng = new Random();
        int length = 10000000;
        int[] a = new int[length];
        for (int i = 0; i < a.length; i++) {
            a[i] = rng.nextInt();
        }
        // sort and measure time
        long start = System.currentTimeMillis();
        if(j==0 && length < 100000){
            selection_sort(a);
            log(“Selection sort”);
        }
        else if(j == 1 && length < 100000) {
            bubble_sort(a);
            log(“Bubble sort”);
        }
        else if(j == 2 && length < 100000) {
            insertion_sort(a);
            log(“Insertion sort”);
        }
        else if(j == 3 && length < 100000) {
            comb_sort(a);
            log(“Comb sort”);
        }
        else if(j == 4) {
            a = merge_sort(a);
            log(“Merge sort”);
        }
        else if(j == 5) {
            a = quick_sort(a);
            log(“Quick sort”);
        }
        long end = System.currentTimeMillis();
        log(“Time taken: ” + (end-start) + “ms\n”);
    }
}

Surprisingly, merge sort still takes the lead, despite quick sort’s participation. In sorting 10,000 integer values, the following output was stable.

Selection sort
Time taken: 78ms
 
Bubble sort
Time taken: 277ms
 
Insertion sort
Time taken: 126ms
 
Comb sort
Time taken: 276ms
 
Merge sort
Time taken: 17ms
 
Quick sort
Time taken: 15ms

With a length of 10,000,000 integer values, quick_sort() takes around 4.31 seconds while merge_sort() wins out with 3.83 seconds very stable.

Various other set-ups reproduce interesting results: an almost-sorted list with a few turtles (small values near the end) gets sorted most efficiently by selection_sort(). Surprisingly, comb_sort() which is supposed to be an improvement of bubble sort specifically targeted to eliminate turtles seems to lose to bubble_sort() itself in that scenario.

Perhaps the values for comb_sort() and quick_sort() —the shrink factor and the pivot point— are not well-chosen. It is advisable that we meddle with these values for ourselves and see if/with which it works out.

Page 1 of 1