quicksort for arraylist

Solutions on MaxInterview for quicksort for arraylist by the best coders in the world

showing results for - "quicksort for arraylist"
Samantha
10 Nov 2018
1public static ArrayList<Vehicle> quickSort(ArrayList<Vehicle> list)
2{
3    if (list.isEmpty()) 
4        return list; // start with recursion base case
5    ArrayList<Vehicle> sorted;  // this shall be the sorted list to return, no needd to initialise
6    ArrayList<Vehicle> smaller = new ArrayList<Vehicle>(); // Vehicles smaller than pivot
7    ArrayList<Vehicle> greater = new ArrayList<Vehicle>(); // Vehicles greater than pivot
8    Vehicle pivot = list.get(0);  // first Vehicle in list, used as pivot
9    int i;
10    Vehicle j;     // Variable used for Vehicles in the loop
11    for (i=1;i<list.size();i++)
12    {
13        j=list.get(i);
14        if (j.compareTo(pivot)<0)   // make sure Vehicle has proper compareTo method 
15            smaller.add(j);
16        else
17            greater.add(j);
18    }
19    smaller=quickSort(smaller);  // capitalise 's'
20    greater=quickSort(greater);  // sort both halfs recursively
21    smaller.add(pivot);          // add initial pivot to the end of the (now sorted) smaller Vehicles
22    smaller.addAll(greater);     // add the (now sorted) greater Vehicles to the smaller ones (now smaller is essentially your sorted list)
23    sorted = smaller;            // assign it to sorted; one could just as well do: return smaller
24
25    return sorted;
26}