Please take a look at my quicksort code, and help me combine the sorted lists ba
ID: 3822764 • Letter: P
Question
Please take a look at my quicksort code, and help me combine the sorted lists back to the original list that was passed as a parameter. I don't know how to quite do that.
/**
* Quicksort algorithm to sort objects in a list
* that implements the IndexedUnsortedList 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 IndexedUnsortedList interface
*/
private static <T extends Comparable<T>> void quicksort(IndexedUnsortedList<T> list) {
// TODO: Implement recursive quicksort algorithm
if(list.isEmpty() || list.size() == 1) {
return;
}
WrappedDLL<T> lesser = new WrappedDLL<T>();
WrappedDLL<T> greater = new WrappedDLL<T>();
T pivot = list.remove(list.last());
for(T i: list)
if(i.compareTo(pivot) < 0) {
lesser.add(i);
}
else if(i.compareTo(pivot) > 0) {
greater.add(i);
}
quicksort(lesser);
quicksort(greater);
list.add(pivot); // is this correct?
}
/**
* Quicksort algorithm to sort objects in a list
* that implements the IndexedUnsortedList 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 IndexedUnsortedList interface
* @param c
* The Comparator used
*/
private static <T> void quicksort(IndexedUnsortedList<T> list, Comparator<T> c) {
// TODO: Implement recursive quicksort algorithm using Comparator
if(list.isEmpty() || list.size() == 1) {
return;
}
WrappedDLL<T> lesser = new WrappedDLL<T>();
WrappedDLL<T> greater = new WrappedDLL<T>();
T pivot = list.remove(list.last());
T i;
while(!list.isEmpty()) {
i = list.remove(list.first());
if(c.compare(i, pivot) < 0) {
lesser.add(i);
}
else if(c.compare(i, pivot)> 0) {
greater.add(i);
}
}
quicksort(lesser,c);
quicksort(greater,c);
list.add(pivot); // is this correct?
}
Explanation / Answer
import java.util.Comparator;
public class QuickSort {
/**
* Quicksort algorithm to sort objects in a list that implements the
* IndexedUnsortedList 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 IndexedUnsortedList
* interface
*/
private static <T extends Comparable<T>> void quicksort(IndexedUnsortedList<T> list) {
// TODO: Implement recursive quicksort algorithm
IndexedUnsortedList<T> sorted = new WrappedDLL<T>();
rQuickSort(list, sorted);
for (int i = 0; i < sorted.size(); i++) {
list.set(i, sorted.get(i));
}
}
/**
* Quicksort algorithm to sort objects in a list that implements the
* IndexedUnsortedList 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 IndexedUnsortedList
* interface
* @param c
* The Comparator used
*/
private static <T> void quicksort(IndexedUnsortedList<T> list, Comparator<T> c) {
// TODO: Implement recursive quicksort algorithm using Comparator
IndexedUnsortedList<T> sorted = new WrappedDLL<T>();
rQuickSort(list, sorted, c);
for (int i = 0; i < sorted.size(); i++) {
list.set(i, sorted.get(i));
}
}
private static <E extends Comparable<? super T>, T> void rQuickSort(IndexedUnsortedList<T> list,
IndexedUnsortedList<T> sorted) {
if (list.size() == 1) {
sorted.add(list.iterator().next());
return;
}
if (list.size() == 0) {
return;
}
T pivotI = list.last();
IndexedUnsortedList<T> fatPivot = new WrappedDLL<T>();
IndexedUnsortedList<T> left = new WrappedDLL<T>();
IndexedUnsortedList<T> right = new WrappedDLL<T>();
/* partition data */
for (T next : list) {
@SuppressWarnings("unchecked")
int compare = ((Comparable<? super T>) pivotI).compareTo(next);
if (compare < 0) {
right.add(next);
} else if (compare > 0) {
left.add(next);
} else {
fatPivot.add(next);
}
}
rQuickSort(left, sorted);
for (T t : fatPivot) {
sorted.add(t);
}
rQuickSort(right, sorted);
}
private static <E extends Comparable<? super T>, T> void rQuickSort(IndexedUnsortedList<T> list,
IndexedUnsortedList<T> sorted, Comparator<T> c) {
if (list.size() == 1) {
sorted.add(list.iterator().next());
return;
}
if (list.size() == 0) {
return;
}
T pivotI = list.last();
IndexedUnsortedList<T> fatPivot = new WrappedDLL<T>();
IndexedUnsortedList<T> left = new WrappedDLL<T>();
IndexedUnsortedList<T> right = new WrappedDLL<T>();
/* partition data */
for (T next : list) {
int compare = c.compare(next, pivotI);
if (compare < 0) {
fatPivot.add(next);
} else if (compare > 0) {
right.add(next);
} else {
left.add(next);
}
}
rQuickSort(left, sorted);
for (T t : fatPivot) {
sorted.add(t);
}
rQuickSort(right, sorted);
}
public static void main(String args[]) {
IndexedUnsortedList<Integer> list = new WrappedDLL<>();
list.add(10);
list.add(4);
list.add(5);
list.add(20);
list.add(24);
list.add(1);
QuickSort.quicksort(list);
for (Integer integer : list) {
System.out.println(integer);
}
System.out.println("----------------------------------------");
IndexedUnsortedList<Integer> list2 = new WrappedDLL<>();
list2.add(11);
list2.add(13);
list2.add(3);
list2.add(20);
list2.add(45);
list2.add(1);
QuickSort.quicksort(list2, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o1.compareTo(o2);
}
});
for (Integer integer : list2) {
System.out.println(integer);
}
}
}
Output:
1
4
5
10
20
24
----------------------------------------
1
3
11
13
20
45