I need help with this Java Data Structures Assignment. Thanks QuickSort Class -
ID: 3836632 • Letter: I
Question
I need help with this Java Data Structures Assignment. Thanks
QuickSort Class - You will write the QuickSort.java class which will implement the Sort Interface using the Quick Sort algorithm.
Sort Interface Method
public interface SortInterface<T extends Comparable <? super T>> {
public void sort(T[] arrayToSort);
}
Explanation / Answer
import java.util.Arrays;
public class QuickSort<T extends Comparable <? super T>> implements SortInterface<T>{
/**
* Swaps to elements in an array. Used by various sorting algorithms.
*
* @param data the array in which the elements are swapped
* @param index1 the index of the first element to be swapped
* @param index2 the index of the second element to be swapped
*/
private void swap(T[] data, int index1, int index2)
{
T temp = data[index1];
data[index1] = data[index2];
data[index2] = temp;
}
/**
* Sorts the specified array of objects using the quick sort algorithm.
*
* @param data the array to be sorted
*/
@Override
public void sort(T[] arrayToSort)
{
quickSort(arrayToSort, 0, arrayToSort.length - 1);
}
/**
* Recursively sorts a range of objects in the specified array using the
* quick sort algorithm.
*
* @param data the array to be sorted
* @param min the minimum index in the range to be sorted
* @param max the maximum index in the range to be sorted
*/
private void quickSort(T[] data, int min, int max)
{
if (min < max)
{
// create partitions
int indexofpartition = partition(data, min, max);
// sort the left partition (lower values)
quickSort(data, min, indexofpartition - 1);
// sort the right partition (higher values)
quickSort(data, indexofpartition + 1, max);
}
}
/**
* Used by the quick sort algorithm to find the partition.
*
* @param data the array to be sorted
* @param min the minimum index in the range to be sorted
* @param max the maximum index in the range to be sorted
*/
private int partition(T[] data, int min, int max)
{
T partitionelement;
int left, right;
int middle = (min + max) / 2;
// use the middle data value as the partition element
partitionelement = data[middle];
// move it out of the way for now
swap(data, middle, min);
left = min;
right = max;
while (left < right)
{
// search for an element that is > the partition element
while (left < right && data[left].compareTo(partitionelement) <= 0)
left++;
// search for an element that is < the partition element
while (data[right].compareTo(partitionelement) > 0)
right--;
// swap the elements
if (left < right)
swap(data, left, right);
}
// move the partition element into place
swap(data, min, right);
return right;
}
public static void main(String[] args) {
Integer arr[] = {12, 11, 13, 5, 6, 7};
System.out.println(Arrays.toString(arr));
QuickSort<Integer> obj = new QuickSort<>();
obj.sort(arr);
System.out.println(Arrays.toString(arr));
}
}
/*
Sample run:
[12, 11, 13, 5, 6, 7]
[5, 6, 7, 11, 12, 13]
*/