CODEWITHSUNDEEP
javaalgorithmsortingquicksort
Abhishek
Abhishek

Reputation: 380

Quicksort Divide and Conquer

I am trying to implement Quicksort using the divide and conquer technique. I am getting a Stack Overflow error in the recursion calls. Here is my code:

public static void main(String[] args) {
    ArrayList<Integer> unsorted = new ArrayList<Integer>();

    unsorted.add(23);
    unsorted.add(5);
    unsorted.add(1);
    unsorted.add(-8);
    unsorted.add(101);
    unsorted.add(21);
    unsorted.add(10);
    unsorted.add(10);
    unsorted.add(0);
    unsorted.add(50);

    ArrayList<Integer> sorted = Quicksort(unsorted);
    System.out.println(sorted.toString());
}

public static ArrayList<Integer> Quicksort(ArrayList<Integer> unsorted) {

    if (unsorted.size() <= 1)
        return unsorted;

    ArrayList<Integer> less = new ArrayList<Integer>();
    ArrayList<Integer> more = new ArrayList<Integer>();

    int pivotindex = unsorted.size()/2;

    for (int i = 0; i < unsorted.size(); i++) {
        if (unsorted.get(i) < unsorted.get(pivotindex))
            less.add(unsorted.get(i));
        else
            more.add(unsorted.get(i));
    }

    ArrayList<Integer> sorted = Quicksort(less);
    sorted.add(unsorted.get(pivotindex));
    sorted.addAll(Quicksort(more));

    return sorted;
}

I want it to implement using ArrayLists. Can anyone point out where I am wrong?

Thanks a lot.

Upvotes: 0

Views: 467

Answers (3)

Debanik Dawn
Debanik Dawn

Reputation: 799

You should keep your pivot value in a separate place from the more and less lists.

Change the condition to:

else if(unsorted.get(i) > unsorted.get(pivotindex))
        more.add(unsorted.get(i));

It should work fine. Hope this helps.

EDIT: As mentioned in the comment by Josh, this wouldn't work if there are multiple elements having the same value as the pivot. For this, what you can do is define another ArrayList called equal and add this line:

else
    equal.add(unsorted.get(i));

Then append this list along with the pivot element when you merge the array back.

Thanks for pointing this out. :)

Note: This sort won't be guaranteed to be stable (as elements having same value might not be placed according to their relative positions in the original array).

Upvotes: 5

Josh Evans
Josh Evans

Reputation: 655

This seems like a solution that can be understood easily

ArrayList<Integer> less = new ArrayList<Integer>();
ArrayList<Integer> equal = new ArrayList<Integer>();
ArrayList<Integer> more = new ArrayList<Integer>();

int pivotindex = unsorted.size()/2;

for (int i = 0; i < unsorted.size(); i++) {
    if (unsorted.get(i) < unsorted.get(pivotindex)) //Put whatever is less to the left
        less.add(unsorted.get(i));
    else if (unsorted.get(i) == unsorted.get(pivotindex)) //Put whatever is equal in the middle
        equal.add(unsorted.get(i));
    else //Put everything else to the right (everything greater)
        more.add(unsorted.get(i));
}

ArrayList<Integer> sorted = Quicksort(less); //Sort the left, then add
sorted.addAll(equal); //Middle is already sorted (all equal), add
sorted.addAll(Quicksort(more)); //Sort the right, then add

return sorted;

Upvotes: 2

Siva R
Siva R

Reputation: 447

The following works perfectly.

public static void main(String[] args) {
         ArrayList<Integer> unsorted = new ArrayList<Integer>();

            unsorted.add(23);
            unsorted.add(5);
            unsorted.add(1);
            unsorted.add(-8);
            unsorted.add(101);
            unsorted.add(21);
            unsorted.add(10);
            unsorted.add(10);
            unsorted.add(0);
            unsorted.add(50);

            ArrayList<Integer> sorted = Quicksort(unsorted);
            System.out.println(sorted.toString());
        }

        public static ArrayList<Integer> Quicksort(ArrayList<Integer> unsorted) {
                System.out.println(unsorted.size());
            if (unsorted.size() <= 1)
                return unsorted;

            ArrayList<Integer> less = new ArrayList<Integer>();
            ArrayList<Integer> more = new ArrayList<Integer>();

            int pivotindex = unsorted.size()/2;

            for (int i = 0; i < unsorted.size(); i++) {
                if (unsorted.get(i) < unsorted.get(pivotindex))
                    less.add(unsorted.get(i));
                else
                    more.add(unsorted.get(i));
            }
            if(less.isEmpty()) {
                less.add(more.remove(more.size() - 1));
            }

            ArrayList<Integer> sorted = Quicksort(less);
            //sorted.add(unsorted.get(pivotindex));
            sorted.addAll(Quicksort(more));

            return sorted;
        }

Upvotes: 0

Related Questions