In today’s blog I will be briefly going through a “basic” sorting algorithm implementation in Java: bubble sort. Right off the bat I’d like to recommend VisuAlgo to see this algorithm in action. So without further ado…
Bubble sort iterates through a collection of comparable items (usually alphanumeric values) and checks the values two at a time. It looks to see which value is greater and moves the larger value to the larger index.
First we check to see if there are no items in the array and if so we return an empty array. Then we create a boolean ‘isSorted’ to turn on or off whether or not the array has been sorted completely. We declare a variable ‘counter’ and set it equal to 0. We’ll use this later to shorten the length of the array we’re iterating through so that we don’t try to sort elements that have already been sorted. Then we initiate a while loop.
Our while loop will run until our variable ‘isSorted’ returns true. Funnily enough the first step in the while loop is setting ‘isSorted’ to true. We’ll assume that the array is sorted until we find that it isn’t in our forthcoming for loop.
The for loop we create is pretty typical except for our 2nd statement. As I previously mentioned we are going to subtract our counter variable from the number of elements that we’ll iterate through. More on this later.
Inside of the for loop we check to see if the current element is greater than the element to its right. If it is we use a temp variable to hold the value of one of the elements in order to swap their values. One thing you can do is abstract this logic into a separate swap function that takes in two values and the original array. I kept the swap in the for loop to keep things simple in this case. At the end of this conditional we set our ‘isSorted’ variable equal to false so that we know we need to iterate through the array again.
At the end of our while loop we increment our counter. This shows that we have been through the array one time and that we don’t need to sort through the last element because if everything went according to plan it is already sorted. So if we finish the while loop and the ‘isSorted’ variable is equal to false, we start again excluding an element at the end.
After our while loop, return the array.
This solution averages out to O(n²) time complexity since we touch on each element about n² times. The use of the counter variable aims to improve time complexity in some examples. Space complexity is constant with O(1).