Q Sort the array <1, 4, 5, 8, 3, 2, 7, 6> using QuickSort, taking the first number of each segment as the pivot. Draw the recursion tree. Assume that a segment containing zero or one element is a base case.
Ans. The final sorted array is:
<1, 2, 3, 4, 5, 6, 7, 8>
Partitioning steps:
Recursion tree:
<1, 4, 5, 8, 3, 2, 7, 6> [pivot 1]
├── <>
└── <4, 5, 8, 3, 2, 7, 6> [pivot 4]
├── <3, 2> [pivot 3]
│ ├── <2>
│ └── <>
└── <5, 8, 7, 6> [pivot 5]
├── <>
└── <8, 7, 6> [pivot 8]
├── <7, 6> [pivot 7]
│ ├── <6>
│ └── <>
└── <>💡 Explanation:
QuickSort selects the first element of each segment as its pivot. Elements smaller than the pivot are placed in the left subarray, while elements larger than the pivot are placed in the right subarray.
The first pivot is 1, which is the smallest value. Therefore, its left subarray is empty and all remaining elements move to the right subarray.
The next pivot, 4, divides its segment into <3, 2> and <5, 8, 7, 6>. The same process continues recursively until every segment contains zero or one element.
Reading the completed tree in the order left subarray → pivot → right subarray produces: <1, 2, 3, 4, 5, 6, 7, 8>.
The tree is relatively tall and unbalanced because several pivots are close to the smallest or largest value in their segments. Such one-sided partitions are a sign of poor pivot selection and may cause QuickSort to approach its O(n2) worst case.