Chapter 7 Quicksort

Is quicksort an incremental algorithm or a divide and conquer algorithm?
Quicksort is a divide and conquer algorithm.

What does quicksort do during the divide step?
During the divide step, quicksort partitions the array into two subarrays, and , such that all elements of the first array are and all elements of the second array are .

What is returned after the partition procedure?
After the partition procedure, is returned.

What does quicksort do during the conquer step?
During the conquer step, quicksort sorts and recursively.

What does quicksort do during the combine step?
During the combine step, quicksort does nothing.

Where is the most effort being used in the quicksort algorithm?
The most effort being used in the quicksort algorithm is during the divide step.

Where is the most effort being used in the merge sort algorithm, in comparison?
In comparison, the most effort being used in the merge sort algorithm is during the combine step.

What is the pseudocode for the Quicksort procedure?
The pseudocode for the Quicksort procedure is:

Quicksort(A, p, r)
1. if p < r
2.     // Partition the array around the pivot which ends up at A[q]
3.     q = Partition(A, p, r)
4.     Quicksort(A, p, q - 1) // Recursively sort the low side
5.     Quicksort(A, q + 1, r) // Recursively sort the high side

What is the pseudocode for the Partition procedure?
The pseudocode for the Partition procedure is:

Partition(A, p, r)
1. x = A[r] // The pivot
2. i = p - 1 // Highest index on the low side
3. for j = p to r - 1 // Process each element other than the pivot
4.     if A[j] <= x // Does this element belong to the low side
5.         i = i + 1
6.         exchange A[i] and A[j]
7. exchange A[i+1] and A[r] // Just to the right of the low side
8. return i + 1 // The new index of the pivot

What are three statements which describe the loop invariant of quicksort?
The three statements which describe the loop invariant of quicksort are:

  1. Elements in the array before index are less than or equal to the pivot . That is, if .
  2. Elements in the array between the index and are larger than the pivot . That is, if .
  3. Elements in the array after index are not yet compared.

...

Performance of Quicksort

What does the performance of quicksort depend on?
The performance of quicksort depends on whether the partition is "balanced" or not.

What is the runtime of quicksort if the partition is balanced?
If the partition is balanced, the runtime of quicksort is .

What is the runtime of quicksort if the partition isn't balanced?
If the partition isn't balanced, the runtime of quicksort is .

What is the worst-case partition for quicksort?
The worst-case partition for quicksort is when it produces one subarray with elements.

What happens when worst-case partitioning happens at each recursive step?
When worst-case partitioning happens at each recursive step, the runtime of quicksort is .

What is the best-case partition for quicksort?
The best-case partition for quicksort is when it produces two subarrays with and elements.

What happens when the best-case partitioning happens at each recursive step?
When the best-case partitioning happens at each recursive step, the runtime of quicksort is or .