Problems with Quicksort in Java

Question

So I have been testing different sorting algorithms, and now I have written a Quicksort! It sort of works, but the sorting is a bit off! Almost always I get output like this:

[0, 1, 2, 3, 8, 6, 5, 4, 7, 9, 20, 16, 22, 21, 14, 17, 18, 10, 15, 19, 13, 11, 23, 12, 26, 24, 25, ...

This is the first 27 elements out of the 100 that I am sorting. This is how I fill a randomized list:

for(int i =0; i < 100; i ++){
            int nr = rand.nextInt(100);
            if (!numbers.contains(new Integer(nr))){
                numbers.add(nr);
            }else {
                i--;
            }
} 

Here is the code for Quicksort:

public class Quicksort{
@SuppressWarnings("unchecked")
static public <T> ArrayList<T> sortting(ArrayList<T> t){
    //System.out.print("-");
    T piv;
    ArrayList<T> left ,right ,newT;
    left    = new ArrayList<T>();
    right   = new ArrayList<T>();
    newT    = new ArrayList<T>();

    if (!t.isEmpty()){
        piv = t.get(t.size()/2);
        for (int i =0; i < t.size(); i++){
            if (0 < ((Comparable<T>) piv).compareTo(t.get(i))){ //left
                left.add(t.get(i));
            }else{  //right
                right.add(t.get(i));
            }
        }

        if (left.isEmpty() || right.isEmpty()){
            newT.addAll(left);
            newT.addAll(right);
            return newT;
        }else {
            right = sortting(right);
            left = sortting(left);

            newT.addAll(left);
            newT.addAll(right);
        }

        return newT;
    }
    return null;

}

}

Answer 1

Tack you bdares for your input you pointed out some impotent parts that helped allot!But that was not the problem

The problem was that the pivot was not removed from the array which meas that if the pivot is the smallest element the right array == to the t which leads to an infinite loop and overload the ram!

eg.

5 ,4 ,8 ,6 ,8 will return 5 ,4 ,8 ,6 ,8

So in order to fix this the pivot need to be removed and reattaches to the begin in of the array

and now

5 ,4 ,8 ,6 ,8 will return 4 ,5 ,8 ,6 ,8

here is the source code if you are interested, and pro tip: all ways make sure that at least a small change is hipping thought your iterations

@SuppressWarnings("unchecked")
static public <T> ArrayList<T> sortting(ArrayList<T> t){

    T piv;
    ArrayList<T> left ,right ,newT;
    left    = new ArrayList<T>();
    right   = new ArrayList<T>();
    newT    = new ArrayList<T>();

    if (!t.isEmpty()){
        if (t.size()==1){       //Finish check  -> one elem is sorted
            return t;
        }       
        piv = t.remove(t.size()/2);
        for (int i =0; i < t.size(); i++){          //sorting
            if (0 < ((Comparable<T>) piv).compareTo(t.get(i))){ //left
                left.add(t.get(i));
            }else{  //right
                right.add(t.get(i));
            }
        }   
        right   = sortting(right);  //sub sorting
        left    = sortting(left);

        newT.addAll(left);      //building newT
        newT.add(piv);
        newT.addAll(right);
        return newT;
    }
    return new ArrayList<>();   
}

Answer 2

Your problem is with this block:

    if (left.isEmpty() || right.isEmpty()){
        newT.addAll(left);
        newT.addAll(right);
        return newT;
    }

If you choose a pivot at some point that just happens to be the smallest in the current sublist, then that sublist is automatically considered to be sorted. You should just remove that check and sort the left and right sublists.

This is okay because then you'll go into the recursive call with an empty list, in which case you return null.

if (!t.isEmpty()){ ... return newT;}
return null;

I'm actually not sure if ArrayList.addAll() handles null inputs gracefully. If you're concerned about that, then you can just return an empty ArrayList instead of null.