QuickSort

Given the QuickSort implementation from class, provide an 18-element list of integers that will take the least number of recursive calls of QuickSort to complete. You must state your reasoning clearly as to why your list of 18 integers would take the least recursive calls. Simply providing the integer list without explanation will lead to ZERO credit.

//As a counter-example, here is a list that will cause QuickSort to make the 
//MOST number of recursive calls:

public static List<Integer> input() {
	return Arrays.asList(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
}

//And here’s the QuickSort algorithm, for convenience:
algorithm QuickSort
Input: lists of integers lst of size N
Output: new list with the elements of lst in sorted order

if N < 2
	return lst
pivot = lst[N-1]
left = new empty list
right = new empty list
for index i = 0, 1, 2, ... N-2
	if lst[i] <= pivot
		left.add(lst[i])
	else
		right.add(lst[i])
return QuickSort(left) + [pivot] + QuickSort(right)

Answer

Myth: The least number of recursive calls will be made if the pivot always lands in the middle of the list.

My initial solution yielded sub-par results. Following this rule, I ended up with 3 redundant recursive calls (namely call 5, 10, and 16).

I realized that the pivot does not need to be in the middle, rather it must create left/right sub-lists that are exactly 3 elements long, as shown in calls 18, 19, and 20 above. Implementing this strategy, I was able to cut down to only one redundant recursive call.

The code below shows the results where # of dashes = # of recursive calls +1

public static void main(String[] args) {

		List<Integer> test = QuickSort(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18));
		System.out.println("\\n" + test);

		test = QuickSort(Arrays.asList(18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1));
		System.out.println("\\n" + test);

		test = QuickSort(Arrays.asList(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0));
		System.out.println("\\n" + test);
		
		// initial solution
		test = QuickSort(Arrays.asList(1, 2, 4, 3, 6, 7, 9, 8, 5, 11, 12, 14, 13, 16, 18, 17, 15, 10));
		System.out.println("\\n" + test);

		// best solution
		test = QuickSort(Arrays.asList(1, 3, 2, 5, 7, 6, 9, 11, 10, 13, 15, 14, 17, 18, 16, 12, 8, 4));
		System.out.println("\\n" + test);

	}

	public static List<Integer> QuickSort(List<Integer> lst) {
		System.out.print("- ");
		int n = lst.size();
		if (n < 2) {
			return lst;
		}
		int pivot = lst.get(n - 1);
		List<Integer> left = new ArrayList<>();
		List<Integer> right = new ArrayList<>();
		for (int i = 0; i < n - 1; i++) {
			if (lst.get(i) <= pivot) {
				left.add(lst.get(i));
			} else {
				right.add(lst.get(i));
			}
		}
		List<Integer> sortedLeft = QuickSort(left);
		List<Integer> sortedRight = QuickSort(right);

		sortedLeft.add(pivot);
		sortedLeft.addAll(sortedRight);

		return sortedLeft;
	}

OUTPUT:
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
- - - - - - - - - - - - - - - - - - - - - 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
- - - - - - - - - - - - - - - - - - - 
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

$$ \text{Solution } = \{1, 3, 2, 5, 7, 6, 9, 11, 10, 13, 15, 14, 17, 18, 16, 12, 8, 4\} $$