Quicksort in Java! Complete the Sort static utility class, using a recursive imp
ID: 3575930 • 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.
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 other version of the algorithms will use a Comparator to compare elements in the lists. To test this version of the sort method, you will need to instantiate a class that implements the Comparator interface.
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)
{
// TODO: Implement recursive quicksort algorithm using Comparator
}
}
Explanation / Answer
I think this will help ..
private static <T extends Comparable<T>> void quicksort(IUListWithListIterator<T> list)
{
// TODO: Implement recursive quicksort algorithm
if (list.size() <= 1) return list;
T pivot = list.getFirst();
List<T> less = new LinkedList<E>();
List<T> pivotList = new LinkedList<E>();
List<T> more = new LinkedList<E>();
for (T i: arr) {
if (i.compareTo(pivot) < 0) less.add(i);
else if (i.compareTo(pivot) > 0) more.add(i);
else pivotList.add(i);
}
less = quickSort(less);
more = quickSort(more);
less.addAll(pivotList);
less.addAll(more);
return l
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.