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. :)