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.
