Problem
Hint: This question is a follow-up to my Code Review question from 09.01.2017: Class sort with BubbleSort algorithm
After been showed Mergesort and QuickSort as pseudo-code this week in lecture
I had to re-implement my class Sort (which formerly used the BubbleSort algorithm).
So that it now uses QuickSort as the sorting algorithm.
Here’s my code.
I have used the pseudo from the (German Wikipedia article) as an orientation.
I have added comments with the detailed requirements for the mandatory methods.
package algorithm;
/*
Task description:
-----------------
Implement the QuickSort algorithm within the
Java class "algorithm.Sort".
Submit your solution to the JUnit system for
automatic evaluation.
*/
public class Sort
{
// Validate leftIndex and rightIndex concerning being within the
// array range.
public static void quickSort(int[] list, int leftIdx, int rightIdx)
{
if (leftIdx > list.length)
{
throw new IllegalArgumentException("Left index invalid.");
}
if (rightIdx < 0 || rightIdx > list.length)
{
throw new IllegalArgumentException("Right index invalid.");
}
if (leftIdx < rightIdx)
{
int index = divide(list, leftIdx, rightIdx);
quickSort(list, leftIdx, index - 1);
quickSort(list, index + 1, rightIdx);
}
}
public static void quickSort(int[] list)
{
Sort.quickSort(list, 0, list.length - 1);
}
// Choose the last element as the pivot-element.
// Left of the pivot-element have all elements to be smaller then the
// pivot-element. Right of the pivot-element have all elements to be
// equal or greater then the pivot-element.
// Return the position of the pivot-element within the list.
public static int divide(int [] list, int leftIdx, int rightIdx)
{
if (leftIdx < 0 || leftIdx > list.length - 1
|| rightIdx < 0 || rightIdx > list.length - 1)
{
throw new IllegalArgumentException("Left or right index invalid.");
}
int pivotItem = list[rightIdx];
int i = leftIdx;
int j = rightIdx - 1;
do
{
while (list[i] < pivotItem && i < rightIdx)
{
i++;
}
while (list[j] >= pivotItem && j > leftIdx)
{
j--;
}
// As long as leftIdx have not overstep rightIdx ...
if (i < j)
{
int tmp = list[i];
list[i] = list[j];
list[j] = tmp;
}
} while (i < j);
if (list[i] > pivotItem)
{
int tmp = list[i];
list[i] = pivotItem;
list[rightIdx] = tmp;
}
return i;
}
// 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.");
}
// I use the StringBuilder as suggested in answer by mdfst13.
// https://codereview.stackexchange.com/questions/152137/write-a-java-class-sort-which-implements-the-bubblesort-algorithm
// The Array.stream suggestion I haven't understood well enough yet. But
// I keep it in mind for sometime in the future. ;)
StringBuilder ret = new StringBuilder("[ ");
for (int i = start; i <= end; i++)
{
ret.append(list[i]).append(", ");
}
return ret.append(list[end]).append(" ]").toString();
}
// Return the complete array as an appropriate String representation.
public static String toString(int[] list)
{
return Sort.toString(list, 0, list.length - 1);
}
}
My optional test-class which I have used 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.quickSort(test);
out.println("After: " + Sort.toString(test));
/* RESULT :
Before: [ 9, 16, 17, 5, 3, 18, 14, 4, 14, 17 ]
After: [ 3, 4, 5, 9, 14, 14, 16, 17, 17, 18 ]
*/
}
}
It has passed the JUnit tests which the college employees use to evaluate
our code.
But because I’m not convinced of that form of evaluation I would appreciate the
comments and hints of real developer concerning my implementation.
Moreover: There are different implementations of QuickSort in which the Pivot-element is placed in the middle of the array: (leftIndex + rightIndex) / 2
What are the advantages / disadvantages of the two possible implementations?
Therefore: Looking forward to read your answers. 🙂
Solution
Controll access to the recursive called methods by using private or no modifier.
Using private would mean that only from inside the class containing the method it can be called.
So you could add a method like
public static void initQuickSort(int[] list)
{
quickSort(list, 0, list.length - 1);
}
and then add private and remove the throws from quickSort method itself since it does only get accessed by itself so itself controlls the input. If there is a reason the exception should be thrown you have a bug in your code.
private static void quickSort(int[] list, int leftIdx, int rightIdx)
{
if (leftIdx < rightIdx)
{
int index = divide(list, leftIdx, rightIdx);
quickSort(list, leftIdx, index - 1);
quickSort(list, index + 1, rightIdx);
}
}
Also the method call in the quickSort-Method outside your call of course has to be changed to
public static void quickSort(int[] list)
{
Sort.initQuickSort(list);
}
It might be even possible to remove this step now since it does not add anything but might be necessary for the review-test so i will not say to remove but modify it.
Also i’d move the other static methods into your class and protecte them so fewer checks are needed. ASk yourself: what does the outside have to see, which methods need to be accessed from outside?
And make access to the other methods as restricted as possible so they cannot be called from outside with corrupt arguments,
// Validate leftIndex and rightIndex concerning being within the
// array range.
public static void quickSort(int[] list, int leftIdx, int rightIdx)
{
if (leftIdx > list.length)
You missed to check leftIdx being < 0.
if (i < j)
{
// ...
}
} while (i < j);
You have the same condition in the if and in the while statement, maybe a head controlled while would have been the better choice over this tail controlled version.
StringBuilder ret = new StringBuilder("[ ");
for (int i = start; i <= end; i++)
{
ret.append(list[i]).append(", ");
}
return ret.append(list[end]).append(" ]").toString();
This could be replaced by
return Arrays.asList(list).toString();
No loop or stream needed as long as the elements are primitive types or their toString() method suits your needs.
The lesson is: “know your tools!”