I wanted some more Java practice before I start my new job as a Software Engineer working with Java, so I decided to implement some basic sorting algorithms and time them. For each algorithm I chose to start by coping the ArrayList into a new one as to preserve the original input. I started with bubble sort, as I remembered it was simple but incredibly slow:
public static ArrayList<Integer> bubble(ArrayList<Integer> input ) { ArrayList<Integer> result = new ArrayList<Integer>(); result.addAll(input); while(true) { boolean done = true; for(int i = 1; i < result.size(); i++) { if (result.get(i) < result.get(i-1)) { int temp = result.get(i - 1); result.set(i - 1, result.get(i)); result.set(i, temp); done = false; } } if(done) { break; } } return result; }
With my test of 100,000 randomly generated Integers between 0 and 99,999, bubble sort was able to complete the sort in 64.82 seconds.
Next I moved on to quick sort as I knew it would be much better:
public static ArrayList<Integer> quick(ArrayList<Integer> input) { ArrayList<Integer> result = new ArrayList<Integer>(); result.addAll(input); if (result.size() <= 1) { return result; } Integer pivot = result.get(0); result.remove(0); ArrayList<Integer> less = new ArrayList<Integer>(); ArrayList<Integer> more = new ArrayList<Integer>(); for (int i = 0; i < result.size(); i++) { if (result.get(i) <= pivot) { less.add(result.get(i)); } else { more.add(result.get(i)); } } ArrayList<Integer> output = new ArrayList<Integer>(); output.addAll(quick(less)); output.add(pivot); output.addAll(quick(more)); return output; }
Using the same ArrayList of Integers quick sort was able to finish in merely 0.71 seconds, obviously a huge speed up! I then decided to implement insertion sort:
public static ArrayList<Integer> insertion(ArrayList<Integer> input) { ArrayList<Integer> result = new ArrayList<Integer>(); // make new ArrayList from input in order to preserve input result.addAll(input); for (int i = 0; i < result.size(); i++) { int x = result.get(i); int j = i; while (j > 0 && result.get(j-1) > x) { result.set(j, result.get(j-1)); j--; } result.set(j, x); } return result; }
With insertion sort, our ArrayList was sorted in 4.319 seconds. Next, I chose to implement selection sort:
public static ArrayList<Integer> selection(ArrayList<Integer> input) { ArrayList<Integer> result = new ArrayList<Integer>(); // make new ArrayList from input in order to preserve input result.addAll(input); int min; for (int i = 0; i < result.size() - 1; i++) { min = i; for (int j = i + 1; j < result.size(); j++) { if(result.get(j) < result.get(min)) { min = j; } } if (min != i) { int temp = result.get(i); result.set(i, result.get(min)); result.set(min, temp); } } return result; }
Selection sort was able to sort the same ArrayList in 14.187 seconds. These results all make sense with the complexities of each respective algorithm. For more information on each algorithm and some pseudo code to work off of check out wikipedia.
