Unless algorithm development is part of the job, many software engineers use readily available algorithmic methods as needed and rarely need to develop algorithms themselves. I’m not talking about some complicated statistical or machine learning algorithms. Just simple mundane ones such as a sorting algorithm. Even if you don’t need to code algorithms, going back to writing a sorting program can still be a good exercise to review certain basic skills that might not be frequently used in your current day job. It’s a good-sized programming exercise that isn’t too trivial or taking up too much time. It also reminds you some clever (or dumb) tricks on how to perform sorting by means of recursive divide-and-merge, pivot partitioning, etc. And if nothing else, it might help you in your next technical job interview in the near future.
If you’re up for such an exercise, first, look up from Wikipedia or any other suitable source for a sorting algorithm (e.g. Merge Sort, Quick Sort) of your choice to re-familiarize yourself with its underlying mechanism. Next, decide on the scope of the application – for example, do you want an integer-sorting application or something more generic? … etc. Next, pseudo code, pick the programming language of your choice, and go for it.
Appended is a simple implementation of both Merge Sort and Quick Sort in Java. For the convenience of making method calls with varying data types and sorting algorithms, an interface (SimpleSort) and a wrapper (Sorter) are used. Java Generics is used to generalize the sorter for different data types. Adding Generics to a sorting application requires the using of either the Comparable or Comparator interface, as ordering is necessary in sorting. In this example application, the Comparable interface is used since the default ordering is good enough for basic sorting. The overall implementation code is pretty self explanatory.
SimpleSort.java
|
1 2 3 4 5 6 |
package sorting; public interface SimpleSort<E extends Comparable<E>> { public void sort(E[] list); } |
Sorter.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
package sorting; public class Sorter<E extends Comparable<E>> { public void performSorting(E[] list, SimpleSort<E> sortingAlgo) { long startTime, elapsedTime; System.out.println("\nOriginal " + list.getClass().getSimpleName() + " list: ..."); for (int i = 0; i < list.length; i++) { System.out.print(list[i] + " "); } System.out.println(); startTime = System.currentTimeMillis(); sortingAlgo.sort(list); elapsedTime = System.currentTimeMillis() - startTime; System.out.println("\nResult: " + sortingAlgo.getClass().getSimpleName() + " ..."); for (int i = 0; i < list.length; i++) { System.out.print(list[i] + " "); } System.out.println("\n\nTime taken: " + elapsedTime + "ms"); } } |
MergeSort.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
package sorting; public class MergeSort<E extends Comparable<E>> implements SimpleSort<E> { private E[] list; private E[] holder; @SuppressWarnings({"unchecked"}) public void sort(E[] list) { this.list = list; int size = list.length; // Type erasure: first bound class of <E extends Comparable<E>> holder = (E[]) new Comparable[size]; mergeSort(0, size - 1); } private void mergeSort(int left, int right) { if (left < right) { int center = left + (right - left) / 2; mergeSort(left, center); mergeSort(center + 1, right); merge(left, center, right); } } private void merge(int left, int center, int right) { for (int i = left; i <= right; i++) { holder[i] = list[i]; } int i = left; int j = center + 1; int k = left; while (i <= center && j <= right) { if (holder[i].compareTo(holder[j]) <= 0) { list[k] = holder[i]; // Overwrite list[k] with element from the left list i++; } else { list[k] = holder[j]; // Overwrite list[k] with element from the right list j++; } k++; } // Overwirte remaining list[k] if the left list isn't exhausted // No need to do the same for the right list, as its elements are already correctly placed while (i <= center) { list[k] = holder[i]; k++; i++; } } } |
QuickSort.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
package sorting; import java.util.Random; public class QuickSort<E extends Comparable<E>> implements SimpleSort<E> { private E[] list; @SuppressWarnings({"unchecked"}) public void sort(E[] list) { this.list = list; int size = list.length; quickSort(list, 0, size-1); } private void swapListElements(E[] list, int index1, int index2) { E tempValue = list[index1]; list[index1] = list[index2]; list[index2] = tempValue; } private int partitionIndex(E[] list, int left, int right, int pivot) { int pivotIndex; E pivotValue; pivotValue = list[pivot]; swapListElements(list, pivot, right); // Swap pivot element to rightmost index pivotIndex = left; // Calculate pivot index starting from leftmost index for (int i = left; i < right; i++) { if (list[i].compareTo(pivotValue) < 0) { swapListElements(list, i, pivotIndex); pivotIndex++; } } swapListElements(list, pivotIndex, right); // Swap pivot element back to calculated pivot index return pivotIndex; } private void quickSort(E[] list, int left, int right) { int randomIndex, pivotIndex; if (left < right) { // Pick random index between left and right (inclusive) Random randomNum = new Random(); randomIndex = randomNum.nextInt(right-left+1) + left; pivotIndex = partitionIndex(list, left, right, randomIndex); quickSort(list, left, pivotIndex - 1); quickSort(list, pivotIndex + 1, right); } else return; } } |
SortingMain.java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
package sorting; public class SortingMain { @SuppressWarnings({"unchecked"}) public static void main(String[] args) { Integer[] integerList = {8, 15, 6, 2, 11, 4, 7, 12, 3}; Double[] doubleList = {2.5, 8.0, 7.2, 4.9, 6.6, 1.8, 3.0, 7.5}; Character[] characterList = {'M', 'X', 'B', 'C', 'T', 'R', 'F', 'S'}; String[] stringList = {"lion", "tiger", "snow leopard", "jaguar", "cheeta", "cougar", "leopard"}; Sorter sorter = new Sorter(); sorter.performSorting(integerList, new MergeSort()); sorter.performSorting(doubleList, new QuickSort()); sorter.performSorting(characterList, new MergeSort()); sorter.performSorting(stringList, new QuickSort()); } } |
Pingback: Programming Exercise – Binary Tree | Genuine Blog