Ever wondered how to sort in Java and what it means to select, insert, and bubble? Then we've got you covered in this tech tutorial. Whether you're practicing for a whiteboard coding scenario, or would like to know just for fun, mastering how to sort will definitely come in handy. If you're thinking that this coding technique is going to be very complex, then you'll be pleased to know that there's minimal code involved. These are some of the simplest sorting techniques that you can learn in Java. Without further ado, let’s get started!
Let's start at the beginning of sorting - the selection sort. This type of sort is one of the easiest techniques you'll be able to find and it's also an in-place sorting algorithm. This means that it takes in the array to be sorted, and then sorts it while iterating through it. It uses two loops to perform this operation which makes the complexity of this O(n²). Imagine we have an input array with five elements: 5, 3, 7, 8, 1. To perform selection sort on this array we follow the steps below:
Start a loop to iterate through each of the elements in the array. This loop runs from the first element to the (n-1)th element, where n is the size of the array. In this loop, we'll initialise an integer and call it min. This will be the variable to hold the minimum value in each iteration.
Now we start another for loop, which starts iterating from the (i+1)th element all the way to the end of the array. This loop compares if the current element in the loop is lesser than the minimum value that we set outside this loop.
After iterating over the entire loop, we get the minimum element. This is swapped with the first element once the loop breaks.
Now, the outer loop starts its next iteration and this goes on until the second last element of the array. With each iteration, we find the minimum value in that iteration, and the array is sorted.
In our example, 5 will be set as min in the first iteration of the outer loop. Then each element of the array is compared with 5 in the inner loop. After the end of the inner loop, 1 will be the minimum element and it will be swapped with 5. This is then repeated for n-1 times until the entire array is sorted.
So you've mastered the selection sort....what next?
Great, you should be feeling quite confident about the selection sort. So let's try the insertion sort. This is another algorithm with a time complexity of O(n²). This is because of the two loops that are used to perform the sorting in insertion. Insertion sort and selection sort have the same time complexity but studies have found out that the former performs better than the latter when it comes to large lists. (But we'll let you in on a little secret – none of these sorting techniques are actually used for sorting large lists because of the square time complexity. For those, we will be using other sorting techniques like quick, heap, or merge sort. Don't worry about these for now...but look out for another tutorial on these!)
Insertion sort is also an in-place sorting algorithm. It starts the outer loop from the second element and the inner loop from the current i index to 0.
The inner loop compares the current value with the previous value and swaps them if the current value is lesser than the previous value.
After one iteration of the inner loop, we get the first element sorted in its correct position. Then we increment i by 1, and then the j loop will proceed as usual from the i index to 0, comparing each element with the previous elements and swapping where needed.
Lastly, we have the bubble sort – one of our favourites, and we're not just saying this because of the name. This is the easiest algorithm to learn because the code is so straightforward and the logic is very simple. This has a time complexity of O(n²) because of the two for loops used to perform the sorting operation. Just like how it is the easiest among the three sorting algorithms we’ve seen today, it is also the worst in terms of performance when it comes to sorting large lists.
The outer loop iterates from the first element up to the last element. The inner loop starts from the first element and goes all the way up to the (n-i-1)th element. This is because with each iteration of the bubble sort, the largest element moves to its sorted position at the end of the array and we will only have to iterate one element less with each iteration.
The inner loop compares the current element and checks if it is greater than the next element. If it is, it swaps the element.
This is done repeatedly inside the inner loop and at the end, the largest element will be at the end index.
We repeat this process by incrementing the outer loop by 1 and then using the inner loop to iterate from the beginning to (n-i-1).
Like we mentioned before, even though each of these sorting algorithms has the same time complexity of O(n²) they perform differently depending on the size of the list and the system in use. Insertion sort usually performs only half as many as operations compared to selection sort according to experiments. Insertion sort is also faster than selection sort in arrays that are close to sorted.
Selection sort is preferred whenever the write operations are more expensive than the read operations. This is because selection sort does O(n) swaps in the average and worst-case whereas insertion sort performs O(n²) swaps. Both of these sorting techniques are extremely fast when the number of elements to be sorted is less, usually less than 20. Anything more than that would require other algorithms, which we would look into later. That’s all for today, happy coding!
Like what you've read or want more like this? Let us know! Email us here or DM us: Twitter, LinkedIn, Facebook, we'd love to hear from you.