Write a Java class "Sort" which implements the BubbleSort algorithm

Question

For a further education I had to do the following task:

Implement the BubbleSort algorithm within the Java class algorithm.Sort.

Submit your solution to the JUnit system for automatic evaluation.

Here the source code of my Sort class. The requirements concerning the single methods I've added as comments.

package algorithm;
public class Sort
{
 /*
 Sort the complete field in ascending order.
 */ 
 public static void bubbleSort(int[] list)
 {
 Sort.bubbleSort(list, 0, list.length - 1);
 }
 /*
 Sort the field ascending from leftIndex to rightIndex.
 Implement the BubbleSort algorithm.
 One has to specify a lower and an upper index.
 These range of the array is then sorted by BubbleSort.
 The lower and the upper index have to be checked for validity.
 */
 public static void bubbleSort(int[] list, int leftIdx, int rightIdx)
 throws IllegalArgumentException
 {
 if (leftIdx < 0 || leftIdx > list.length - 1 
 || rightIdx < 0 || rightIdx > list.length - 1) 
 {
 throw new IllegalArgumentException("Left or right index invalid.");
 }
 for (int i = list.length; i > 1; i--) 
 { 
 for (int j = leftIdx; j < rightIdx; j++) 
 { 
 if (list[j] > list[j + 1]) 
 {
 int tmp = list[j];
 list[j] = list[j + 1];
 list[j + 1] = tmp;
 } 
 }
 }
 }
 // The largest element within the specified array-range
 // has to be moved to position i.
 // Basically just the inner loop of BubbleSort.
 // Parameter validity checks required.
 public static void bubbleUp(int[] list, int leftIdx, int i)
 {
 if (leftIdx < 0 || leftIdx > list.length - 1 
 || i < 0 || i > list.length - 1) 
 {
 throw new IllegalArgumentException("Left or right index invalid.");
 }
 while (leftIdx < i) 
 { 
 if (list[leftIdx] > list[leftIdx + 1]) 
 {
 int tmp = list[leftIdx];
 list[leftIdx] = list[leftIdx + 1];
 list[leftIdx + 1] = tmp;
 }
 leftIdx++;
 }
 }
 // Convert the array to a appropriate String representation!
 // Parameter validity checks required.
 public static String toString(int[] list, int start, int end)
 {
 if (start < 0 || start > list.length - 1 
 || end < 0 || end > list.length - 1
 || start > end) 
 {
 throw new IllegalArgumentException("Left or right index invalid.");
 }
 String ret = "";
 for (int i = start; i <= end; i++) 
 {
 ret += list[i] + ", ";
 }
 return "[ " + ret.substring(0, ret.length() - 2) + " ]";
 }
 // Return the complete array as an appropriate String representation.
 public static String toString(int[] list)
 {
 return Sort.toString(list, 0, list.length - 1);
 }
}

Here's the Java class which I've made for myself, so I could test my code while developing:

package test;
import algorithm.Sort;
import static java.lang.System.out;
public class SortTest
{
 public static void main(String[] args)
 {
 int[] test = { 9, 16, 17, 5, 3, 18, 14, 4, 14, 17 };
 out.println("Before: " + Sort.toString(test) + "\n");
 Sort.bubbleSort(test);
 out.println("After: " + Sort.toString(test));
 /* RESULT :
 Before: [ 9, 16, 17, 5, 3, 18, 14, 4, 14, 17 ]
 After: [ 5, 3, 4, 9, 14, 14, 16, 17, 17, 18 ] 
 */
 } 
}

My class passed the automated tests, so it might be correct formally. I would appreciate comments and critiques from other developers.

Answer 1

No unnecessary math

 if (leftIdx < 0 || leftIdx > list.length - 1 
 || rightIdx < 0 || rightIdx > list.length - 1) 

You could simplify this to

 if (leftIdx < 0 || leftIdx >= list.length 
 || rightIdx < 0 || rightIdx >= list.length) 

Because if either Idx is equal to list.length, it is greater than list.length - 1.

Don't do extra work

 for (int i = list.length; i > 1; i--) 
 { 
 for (int j = leftIdx; j < rightIdx; j++) 

You're doing more passes than necessary.

 for (int i = rightIdx; i > leftIdx; i--) 
 { 
 for (int j = leftIdx; j < i; j++) 

This works by bubbling the largest element to the end. Once that's done, we don't have to review the end again. So we can decrease i, which points to the end.

Bubble Sort best case

 for (int i = list.length; i > 1; i--) 
 { 
 for (int j = leftIdx; j < rightIdx; j++) 
 { 
 if (list[j] > list[j + 1]) 
 {
 int tmp = list[j];
 list[j] = list[j + 1];
 list[j + 1] = tmp;
 } 
 }
 }

One of the advantages of bubble sort is that it is possible to get a best case of linear time. However, this code doesn't do that. It's always quadratic, regardless of whether the data is already sorted.

Consider

 for (int i = rightIdx; i > leftIdx; i--) 
 {
 Integer tmp = null;
 for (int j = leftIdx; j < i; j++) 
 { 
 if (list[j] > list[j + 1]) 
 {
 tmp = list[j];
 list[j] = list[j + 1];
 list[j + 1] = tmp;
 } 
 }
 if (tmp == null)
 {
 break;
 }
 }

Now if we never swap, then tmp is null and we stop processing. If the list is sorted, that happens on the first outer iteration and we only go through the list once. If the code is almost sorted but not quite, it could happen after just a few iterations.

If you add data at the end a lot, note that reversing the sort so that it bubbles the smallest forward rather than the largest back would help.

StringBuilder

 String ret = "";
 for (int i = start; i <= end; i++) 
 {
 ret += list[i] + ", ";
 }
 return "[ " + ret.substring(0, ret.length() - 2) + " ]";

This should use a StringBuilder instead of string concatenation.

 String Builder ret = new StringBuilder("[ ");
 for (int i = start; i < end; i++) 
 {
 ret.append(list[i]).append(", ");
 }
 ret.append(list[end]).append(" ]");
 return ret.toString();

Now rather than creating new strings each time, it just expands the StringBuilder as needed.

I also changed it so that the substring call is unnecessary. Since we're manually iterating anyway, we can just not do the last element inside the loop. That way we can handle it separately outside.

The substring trick makes more sense when we're automating the iteration such that we can't control the bounds. But that's not the case here.

Answer 2

In addition to the other parts of mdfst13s answer, note that standard functions like converting things to strings hardly need to be implemented manually anymore. Instead of using a StringBuilder and manual looping, you can simply stream your ints into a joining collector:

retrun Arrays.stream(list, start, end + 1)
 .mapToObj(Integer::toString)
 .collect(Collectors.joining(", ", "[ ", " ]"));