Okay, so we are convinced that if we have a sorted array, it takes a lot less time to find an element in it. But how do we get a sorted array? An arbitrary array is unlikely to be sorted. The algorithm of getting a sorted array out of an arbitrary array while keeping all the elements same, that is, by only rearranging the elements of an input array, is called sorting. There are a lot of algorithms for sorting. But in this chapter, we will start with a few simple ones that are not efficient. In the next chapter, we will explore efficient sorting algorithms.
This is the most natural algorithm for sorting. We choose each position of the array and find the element in the array that belongs in that position. The functional definition of selection sort is as follows:
- Find the minimum element in an array
- Swap this element with the first element of the array
- Sort the rest of the array after the first element recursively
Finding the minimum element has the functional structure as follows:
- Consider the array as a composition of the first element and the rest of the array.
- Find the index of the minimum element in the rest of the array.
- Compare this element with the first element. If this element is smaller than the first element, then it is the minimum element in the entire array. Otherwise, the first element is the minimum element.
Instead of making copies of the array, we represent subarrays by simply storing the starting index we want to consider, and then we work on the index recursively.
First, we write a function to find the index of the minimum element in a given array, starting from a position:
public static <E extends Comparable<E>> int findMin(E[] array, int start){ Then, we check whether the start position is the last position in the array, in which case we just simply return the start position as there are no more elements:
if(start==array.length-1){
return start;
} We find the index of the minimum element in the array to the right of the current start position and compare that element with the current start element. We return whichever has the minimum element, as demonstrated in the following:
int restMinIndex = findMin(array, start+1);
E restMin = array[restMinIndex];
if(restMin.compareTo(array[start])<0){
return restMinIndex;
}else {
return start;
}
}The swap function swaps or interchanges two elements in the array at the given positions. This function is pretty straightforward:
public static <E> void swap(E[] array, int i, int j){
if(i==j)
return;
E temp = array[i];
array[i]=array[j];
array[j] = temp;
}With the findMin and swap functions in our repository, we can finally put down the selectionSort algorithm. We start off by passing the position zero as the value of the start parameter:
public static <E extends Comparable<E>> void selectionSort(
E[] array, int start){ Firstly, there is no sorting to be done if the array is empty:
if(start>=array.length){
return;
} Now, we just find the index of the minimum element and swap the current position with the index of the minimum position. This will put the minimum element in the current position:
int minElement = findMin(array, start);
swap(array,start, minElement); Then, we recursively sort the rest of the array:
selectionSort(array, start+1);
}Now, we can write a wrapper function to just do selectionSort without having to pass a start index:
public static <E extends Comparable<E>> void selectionSort(
E[] array) {
selectionSort(array, 0);
}We can test our code by creating an arbitrary array and then sorting it using our algorithm:
Integer[] array = new Integer[]{10, 5, 2, 3, 78, 53, 3};
selectionSort(array);
System.out.println(Arrays.toString(array));And the output would be as follows:
[2, 3, 3, 5, 10, 53, 78]
Note how all the elements are repositioned in ascending order, which means that the array is sorted.
Note
The form of selection sort shown is not functional in a strict sense because we are modifying the contents of an array. A truly functional sort of an array will make a copy of the array on every modification. However, this is very expensive. On the other hand, thinking of the algorithm in terms of smaller versions of the same problem, like we have done, does make the algorithm simpler to understand. I tried to hit a sweet spot where I have the simplicity of the recursive algorithm, but don't have to keep creating copies of the array.
To compute the complexity of the selection sort algorithm, first we have to compute the complexity of the findMin and swap functions. Let's start with the findMin function. As with any recursive function, we start with assuming that with an array of length n (in this case, the effective length of the array, starting from the start position), it takes us T(n) time to compute the findMin function. While recursively calling itself, it passes on an effective array of length n-1. So, we have the following equation:
T(n) = T(n-1) + A where A is a constants => T(n) – T(n-1) = A, so it is an arithmetic progression => T(n) = An + B where B is a constant => T(n) = θ(n)
Now, let's move on to the swap function. It has no recursion and no loops, so the complexity is constant or θ(1).
Finally, we are ready to compute the complexity of the function selectionSort. Say, for an effective length n of an array, the time taken is T(n). It calls itself with effective length n-1, it also calls findMin and swap functions, which are θ(n) and θ(1), respectively. So, we have this:
T(n) = T(n-1) + θ(n) + θ(1)
Note that some expressions that are θ (n) have been written as θ (n) itself. It should be read as, "Some function of n that has the asymptotic complexity, θ (n)." It turns out, for computing complexity of T(n), we don't have to actually know the actual expression, we can simply put Cn and D for functions that are θ (n) and θ (1), respectively, where C and D are constants. So, we form the following equation:
T(n) = T(n-1) + Cn + D => T(n) – T(n-1) = Cn + D
Similarly, T(n-1) - T(n-2) = C(n-1) + D and so on. If we stack these equations, we get the following:
T(n) – T(n-1) = Cn + D T(n-1) – T(n-2) = C(n-1) + D T(n-2) – T(n-3) = C(n-2) + D T(n-3) – T(n-4) = C(n-3) + D … T(1) – T(0) = C(1) + D
Adding both sides, we get this:
So, the selection sort has a complexity of θ(n2), where n is the size of the array being sorted. Now, we will see the next sorting algorithm, which is the insertion sort.
In selection sort, we first selected a position and then found the element that should sit there. In the insertion sort, we do the opposite; we first select an element and then insert the element into position where it should sit. So, for every element, we first find out where it should be and then we insert the element in the right place. So, we first see how to insert an element into a sorted array. The idea is that we are given an array of sorted elements and we are supposed to insert another element in the correct position, so that the resulting array remains sorted. We will consider a simpler problem. We are given an array that is sorted except for the last element. Our job is to insert the last element in the correct position. The recursive way to achieve this insertion is as follows:
- If the element to be inserted is bigger than the end element of the sorted array, it belongs in the end and the insertion is complete.
- Otherwise, we swap the last element with the element to be inserted and recursively insert this element in the rest of the smaller array in front of it.
We do it with the following function. The function takes an array and a position that represents this last position:
public static <E extends Comparable<E>> void insertElementSorted(
E[] array, int valueIndex) {
if (valueIndex > 0 && array[valueIndex].compareTo(array[valueIndex - 1]) < 0) {
swap(array, valueIndex, valueIndex - 1);
insertElementSorted(array, valueIndex - 1);
}
}If the last position or the valueIndex is 0, there is nothing to be done, as the element is already in the correct position, that is, 0. There is no array to the left of valueIndex in this case. If not, we compare the last element to the previous element. Since the array on the left is presumed to be sorted, the previous element is the largest element in the sorted part of the array. If the last element is bigger than even this one, there is nothing more to be done. If not, we swap the last element with the previous one and run the insertion recursively on the array with one less element. The last element has moved to the previous position and it must now be compared with the element before that, and so on.
With the insertion function available for sorted arrays, we are now ready to write the algorithm for an insertion sort. In every step of the insertion sort, we consider a boundary in the array. Everything on the left of the boundary has already been sorted. Our job in the current step is to insert the element at the boundary index into the left sorted array, which we achieve using the insertElementSorted function. We implement this sort with the following simple strategy. In any step, we do the following:
Of course, when boundary is zero, it means that there is no array to be sorted and we simply return:
public static <E extends Comparable<E>> void insertionSort(
E[] array, int boundary) {
if(boundary==0){
return;
}
insertionSort(array, boundary-1);
insertElementSorted(array, boundary);
}To compute the complexity of insertion sort, we must first compute it for the insertElementSorted function. Let the time taken for an array of effective length (that is, from zero to boundary-1), n be T(n). From there, we recursively call it with n-1. So, we have the following:
T(n) = T(n-1) + C where C is a constant => T(n) = θ(n)
Let's now assume that the time taken for sorting an array of n elements is S(n). Apart from the base case, it calls itself with one less argument and then calls the insertElementSorted function with an array of effective length n-1. Thus, we have this:
S(n) = S(n-1) + T(n) + D where D is a constant.
Again, when n is large, T(n) = θ(n); hence, it can be approximated by An where A is a constant. So, we have this:
S(n) = S(n-1) + An + D => S(n) – S(n-1) = An + D,
Since this is true for all n, we have:
S(n) – S(n-1) = An + D S(n-1) – S(n-2) = A(n-1) + D S(n-2) – S(n-3) = A(n-2) + D … S(1) – S(0) = A + D
Summing both sides, we get the following:
Thus, insertion sort has the same asymptotic complexity as selection sort.
Another interesting sorting algorithm is a bubble sort. Unlike the previous algorithms, this one works at a very local level. The strategy is as follows:
- Scan through the array, searching pairs of consecutive elements that are ordered wrongly. Then find a j, such that array[j+1] < array[j].
- Whenever such a pair is found, swap them and continue searching until the end of the array and then back from the beginning again.
- Stop when a scan through the entire array does not even find a single pair.
The code that does this is as follows:
public static <E extends Comparable<E>> void bubbleSort(
E[] array) {
boolean sorted = false;
while (!sorted) {
sorted = true;
for (int i = 0; i < array.length - 1; i++) {
if (array[i].compareTo(array[i + 1]) > 0) {
swap(array, i, i + 1);
sorted = false;
}
}
}
}The flag, sorted, keeps track of whether any inverted pairs were found during a scan. Each iteration of the while loop is a scan through the entire array, the scan being done inside the for loop. In the for loop, we are, of course, checking each pair of elements, and if an inverted pair is found, we swap them. We stop when sorted is true, that is, when we have not found a single inverted pair in the entire array.
To see that this algorithm will indeed sort the array, we have to check two things:
- When there are no inverted pairs, the array is sorted. This justifies our stopping condition.
- Irrespective of the input, the program will eventually reach the preceding condition after a finite number of steps. That is to say that we need the program to finish in a finite number of steps. To see this, we need to understand the concept of inversions. We will explore them in the next section.
Inversion in an array is a pair of elements that are wrongly ordered. The pair may be close together or very far apart in the array. For example, take the following array:
Integer[] array = new Integer[]{10, 5, 2, 3, 78, 53, 3};How many inversions does the array have? Let us count:
10>5, 10>2, 10>3, 10<78, 10<53, 10>3
5>2, 5>3, 5<78, 5<53, 5>3
, 2<3, 2<78, 2<53, 2<3
, 3<78, 3<53, 3=3
, 78>53, 78>3
53>3In this listing, every element is compared with the elements following it. There is an inversion when there is a greater-than sign, highlighted by bold characters. Counting the bold ones, we see there are 10 inversions.
For any input array, there is a number of inversions. In a sorted array, the number of inversions would be zero. Now, think about what happens to the number of inversions when a swap is made. A swap interchanges a pair of consecutive elements, thus breaking one inversion (the swap happens only when there is an inversion between consecutive elements). To see this more clearly, consider the following case of a swap between j and j+1 indexes:
…......., j, j+1, …....
Let's take the jth element first. Let it have x number of inversions with the left part of the array. Since these elements are on the left, all inversions of this type are with elements greater than the jth element. When the jth element moves to the (j+1)th position, they still remain to the left, and the only element added to the left of the jth element is the element it is swapped with. Hence, no changes to the number of inversion happens to the jth element, other than the one due to the (j+1)th element. The same logic can be applied to the inversions with it in the right part of the array, and also to both sides of the array for the (j+1)th element. Because of the swap, one inversion is broken between jth and (j+1)th elements. Hence, the number of inversions reduce by exactly one in each inversion. This means the number of swaps in bubble sort would be exactly equal to the number of inversions in the input array, which is finite. And since each scan through the array requires a swap in the previous scan, the total number of scans is at most one more that the number of swaps; this is finite too. This makes sure that the algorithm always finishes.
To understand the complexity of a bubble sort, we have to count the number of steps. Is the number of steps equal to the number of swaps? The answer is, not really. In case of asymptotic analysis, we must always count the step that happens a maximum number of times. In this case, that step is comparison. How many comparisons are there per scan of the array? n-1 of course. So, now the analysis of complexity is reduced to the number of scans we need to sort the array.
Let's see what happens to the maximum element after the first scan. Let's say the maximum element is at the index j. So, it will be compared with the element at j+1. For simplicity, let's assume that all elements are different. Now, since it is the maximum element, the element at the j+1 position will be less than it, and hence it will be swapped. Now the maximum element is at the position, j+1, and is being compared with the element at position, j+2, and the same thing happens. It will continue until the maximum element is at the end of the array. If the elements are not unique, the same will happen to the rightmost maximum element. In the next cycle, the maximum element will already be at the end of the array, and we will hit the second maximum (or another maximum element) somewhere in the array. Now, since one maximum element is at the end of the array, we can think of the rest of the array apart from the last element. In this array, the current maximum is the maximum and it will reach the end of the current part of the array at the end of the current scan.
This shows that at the end of each scan, at least one element reaches the correct final position without altering the correct positions of the ones that got there before the scan, which means that at the end of n scans, all of the elements would be in the correct position and the array would be sorted. That is to say that after at most n scans, the bubble sort would be complete. In each of those scans, there are O(n) operations. So, the worst case complexity of bubble sort is O(n2).
This is not the end of this analysis; we still have to show that there is a case that takes that many steps, and only then can we have a theta bound on the worst case. We take the case where all the elements are sorted in the opposite order, that is, they are in a decreasing order and are all distinct. In such a case, every element has an inversion with all the others. This means that each one of the n elements have an inversion with n-1 other elements, that is, n(n-1) inversions in total. But since each inversion would be counted twice, once from each of the elements that are members of the inversion, it is actually n(n-1)/2. Now, note that the maximum number of swaps that can be done in one scan is n-1, which will happen if every comparison results in a swap because there are n-1 comparisons per scan. So, we will need at least (n(n-1)/2)/(n-1) = n/2 scans to complete all the swaps, each requiring n-1 comparisons. So, the complexity is at least n(n-1)/2 = Ω(n2). Of course then, the worst case is at least this much complex because the worst case is, by definition, the most complex case.
So, the worst case is both O(n2) and Ω(n2), that is to say that it is θ(n2).