Ordering a List Using QuickSort
QuickSort Strategy

If there is more than one element in ```info.get(first) .. info.get(last)``` then

1. select splitVal
2. split the array so that:
• `info.get(first) . . . info.get(splitPt - 1) <= splitVal`
• `info.get(splitPt).equals(splitVal`)
• `info.get(splitPt + 1) . . . info.get(last) >= splitVal`
3. quickSort the left half
4. quickSort the right half

```// Java Code
void quickSort (ArrayList info, int first, int last)
{
int splitPt;
if (first < last)      // general case
{  // call function split which chooses the splitting value and
// rearranges the array so that
// `info.get(first) . . . info.get(splitPt - 1) <= splitVal` ```
// info.get(splitPt).equals(splitVal```)
`      // info.get(splitPt + 1) . . . info.get(last) >= splitVal` ```
```      split (info, first, last, splitPt);
quickSort (info, first, splitPt - 1);   // sort the left "half"
quickSort (info, splitPt + 1, last);    // sort the right "half"
}
}
```

How do we select splitVal? One simple solution is to use the value in `info[first]` as the splitting value.
 9 20 6 10 14 8 60 11 [first] [last]

After the call to split, all the elements less than or equal to splitVal will be on the left side of the array and all those greater than splitVal will be on the right side of the array and splitVal is in its correct position.

 6 8 9 10 14 20 60 11 [first] [splitPt] [last]

```void Split (ArrayList info, int first, int last, int splitPt)
{  // choose splitVal and rearrange info so that
// info.get(first) . . . info.get(splitPt - 1) <= splitVal and info.get(splitPt) = splitVal
// info.get(splitPt + 1) . . . info.get(last) >= splitVal
splitPt = first;
someType splitVal = info.get(first); // splitVal is chosen from the first array slot
// set up for split loop
// loop invariant:  elements to the left of first are less than or equal to splitVal;
// elements to the right of last are greater than or equal to splitVal

while (first <= last)
{
if (info.get(first) <= splitVal)
first++; // increment first until element > splitVal
else if (info.get(last) >= splitVal))
last--; // decrement last until element < splitVal
// If first and last are on the wrong side of the split point, then swap them
// update first and last to set up to continue splitting
else
{
swap (info.get(first), info.get(last));
first++;
last--;
}
}
swap (info.get(last), info.get(splitPt)); // swap splitVal with element at splitPt
splitPt = last; // set splitPt to place where the halves meet
}
```

Continue to:  Unit 3 / Prev / Next