QuickSort – List Interface Java


Yes, this is one of my assignments.

Question:

I am asked to rewrite a generic QuickSort algorithm using only Java List Interface. The purpose is that the algorithm can be executed for both LinkedList and ArrayList with any type extends Comparable interface. Professor suggests me that I should think stackwise and list approach (instead of in-place approach), using as less memory as possible and still maintain O(nlogn) complexity.

What I got so far

I have these lists lessThanPivot, equalPivot, greaterThanPivot to store the partitions, sortedList to store the output sorted array. These lists are put on top of my class to reuse instead of instantiate them in every pass.

public List<T> lessThanPivot, equalPivot, greaterThanPivot, sortedList; 

The QuickSort function:

    public void quickSort(List<T> data, int start, int end)     {         if (start > end) return;         end = Math.min(data.size(), end);         T pivot = null;         //Construct buffer lists         ListIterator<T> iterator = data.listIterator(end);         while (iterator.hasPrevious() && iterator.previousIndex() >= start)         {             T current = iterator.previous();             if (pivot == null) pivot = current;             if (current.compareTo(pivot) < 0) lessThanPivot.add(current);             else if (current.compareTo(pivot) == 0) equalPivot.add(current);             else greaterThanPivot.add(current);             iterator.remove();         }         int lessThanPivotStartIndex = start + greaterThanPivot.size() + equalPivot.size();         int greaterThanPivotEndIndex = start + greaterThanPivot.size() - 1;         copyBufferListsToOriginalList(data);         //Recursively sort the less than pivot         if (lessThanPivotStartIndex < end && end <= data.size()) quickSort(data, lessThanPivotStartIndex, end);         //In case all the lessThanPivot and equalPivot has been moved to output array, recursively call to sort the whole data         //as it now contains only greaterThanPivot         else if (lessThanPivotStartIndex > data.size()) {quickSort(data, 0, data.size()); return;}          //Recursively sort the greater than pivot         if (greaterThanPivotEndIndex > start) quickSort(data, start, greaterThanPivotEndIndex);     } 

The copyBufferListsToOriginalList function:

    private void copyBufferListsToOriginalList(List<T> data)     {         if (lessThanPivot.size() <= 1) {             copy(lessThanPivot, sortedList);             copy(equalPivot, sortedList);             if (greaterThanPivot.size() <= 1) copy(greaterThanPivot, sortedList);             else copy(greaterThanPivot, data);         }else {             copy(greaterThanPivot, data);             copy(equalPivot, data);             copy(lessThanPivot, data);         }     } 

Problems

  • Even though my QuickSort can sort correctly, but it runs quite slow compare to recursive in-place versions.
  • I got StackOverflow exception when n = 10,000.

I am not sure what is wrong and what could I improve on my program.

Thanks for your all advice and stay safe.