I am involved in maintaining legacy Java code written by long forgotten souls and came across a mesmerizing function that finds the minimum of an array. It boils down to the following:
static int findMin(int[] orgArray) {
//A typical "WTF is this shit?!" case...
int[] sortedArray = Arrays.copyOf(orgArray, orgArray.length);
int minValue = 0;
Arrays.sort(sortedArray);
for (int i = 0; i < sortedArray.length; i++) {
if (orgArray[i] == sortedArray[0]) {
minValue = orgArray[i];
break;
}
}
return minValue;
//TODO: This function should be simplified as follows:
/*
int minValue = orgArray[0];
for (int i = 0; i < orgArray.length; i++) {
if (orgArray[i] < minValue) {
minValue = orgArray[i];
}
}
return minValue;
*/
}
A classic "
WTF is this shit!" case...
If we
analyze the first algorithm, we can assume that
Arrays.sort() method will run at
O(n*log2(n)). The following for loop will run at
O(n) time. So in total it runs at O(n*log2(n)) + O(n) which asymptotically converges to O(n*log2(n)).
The second algorithm uses a single for loop and runs at O(n).
Update - November 5th, 2016: There is a somewhat similar looking case (determining if there are repeating elements) where using Arrays.sort improves performance ["
Data Structures and Algorithms in Java", 6th Edition, p.174-5]:
/∗∗ Returns true if there are no duplicate elements in the array. ∗/
public static boolean unique1(int[ ] data){
int n = data.length;
for (int j=0; j < n−1; j++)
for (int k=j+1; k < n; k++)
if (data[j] == data[k])
return false; // found duplicate pair
return true; // if we reach this, elements are unique
}
The above funtion runs in O(n^2). Using Arrays.sort, we can decrease the running time to O(n*log2(n)):
public static boolean unique2(int[] data) {
int n = data.length;
int[] temp = Arrays.copyOf(data, n);
Arrays.sort(temp);
for (int j=0; j < n−1; j++)
if (temp[j] == temp[j+1])
return false; // found duplicate pair
return true; // if we reach this, elements are unique
}
