It is Thursday morning in the Twin Cities of Minneapolis and St. Paul. The weather forecast called for a winter storm that should have started around 03:00 AM CST. When I got up around 05:00 AM it was pitch dark and no storm yet. I did check later when it started clearing up and no signs of the storm yet. I find it interesting that different weather services make forecasts by the hour which include temperature, humidity, precipitation, and wind direction to list a few. I understand weather forecasting is not accurate but …
As I mentioned in a previous post, I am watching the video Advanced Data Structures and Algorithms in Java 9 by Debasish Ray Chawdhuri produced by Packt and published by O’Reilly. That was a mouthful. I just felt to refresh my understanding on a few algorithms.
Like most software engineers, once upon a time while in school, I studied and had to implement the algorithm for a couple classes. Since then, when at work, I tend to use sorting implementations that come in libraries. That said, if there is a performance issue, or the need to enhance an algorithm, they it is justifiable to implement your own version.
To be honest with you, I have done and do a lot of development work using C / C++ and I have used the quicksort implementation that comes in standard libraries. In specific I have used the function qsort that comes standard in the cstdlib of C and C++ in multiple projects and products. I have yet not encountered a situation in which I had to implement a faster implementation of such algorithm.
That said; it is very useful to understand how sorting algorithms are implemented and pay attention at the time and space complexity of the algorithms when you need to perform an educated selection in a software development project.
:::: :::: ::::
// **** sort the array of full paths ****
qsort( *sortedArray,
countOfFiles,
lengthOfEntry,
strcmp);
:::: :::: ::::
This code snippet is one of several in a storage server product that runs in the cloud.
main <<< arr.length: 19 main <<< arr: [10, 5, 2, 3, 78, 53, 3, 1, 1, 24, 1, 35, 35, 2, 67, 4, 33, 30, 13] quicksort <<< count: 99 main <<< arr: [1, 1, 1, 2, 2, 3, 3, 4, 5, 10, 13, 24, 30, 33, 35, 35, 53, 67, 78]
I will show a single example running the Java implementation of the algorithm on a Windows 10 machine which I developed using the VSCode IDE.
The content of the input array that provides the integers we will be sorting has been hardcoded. I could have added a mechanism to read the values from the console and perhaps make a copy in the file system that we could reuse. As we will see shortly, in this post, we want to run the same data set with different options to better understand what is going with the algorithm and offer some optimizations.
Our test scaffolding displays the length of the Integer[] followed by the actual contents of the arr[]. In this case we seem to have 19 integers and they are presented in no specific order.
We then ran our quicksort algorithm. The algorithm seems to display a count. We should be counting some operation which hopefully will indicate how the algorithm is performing. Finally we display the contents of the sorted array. The value 99 should be used for comparison purposes between passes only. In our case we are interested how the algorithm performs when the same data is ordered in different ways.
/**
* Test scafolding
*/
public static void main(String[] args) {
// **** array to sort ****
Integer[] arr = new Integer[] {10, 5, 2, 3, 78, 53, 3, 1, 1, 24,
1, 35, 35, 2, 67, 4, 33, 30, 13};
// ???? array info ????
System.out.println("main <<< arr.length: " + arr.length);
System.out.println("main <<< arr: " + Arrays.toString(arr));
// ???? sort array (swap a and b to change order) ????
// Arrays.sort(arr, (a,b) -> b - a );
// System.out.println("main <<< arr: " + Arrays.toString(arr));
// ???? shuffle array ????
// List<Integer> lst = Arrays.asList(arr);
// Collections.shuffle(lst);
// arr = lst.toArray(new Integer[lst.size()]);
// System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** sort array ****
quicksort(arr, (a, b) -> a - b);
// **** display sorted array ****
System.out.println("main <<< arr: " + Arrays.toString(arr));
}
We declare arr[] and populate it with 19 values following no specific order. Some values are repeated.
Our test program displays the count of elements and the contents of the actual array.
Two sets of lines of code follow. We have seen the results of shown such lines in operation.
We then call the quicksort entry point. It has two arguments. The first is the array of integers and the second a comparator. The comparator is used to allow the algorithm to sort two values each time the need arises.
Finally we display the resulting (hopefully sorted) array of integers.
/**
* Utility function.
* Swaps two entries in the array.
*/
private 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;
}
Most sorting algorithms tend to move data in the same or between data structures. In our case we will be sorting the data in place. We do not require additional space. This utility function is used to swap two values in the array. Note that the contents of the array could be different data types or objects. Of course the comparator passed to the quicksort function / method would have to be adjusted to the specific class of object. In our case we use Integers.
/**
* Entry point for recursive call.
*/
public static <E> void quicksort(E[] array, Comparator<E> comparator) {
// **** reset counter ****
count = 0;
// **** recursive call ****
quicksort(array, 0, array.length, comparator);
// **** display counter ****
System.out.println("quicksort <<< count: " + count);
}
This is the entry point for the quicksort algorithm. Note that we initialize and later display the value of a counter. In addition we need to pass the start and end values in the array for each pass of the recursive call which we will be looking at it next.
/**
* Recursive call
*
* Time complexity:
* Best: (n log(n)) Average: Θ(n log(n)) Worst: O(n^2)
*
* Space complexity:
* O(log(n))
*/
private static <E> void quicksort(E[] array, int start, int end, Comparator<E> comparator) {
// ???? ????
// System.out.println("quicksort <<< start: " + start + " end: " + end);
// **** end condition ****
if (end - start <= 0)
return;
// **** choose a random pivot (optimization technique) ****
// int pivotIndex = (int)((end - start) * Math.random()) + start;
// swap(array, pivotIndex, end - 1);
// **** initialization ****
int i = start;
int j = end - 1;
boolean movingI = true;
// **** sort ****
while (i < j) {
// **** count this operation ****
count++;
// **** ****
if (comparator.compare(array[i], array[j]) > 0) {
swap(array, i, j);
movingI = !movingI;
} else {
if (movingI) {
i++;
} else {
j--;
}
}
}
// **** recursion ****
quicksort(array, start, i, comparator);
quicksort(array, i + 1, end, comparator);
}
This is the recursive quicksort method. We start by defining our base case.
The next two lines have been commented out. We will talk about them later. They implement an optimization step.
The initialization sets three variables. They are used to traverse elements in the array. We will be pivoting from right to left so the variable movingI will be used to signal if we are pivoting on the variable ‘I’ or ‘j’.
The loop is used to swap array entries. The idea is to move all smaller variables from a pivoting point to the other side.
After each pass we repeat the operation with the left and right sides of the array. We are using a divide and conquer approach.
At this time I suggest spending some time reading the description of the quicksort algorithm in Wikipedia, watching the animated visualization and following the code we have in this post.
Once you are fine with the code, enable the optimization. Run the code and observe the results. My suggestion is to leave the optimization enabled.
After that, see if you have some time to spend experimenting by sorting the input array in ascending and descending orders. The count value will change. You can also experiment changing the values in the array and changing the size of the array.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all 5,825 subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com