Sorting an ArrayList of Vehicles using quick sort

Question

For an assignment I have to sort an ArrayList of Vehicle objects using the quick sort method. I have come up with two implementations for this, which would be the best to use? Is method 1 considered quick sort since it splits the array?

Method 1

protected ArrayList<Vehicle> quickSort(ArrayList<Vehicle> list)
{
 if (list.size() <= 1) 
 return list; // Already sorted 
 ArrayList<Vehicle> sorted = new ArrayList<Vehicle>();
 ArrayList<Vehicle> lesser = new ArrayList<Vehicle>();
 ArrayList<Vehicle> greater = new ArrayList<Vehicle>();
 Vehicle pivot = list.get(list.size()-1); // Use last Vehicle as pivot
 for (int i = 0; i < list.size()-1; i++)
 {
 //int order = list.get(i).compareTo(pivot);
 if (list.get(i).compareTo(pivot) < 0)
 lesser.add(list.get(i)); 
 else
 greater.add(list.get(i)); 
 }
 lesser = quickSort(lesser);
 greater = quickSort(greater);
 lesser.add(pivot);
 lesser.addAll(greater);
 sorted = lesser;
 return sorted;
}

Method 2

protected ArrayList<Vehicle> quickSort(ArrayList<Vehicle> list, int a, int b)
{
 if (a >= b) 
 return list;
 Vehicle pivot = list.get(b);
 int left = a;
 int right = b;
 while (left < right)
 {
 while(list.get(left).compareTo(pivot) < 0)
 left++;
 while(list.get(right).compareTo(pivot) > 0)
 right--;
 if (right > left);
 {
 Collections.swap(list, left, right);
 }
 }
 quickSort(list, a, right-1);
 quickSort(list, right+1, b);
 return list;
}

Now the problem with Method 2 is that my protected quickSort is called from

public ArrayList<Vehicle> quickSort()
{ 
 return quickSort(vehicleList);
}

which I'm not allowed to modify, so I'd need to overload the method again and call my version with the two extra integer parameters. Would this just be messy doing another overload?

Answer 1

Is method 1 considered quick sort since it splits the array?

It is quick sort because you split the array in parts lesser and greater than the pivot, and recursivly sorting these arrays.

Would this just be messy doing another overload?

No. The quickSort with the extra params is internal, so callers from outside the class won't even see it.

Which one is best to use?

That depends on what you call 'better'. I prefer the first method because I find it much easier to understand. The second has (I suspect) better performance, because you create less objects.

Note

While you probably need to return an ArrayList because of the given signature, it is preferred to return the interface List. See here

Answer 2

In method 1 the sorted list you create here:

ArrayList<Vehicle> sorted = new ArrayList<Vehicle>();

is never used and overwritten here:

sorted = lesser;

Just drop the variable sorted and return lesser.

---

There is no reason to limit the method to ArrayLists or even Vehicles. Just have Vehicle implement the standard Comparableinterface and let your method have the signature:

protected <T extends Comparable<T>> List<T> quickSort(List<T> list) {
 // ...
}

• screencut: Well it's limited to ArrayList<Vehicle> due to the lecturer making it that way, I had no control over that.