In this lecture we will learn about two basic problems in programming: sorting and searching. We will also learn how to analize the complexity of the algorithms.
Sorting is one of the most basic tasks in programming. The libraries in Java provide methods for sorting that you can use for free, but by looking at the algorithms you can learn how to design new algorithms and to analize their complexity. There are many different sorting algorithms but we will discuss only two of them - selection sort and merge sort.
Selection sort is the simplest possible sorting algorithm. We search for the smallest number in the array and we exchange the first element in the array with the smallest one. After that we do the same for the fragment from element with index one to the end of the array, i.e. we search for the next smallest number and we exchange it with the second element. If we continue in this way then at the end we will have the whole array sorted. The source code for the selection sort is in the attached file SelectionSorter.java.
This is a simple algorithm but it takes approximately n2 steps to sort an array with n elements. On every step we must search for the smallest number. On the first step we have to search among n-1 elements and we have to do one swap. We count the swap as three operations since it involves three assignments. The search involves n-1 elements so we count this as n-1 steps. The conclusion is that the first step involves n-1+3==n+2 operations. The second step does the same but this time we have n-2 elements which means n-2+3=n+1 operations. By doing the same for every step we can conclude that sorting the whole array takes:
(n+2) + (n+1) + n ... + 4 = (n+6)*(n-1)/2 = (n^2)/2 + 5*n/2 - 3
When we compute the complexity of algorithms we are usually interested only in the order of time that the algorithm requires. For example when the array is big then the quadratic term will be much bigger than the linear component. This means that we can safely ignore the linear term. At the same time the constant factor is also irrelevant since the formula above shows only the number of operations. Since every operation takes different physical time, the expression for the computational time will have to be scaled by some factor that depends on the particular computer architecture. The only conclusion that we can draw from the formula above is that the time needed to sort an array of size n is proportional to n2. In order to emphasize that this is only a measure of the order of time and not the exact physical time we use the Big Oh notation, i.e. we write O(n2).
The Merge Sort algorithm is a lot more complex but it also a lot faster. The source code is in the file MergeSorter.java. The idea is to use the divide and conquer strategy. In order to sort an array we divide it in two equal parts and we sort each of them separately. After that we merge the already sorted parts. Note that the sorting of each part is done by the same algorithm. This means that the array is first divided in two parts after that each part is again divided which means that we get four parts. Each of the four parts is again divided and we continue in this way until we get an array on size zero or one. The is the basic case and since an array of size zero and one is trivially sorted we can just return the same array.
On every step we divide the array into two parts. This means that we have to create two new arrays and to copy the content of the old array into the new arrays. We count the copying for an array of size n as 2*n operations since it involves n reads and n writes. Furthermore we have to merge the parts after they are sorted. We count the merging as 2*n operations since we have to read the elements of the first/second part and to store them in the final array. In total this two steps take 4*n operations. In addition we must add the time for sorting the two parts. The conclusion is that the time T(n) to sort an array of size n is computable with:
T(n) = 2*T(n/2) + 4*n
This formula needs a bit of reorganization to make it easier to understand. We can rewrite T(n/2) in the following way:
T(n/2) = 2*T(n/4) + 4*(n/2)
which we can substitute:
T(n) = 4*T(n/4) + 4*n + 4*n
We can continue in this way by substituting the expression for T on the right hand side with something else. In general on the k-th substitution step we will have:
T(n) = (2^k)*T(n/(2^k)) + 4*n*k
If we assume that n is an exact power of two then if we can repeat this step exactly log(n) times i.e. k = log(n) (here I assume binary logarithm) then we will get:
T(n) = (2^log(n))*T(1) + 4*n*log(n)
= n + 4*n*log(n)
Here we substitute T(1) = 1 since sorting an array with only one element is a trivial operation. Now again we can transform this formula to the Big Oh notation. Sorting an array by using the merge sort algorithm requires O(n*log(n)) operations.
It happens very often that we have a collection of elements and we need to find an element with given properties in this collection. The details of the search procedure depend on the situation but there are two simple cases.
If we have an array where the elements are in arbitrary order, then the only way to find a given element is to iterate over the array and to test each element one by one:
public static int search(int x, int[] a) {
for (int i = 0; i < a.length; i++) {
if (x == a[i])
return i;
}
return -1;
}
Since we iterate over the whole array, the complexity of the search is linear to the size of the array, i.e. we get O(n) complexity.
If we know in advance that the array is sorted, then we can do a lot faster search. Again we use the divide and coquer principle. We divide the array into two equal parts and we compare the element that we search for with the element in the middle of the array. If it is smaller then we continue the same procedure with the first part of the array. If it is bigger then we continue searching in the second part of the array. If it happes to be equal then we have just found the element that we want.
public static int search(int x, int[] a) {
int low = 0;
int high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == x)
return mid;
else if (a[mid] < x)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}
The analysis of the complexity is similar to the one with merge sort. On every step we do one comparison and after that we continue searching in one of the two parts of the array. The time to search in an array of size n is:
T(n) = T(n/2) + 1
Using the same trick as above we can derive that:
T(n) = T(n/(2^k)) + k
If we assume that n is a power of two then we can also conclude that:
T(n) = 1 + log(n)
From which we see that the final complexity is O(log(n)).
The standard libraries provided with Java already have methods for sorting and searching. If you have an array that you want to sort, then you can use one of the variants of the static method sort from the class Arrays. Similarly there is a method binarySearch which can be used to search in an array.
In both cases if the array contains objects, then implementation needs to know how to compare these objects. There is a standard interface that all comparable objects must implement:
public interface Comparable {
int compareTo(Object otherObject);
}
The method compareTo must return zero if the two objects are equal, positive number if the current object is bigger than the other object and a negative number if the current object is smaller.