CODEWITHSUNDEEP
javasortingarraylistquicksort
jonan
jonan

Reputation: 217

Implementing QuickSort in descending order on ArrayList

I am trying to implement quickSort in Java on an arrayList, and I want the output to be in descending order. I have the following code:

    public static <K, V extends Comparable> ArrayList<K> quickSort(ArrayList<K> toSort, HashMap<K, V> results) {

        if (toSort.size() <= 1) {
            return toSort;  //already sorted!
        }

        ArrayList<K> sorted = new ArrayList<K>();
        ArrayList<K> lesser = new ArrayList<K>();
        ArrayList<K> greater = new ArrayList<K>();

        K pivot = toSort.get(toSort.size()-1);   //use last element as pivot ??

        for (int i = 0; i < toSort.size(); i++) {

            if (results.get(toSort.get(i)).compareTo(results.get(pivot)) >=  0) {
                greater.add(toSort.get(i));
            }


            else {
                lesser.add(toSort.get(i));
            }
        }


        lesser = quickSort(lesser, results);
        greater = quickSort(greater, results);


        lesser.add(0, pivot);
        greater.addAll(lesser);
        sorted = greater;

However, instead of outputting something like: {99, 98, 97},

I receive the following "doubled" output: {99, 99, 98, 98, 97, 97}

I imagine the mistake is somewhere at the end in the concatenation of the lesser and greater lists, but I can't seem to figure out how to fix it. Any advice? Thanks

Upvotes: 0

Views: 262

Answers (1)

MDK
MDK

Reputation: 499

The problem is you are not removing the pivot-element from the input anywhere, but add it again later, thereby doubling it.

Upvotes: 1

Related Questions