It has been a few weeks since my last post. I apologize for this. Will let you know after my current quest is completed. Hopefully everything will turn out as I desire.
In the meantime I have been taking a few on-line courses.
I am almost done with the course C++20 Fundamentals by Paul J. Deitel. The course was released July, 2021 and published by Pearson3. The ISBN: 013687518. This online course is made available through O’Reilly. I am a member of the Association of Computing Machinery and have access to several O’Reilly titles.
There is an associated book which is still being produced. The title is C++20 for Programmers: An Object’s-Natural Approach (Deitel Developer Series) 3rd Edition by Paul Deitel.
I placed my order on Amazon on December 6, 2021. I just checked the status of the delivery. Not yet shipped. We will email you when we have an estimated delivery date.
Last I heard it was going to be released in March, 2022. Today is the 28th of the month so it can still arrive on time.
I am also taking a set of seven on-line courses for “C Programming with Linux Professional Certificate” on edX | Dartmouth College, IMT. So far I have completed three of them. If interested, you can see the certificates on my LinkedIn profile. Currently working on the fourth course which I hope to complete later this week.
I also want to thank all 12’314 subscribers to this blog.
A day or so ago I was looking at my blog and noticed that it did not have a blog related to Bubble Sort so I decided to generate this post.
We will implement and test the Bubble Sort function using the Java programming language and the VSCode IDE on a Windows 11 computer.
Given an array of integers (could be any other type or class), we need to sort the elements in ascending or descending order.
7, 2, 19, -3, 17 main <<< arr: [7, 2, 19, -3, 17] main <<< ascending: [-3, 2, 7, 17, 19] main <<< arr: [7, 2, 19, -3, 17] main <<< descending: [19, 17, 7, 2, -3] 7, 2, 19, -3, 17, 9, -8, 3, -1, 5 main <<< arr: [7, 2, 19, -3, 17, 9, -8, 3, -1, 5] main <<< ascending: [-8, -3, -1, 2, 3, 5, 7, 9, 17, 19] main <<< arr: [7, 2, 19, -3, 17, 9, -8, 3, -1, 5] main <<< descending: [19, 17, 9, 7, 5, 3, 2, -1, -3, -8]
We have two test cases. The test cases are separated by two blank lines.
The first line in the test case is the input line. It contains a set of unordered integers.
Our test scaffold seems to allocate an int[] array and load the input values. The contents of the array are then displayed in order to verify that all is well before calling the implementation of the Bubble Sort algorithm.
It seems that the test code makes a call to the function of interest indicating that the values should be sorted in ascending order. The returned array is displayed.
The test scaffold then displays the initial array. This is done to verify that the next call to the function of interest will use the values in the original order.
The test scaffold calls the function of interest indicating that the values of the array are sorted in descending order. After the call to the function of interest completes, the returned array is displayed.
/**
* Test scaffold.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read array of integers ****
int[] arr = Arrays.stream(br.readLine().trim().split(","))
.map(x -> x.trim())
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? display array ????
System.out.println("main <<< arr: " + Arrays.toString(arr));
// **** sort array using bubble sort ****
int[] sorted = bubbleSort(arr, ASC_ORDER);
// ???? display sorted array ????
System.out.println("main <<< ascending: " + Arrays.toString(sorted));
// **** sort array using bubble sort ****
sorted = bubbleSort(arr, DES_ORDER);
// ???? display sorted array ????
System.out.println("main <<< descending: " + Arrays.toString(sorted));
}
The test scaffold starts by reading the input line and declaring and populating the int[] array arr. The contents of the array are displayed to verify that all is well so far.
The function of interest is invoked to sort the array in ascending order. The resulting array is displayed.
The function of interest is called a second time but the second argument indicates to sort the array in descending order. The resulting array is displayed.
/**
* Sort the array using Bubble Sort.
*
* Execution: O(n^2) Space: O(1)
*
* @param args
* @throws IOException
*/
static int[] bubbleSort(int[] arr, int sortOrder) {
// **** sanity check(s) ****
if (arr == null) return null;
int n = arr.length;
if (n <= 1) return arr;
// **** initialization ****
int[] sorted = arr.clone();
// **** ****
for (var i = 0; i < n - 1; i++) {
// **** ****
for (var j = 0; j < n - i - 1; j++) {
// **** swap values in ascending order ****
if (sortOrder == ASC_ORDER && sorted[j] > sorted[j + 1]) {
sorted = swapAdjacent(sorted, j);
}
// **** swap values in descending order ****
else if (sortOrder == DES_ORDER && sorted[j] < sorted[j + 1]) {
sorted = swapAdjacent(sorted, j);
}
}
}
// **** return sorted array ****
return sorted;
}
The function of interest starts by performing some sanity checks.
The initialization step is not part of the algorithm. I decided to clone the input array so the order of the values would be preserved; otherwise the ordering would be different in the second invocation of the function of interest. I should have cloned the array in the main() function, not here.
We need to take the first entry in the array and compare it to the second. Depending on the sorting order, we need to swap them in order to bubble the highest or lowest value up (right) depending if the sorting order is ascending or descending respectively.
Take a moment and verify what happens to the first two entries in the array. The inner loop will bubble the lowest or highest entry to the right of the array. As the process repeats the values will end up in sorted values on the right side of the array. When done all array values will be sorted.
/**
* Swap adjacent elements in array index i and i + 1.
* Auxiliary function.
*/
private static int[] swapAdjacent(int[] arr, int i) {
// **** swap elements ****
int tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
// **** return swapped array ****
return arr;
}
This auxiliary function is used to swap the two adjacent entries specified by `i` and `i + 1` in the specified array. The updated array is returned to the caller.
// **** define sort order ****
static final int ASC_ORDER = 0;
static final int DES_ORDER = 1;
These lines declare the sorting order that needs to be specified to the function of interest.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named BubbleSort.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge, and enhance your developer / engineering toolset.
Thanks for reading this post and feel free to connect with me John Canessa on LinkedIn.
Enjoy;
John