Quicksort in Java! Complete the Sort static utility class, using a recursive imp
ID: 3576014 • Letter: Q
Question
Quicksort in Java!
Complete the Sort static utility class, using a recursive implementation of the Quicksort sorting algorithm. Complete the Sort class without modifying the sort methods or the method signatures of the quicksort methods.
The part I cannot figure out: One version of the algorithm will compare the elements in the lists using the class-defined compareTo method, which is required by the Comparable interface. Because Sort class will be tested on lists with Integer objects, you will not need to create this method. It's provided by the Integer class.
The code I am missing in down below in bold.
Here's the Sort class:
import java.util.Comparator;
import java.util.ListIterator;
/**
* Class for sorting lists that implement the IUListWithListIterator interface,
* using ordering defined by class of objects in list or a Comparator.
* As written uses Quicksort algorithm.
*
*/
public class Sort
{
/**
* Returns a new list that implements the IUListWithListIterator interface.
* As configured, uses WrappedDLL.
*
* @return a new list that implements the IUListWithListIterator interface
*/
private static <T> IUListWithListIterator<T> newList()
{
return new WrappedDLL<T>();
}
/**
* Sorts a list that implements the IUListWithListIterator interface
* using compareTo() method defined by class of objects in list.
* DO NOT MODIFY THIS METHOD
*
* @param <T>
* The class of elements in the list, must extend Comparable
* @param list
* The list to be sorted, implements IUListWithListIterator interface
* @see IUListWithListIterator
*/
public static <T extends Comparable<T>> void sort(IUListWithListIterator<T> list)
{
quicksort(list);
}
/**
* Sorts a list that implements the IUListWithListIterator interface
* using given Comparator.
* DO NOT MODIFY THIS METHOD
*
* @param <T>
* The class of elements in the list
* @param list
* The list to be sorted, implements IUListWithListIterator interface
* @param c
* The Comparator used
* @see IUListWithListIterator
*/
public static <T> void sort(IUListWithListIterator <T> list, Comparator<T> c)
{
quicksort(list, c);
}
/**
* Quicksort algorithm to sort objects in a list
* that implements the IUListWithListIterator interface,
* using compareTo() method defined by class of objects in list.
* DO NOT MODIFY THIS METHOD SIGNATURE
*
* @param <T>
* The class of elements in the list, must extend Comparable
* @param list
* The list to be sorted, implements IUListWithListIterator interface
*/
private static <T extends Comparable<T>> void quicksort(IUListWithListIterator<T> list)
{
// TODO: Implement recursive quicksort algorithm
}
/**
* Quicksort algorithm to sort objects in a list
* that implements the IUListWithListIterator interface,
* using the given Comparator.
* DO NOT MODIFY THIS METHOD SIGNATURE
*
* @param <T>
* The class of elements in the list
* @param list
* The list to be sorted, implements IUListWithListIterator interface
* @param c
* The Comparator used
*/
private static <T> void quicksort(IUListWithListIterator<T> list, Comparator<T> c)
{
if(list.size() <= 1)
{
return;
}
T pivot = list.remove(list.last());
IUListWithListIterator<T> lesser = new WrappedDLL<T>();
IUListWithListIterator<T> equal = new WrappedDLL<T>();
IUListWithListIterator<T> greater = new WrappedDLL<T>();
T current;
while(!list.isEmpty())
{
current = list.remove(list.first());
if(c.compare(current, pivot) < 0)
{
lesser.addToFront(current);
}
else if(c.compare(current, pivot) == 0)
{
equal.addToFront(current);
}
else
{
greater.addToFront(current);
}
}
quicksort(lesser,c);
quicksort(greater,c);
while(!lesser.isEmpty())
{
list.addToRear(lesser.remove(lesser.first()));
}
while(!equal.isEmpty())
{
list.addToRear(equal.remove(equal.first()));
}
list.addToRear(pivot);
while(!greater.isEmpty())
{
list.addToRear(greater.remove(greater.first()));
}
}
}
Explanation / Answer
Implement recursive quicksort algorithm
Just simple exmple and explain. we use this according to recruitment with array and list
First we define some class varible just like
private int array[];
private int length;
Now define some short method
public void mySort(int[] list) {
// check null and not
if (list == null || list.length == 0) {
return;
}
this.array = list;
length = list.length;
// Here we call another method and send 0 and total index
quickSortMethod(0, length - 1);
}
private void quickSortMethod(int lowIndex, int highIndex) {
int a = lowIndex;
int b = highIndex;
// calculate central number
int mid = array[lowIndex+(highIndex-lowIndex)/2];
// Divide in diffrent array
while (a <= b) {
// move value according to
while (array[a] < mid) {
a++;
}
while (array[b] > mid) {
b--;
}
if (a <= b) {
// call method for change number with each other
changeNumbers(a, b);
//change index to next
a++;
b--;
}
}
// call recursive method
if (lowIndex < b)
quickSortMethod(lowIndex, b);
if (i < highIndex)
quickSortMethod(a, highIndex);
}
// This function use for change number with each other
private void changeNumbers(int a, int b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
First we create class object just like
Sort mysort = new Sort();
here we define array and list according to requrement.
int[] myvalue = {3,6,1,0,45,,11,87,22,56,2};
//call short method and pass array or list according to requrement.
mysort.mySort(input);
//Finaly print array
for(int i:input){
System.out.print(i);
System.out.print(" ");
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.