0
Ich habe ein bisschen mit meiner Quicksort-Funktion gerungen, habe aber immer noch keine Ahnung, was ich falsch mache.Doppelte Warteschlange (Deque) Quicksort
Wenn ich laufen quicksort auf einem zufällig erzeugten Deque Elemente enthalten [6,92,63,90,79,94,8,13,72,28]
Das Resultat ist [13,8,28, 94,92,63,72,90,79,6]
public class DoublyLinkedDeque<E extends Comparable<E>> implements DequeADT<E>
{
...
public void quickSort(DoublyLinkedDeque<E> deque, Comparator<E> comp)
{
int n = deque.size();
if (n < 2)
{
return;
}
// using first as arbitrary pivot
E pivot = deque.first();
DoublyLinkedDeque<E> left = new DoublyLinkedDeque<>();
DoublyLinkedDeque<E> equalsPivot = new DoublyLinkedDeque<>();
DoublyLinkedDeque<E> right = new DoublyLinkedDeque<>();
while (!deque.isEmpty())
{
// divide original into left, equalsPivot, and right
E element = deque.dequeueFront();
int tmpCompare = comp.compare(element, pivot);
// element is less than pivot
if (tmpCompare < 0)
{
left.enqueueFront(element);
}
// element is equal to pivot
else if (tmpCompare == 0)
{
equalsPivot.enqueueFront(element);
}
// element is greater than pivot
else
{
right.enqueueFront(element);
}
}
// sort elements less than pivot
quickSort(left, comp);
// sort elements greater than pivot
quickSort(right, comp);
// concatenate results
while (!left.isEmpty())
{
deque.enqueueFront(left.dequeueFront());
}
while (!equalsPivot.isEmpty())
{
deque.enqueueFront(equalsPivot.dequeueFront());
}
while (!right.isEmpty())
{
deque.enqueueFront(right.dequeueFront());
}
}
}
public static void main(String[] args)
{
DoublyLinkedDeque<Integer> deque = new DoublyLinkedDeque<Integer>();
/* ADDING RANDOM NUMBER TO deque */
Comparator<Integer> intComparator = new Comparator<Integer>()
{
@Override
public int compare(Integer i1, Integer i2)
{
return (i1 < i2 ? -1 : i1 > i2 ? +1 : 0);
}
};
deque.quickSort(deque, intComparator);
}