Sorting is one of the basic operations that we perform on objects. Even in childhood, children are taught to sort as they develop their thinking skills. Computers and software are no exception. There are a huge variety of sorting algorithms in Java. I suggest that you check out what they are and how they work. What if you're asked about one of them at an interview someday?
Introduction
Sorting elements is one of the categories of algorithms that a developer must know. If computer science was once not taken seriously when I was in school, today's students must be able to implement and understand sorting algorithms.
Basic algorithms, the simplest, are implemented using a for loop.
Naturally, to sort a collection of elements, such as an array, you need to somehow go through the collection. For example:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
What can be said about this segment of code?
We have a loop in which we change the index (int i) from 0 to the last element in the array. In fact, we're simply taking each element in the array and printing its contents. The more elements in the array, the longer the code will take to finish.
That is, if n is the number of elements, when n = 10 the program will take twice as long to run than when n = 5. If our program has a single loop, the execution time grows linearly: the more elements there are, the longer the execution time. It turns out that the algorithm above works in linear time (a linear function of n). In such cases, we say that the algorithm's complexity is "O(n)". This notation is also called "big O" or "asymptotic behavior". But you can just remember "algorithm's complexity".
The simplest sorting algorithm (bubble sort)
Suppose we have an array and we can iterate through it. Great. Now let's try to sort it in ascending order. What does this mean? It means that given two elements (for example, a = 6, b = 5), we must rearrange a and b if a is greater than b (if a > b).
What does this mean when we're using an index to work with a collection (as is the case with an array)? It means that if the element with index a is larger than the element with index b (array[a] > array[b]), then the elements must be swapped.
There are different ways to change places. But we'll use a technique that is simple, understandable and easy to remember:
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
Now we can write the following:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
As you can see, the elements really were swapped. We started with index 1, because if the array has just one element, the expression array[i] < array[i-1] is invalid for index 0. Doing this also protects us from cases where the array has no elements or only one element, and it makes the code look better.
But the resulting array is still not sorted, because one pass isn't enough to do the sorting. We'll have to add another loop in which we will perform passes again and again until we get a sorted array:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
So we finished our first sorting algorithm. We repeat the outer loop (while) until we decide that no more iterations are needed. By default, before each new iteration, we assume that our array is sorted and we don't need to loop anymore. Accordingly, we move sequentially through the elements and check this assumption. But if the elements are not in order, then we swap elements and understand that we now have no guarantee that the elements are in the correct order. This means that we need to perform another iteration. For example, suppose we have [3, 5, 2]. 5 is more than 3 — all is well. But 2 is less than 5. However, [3, 2, 5] requires another pass, since 3 > 2 and they need to be swapped.
Because we are using a loop within a loop, the complexity of our algorithm increases. Given n elements, it becomes n * n, that is, O(n^2). This is called quadratic complexity. In general, we can't know exactly how many iterations will be needed. The expression of complexity of an algorithm shows how the complexity increases in the worst case. That is, it indicates how much the execution time will increase as the number of elements n changes.
Bubble sort is one of the simplest and most inefficient sorting algorithms. It is also sometimes called "stupid sort". Material on this topic:
Another sorting algorithm is selection sort. It also has quadratic complexity, but more on that later. So the idea is simple. On each pass, we select the smallest element and shift it to the beginning. Additionally, each pass starts one step to the right. In other words, the first pass starts from the zeroth element, the second pass from the first, etc. It will look like this:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
This sort is unstable, because identical elements (in terms of whatever characteristic we are using to sort the elements) can change their relative positions. There's a good example is in the Wikipedia article on selection sort.
Material on this topic:
Insertion sort also has quadratic complexity, since we again have a loop within a loop. What makes insertion sort different? This sorting algorithm is "stable." This means that identical elements will not change their relative order. Again, we mean identical in terms of the characteristics we are sorting by.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
Shuttle sort
There is another simple sorting algorithm: shuttle sort. This is also known as a bidirectional bubble sort or the cocktail shaker sort. These alternate names tell us that the shuttle sort isn't about the space shuttle. It's about something that moves back and forth. Now you can think of that when you think of this algorithm.
What's the essence of the algorithm? The essence of the algorithm is that we iterate from left to right, swapping elements and checking whether any of the elements remaining in the other direction need to be swapped.
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
Another simple sorting algorithm is shell sort. The gist of it is similar to bubble sort, but in each iteration we have a different gap between the compared elements. It is cut in half with each iteration. Here's an implementation:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
In addition to these simple sorting algorithms, there are also more complicated sorting algorithms. For example, merge sort. There are two things to note. First, recursion comes to our rescue here. Second, the algorithm's complexity is no longer quadratic, as we are used to. This algorithm's complexity is logarithmic. This is written as O(n log n).
So let's implement it.
First, we'll write a recursive call to the sort method:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
Now, let's add the main action to our implementation. Here's our super method:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
We can run our example by calling mergeSort(array, 0, array.length-1). As you can see, the process boils down to accepting an input array along with indications of the beginning and end of the section that needs to be sorted. When the sorting begins, these are the beginning and end of the array. Then we calculate the delimiter, which is the index where we will split the array.
If the array can be divided into 2 parts, then we call the sort method recursively for the two halves of the array. We prepare an auxiliary buffer where we'll insert the sorted section. Next, set the index at the beginning of the section to be sorted and start walking through each element of the empty buffer, filling it with the smallest elements. If the element pointed to by the index is less than the element pointed to by the delimiter, we put the element in the buffer and shift the index.
Otherwise, we place the element pointed to by the delimiter into the buffer and shift the delimiter. As soon as the delimiter goes beyond the boundaries of the section being sorted or we fill the entire array, the specified range is considered sorted. Material on this topic:
Another interesting sorting algorithm is counting sort. The algorithmic complexity here is O(n+k), where n is the number of elements and k is the maximum value of an element. This algorithm does have one shortcoming: we need to know the minimum and maximum values in the array.
Here is an example of the counting sort:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
You can understand that it's very inconvenient when we need to know in advance the minimum and maximum values. And we've got another algorithm here: radix sort. I'll only present the algorithm here visually. See the supplementary materials for the implementation:
Materials:
Well, it's time for dessert — quick sort, one of the most famous sorting algorithms. It has logarithmic complexity: O(n log n).
This sorting algorithm was developed by Tony Hoare. Interestingly, he invented it while living in the Soviet Union, where he studied machine translation at Moscow University and developed a Russian-English phrase book. What's more, Java uses a more complex version of this algorithm in Arrays.sort. What about Collections.sort? Why not take a look at how things are sorted "under the hood"?
Here's the code:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
This is all very scary stuff, so let's dig into it.
For input array (int[] source), we create two markers: left (L) and right (R). During the first method call, they correspond to the beginning and end of the array.
Then we identify the pivot element, which is aptly named pivot. After this, our task is to move values smaller than pivot to the left of pivot, and larger ones — to the right.
To do this, we first move the L marker until we find a value greater than pivot. If no smaller value is found, then L becomes equal to pivot.
Then we move the R marker until we find a value smaller than pivot. If no larger value is found, then R becomes equal to pivot.
Next, if the L marker is before the R marker or coincides with it, then we try to swap the elements if the L element is less than the R element.
Then we shift L to the right by 1, and we shift R to the left by 1.
When the L marker moves beyond the R marker, it means the swapping is complete: smaller values are to the left of pivot, larger values are to the right of pivot.
After this, we call the same sort method recursively on the subarrays — from the beginning of the section to be sorted to the right marker, and from the left marker to the end of the section to be sorted.
Why from the beginning to the right marker? Because at the end of an iteration, it turns out that the right marker moves enough to become the boundary of the left part.
This algorithm is more complex than simple sorting, so it's best to sketch it. Take a white sheet of paper and write: 4 2 6 7 3. Then write pivot in the middle, i.e. under number 6. Circle it.
Under 4, write L, and under 3, write R. 4 less than 6, 2 less than 6. We end up moving L to the pivot position, because L can't move past pivot, according to the condition.
Write again 4 2 6 7 3. Circle 6 (pivot) and put L underneath it. Now move the R marker.
3 is less than 6, so put the R marker on 3. Since 3 is less than 6 (pivot), we perform a swap.
Write the result: 4 2 3 7 6. Circle 6, because it is still the pivot.
The L marker is on 3. The R marker is on 6. Remember that we move the markers until L moves beyond R. Move L to the next number.
Here I'd like to explore two possibilities: 1) the case where the penultimate number is 7 and 2) the case where it is 1, not 7.
If the penultimate number is 1: Move the L marker to 1, because we can move L as long as the L marker points to a number smaller than pivot. But we can't move R off of 6, because we can only move R if the R marker points to a number that is greater than pivot. We don't perform a swap, because 1 is less than 6. Write the current situation: 4 2 3 1 6. Circle 6 (pivot). L shifts by pivot and stops moving. R doesn't move. We don't perform a swap. Shift L and R by one position. Write the R marker under 1. The L marker is out of bounds. Because L is out of bounds, we do nothing. But, we write 4 2 3 1 again, because this is our left side, which is less than pivot (6). Select the new pivot and start everything again :)
If the penultimate number is 7: Move the L marker to 7. We can't move the right marker, because it is already pointing at the pivot. 7 is greater than pivot, so we perform a swap. Write the result: 4 2 3 6 7. Circle 6, because it is the pivot. The L marker is now shifted to 7, and the R marker is shifted to 3. It doesn't make sense to sort the part from L to the end, because there's only 1 element. However, we send the part from 4 to the R marker for sorting. We choose a pivot and start all over again :)
At first glance, it may seem that if you add a lot of values equal to pivot, then you will break the algorithm. But this isn't the case. You can think up tricky combinations and on paper convince yourself that everything is correct and marvel that such simple actions implement such a reliable sorting mechanism. The only downside is that this sorting algorithm is not stable. Because a swap may change the relative order of identical elements if one of them is encountered before pivot before the other element is swapped into the part before pivot.
The bottom line
Above, we looked at a "gentleman's" set of sorting algorithms implemented in Java. Algorithms are generally useful, both from an applied perspective and in terms of learning how to think. Some are simpler, some are more complicated. Smart people defended their dissertations for some. For others, they wrote super thick books.
I hope the supplementary materials will help you learn even more, since this article is just an overview that has already turned out to be weighty. And its purpose is to provide a small introduction. You can also find an introduction to algorithms if you read "Grokking Algorithms".
I also like the playlist from Jack Brown: AQA Decision 1 1.01 Tracing an Algorithm.
For fun, you can see algorithm visualizations at sorting.at and visualgo.net.
GO TO FULL VERSION