The Salesforce ecosystem always seems to have a higher number of self taught developers than other industries. I, certainly, count myself among them. It was not too many years ago that I could not have told you the difference between Java and HTML. As my own developer career has grown I have realized that two of the common concerns with self taught or boot camp grads is their lack of understanding of core computer science principles. Particularly, algorithms and data structures and how to evaluate them. I know I wrote more than my share of nested for loops before I realized that they didn’t scale too well and have a way of blowing up your CPU governor limits at the worst time.
In my own studies I realized that there is a lack of examples of some of these classic CS concepts implemented in Apex. I wanted to give back by creating a GitHub repository of classic sort and search algorithms and blogging about some of them.
Bubble Sort In Apex
Bubble sort seems to be one of the first sorting algorithms that is taught. Typically as an example of of algorithm that scales poorly. The nested for loop means that sorting 10 items will take 100 operations, 100 items will take 1000 operations and so on. If you are starting your journey as a developer it is worth taking some time to understand time complexity and Big-O notation.
Lets talk about the code. If we look at the class BubbleSort in the image above we we can see it has two methods Sort and Swap. The Sort method accepts a list of integers and then create a basic for loop. We set the index of the loop to the last value in our collection. This is our unsorted partition of our collection. The loop will continue as long as the value of the unsortedIndex variable is greater than 0 and will decrement by 1 each time go through the loop. A list of 10 integers would result create an unsortedIndex of 9.
We then set up an inner for loop. The index starts at 0 and will loop as long as the value is less than that of the unsortedIndex in the parent loop. (This is a slightly optimized bubble sort) The inner loop then compares each value in the array. If the element at position i is greater than the element at position i+1 we call our Swap method and change their place in the array. This results in the largest element in the loop “bubbling” up to the end of the collection.
The image below is an example of bubble sort being called on a simple 5 integer list. On the right you can see the debug log to help you follow the logic of the algorithm. We can see that in our first traversal through the inner loop that 78 is greater than 4 and their positions are swapped. 78 is greater than 22 and so forth until 78 bubbles up to the end of the array. We now know that the largest value is in the last position of our array. We can reduce the size of our unsorted partition by 1 and and examine the remaining 4 values.
I hope that this is a useful post to new developers and illustrates the issues with nested for loops and large data volumes.
SFDC Vets 