Partition Algorithm - Solution

Solution to Problem 1
Given Array:
A = ⟨15, 7, 20, 3, 9, 12, 6, 18, 5, 10, 14, 8⟩
The pivot element is the last element: x = 8.

Partition Algorithm
The following function implements the partitioning procedure:
1 def partition (A , p , r ) :
2 x = A [ r ] # Pivot element
3 i = p - 1 # B o u n d a r y for e l e m e n t s <= pivot
4
5 for j in range (p , r ) :
6 if A [ j ] <= x :
7 i += 1
8 A[i], A[j] = A[j], A[i] # Swap e l e m e n t s
9
10 A [ i + 1] , A [ r ] = A [ r ] , A [ i + 1] # Place pivot in correct
position
11 return i + 1
12
13 # Example usage
14 A = [15 , 7 , 20 , 3 , 9 , 12 , 6 , 18 , 5 , 10 , 14 , 8] # Given dataset
15 p = 0
16 r = len ( A ) - 1
17
18 partition (A , p , r )
19 print ( A ) # Final p a r t i t i o n e d array

Step-by-Step Execution
Initial: 15 7 20 3 9 12 6 18 5 10 14 8
Step 1: 7 15 20 3 9 12 6 18 5 10 14 8
Step 2: 7 3 20 15 9 12 6 18 5 10 14 8
Step 3: 7 3 6 15 9 12 20 18 5 10 14 8
Step 4: 7 3 6 5 9 12 20 18 15 10 14 8
Step 5: 7 3 6 5 8 12 20 18 15 10 14 9 ← **Final Partition**

1
Final Output:

A = ⟨7, 3, 6, 5, 8, 12, 20, 18, 15, 10, 14, 9⟩

2
Solution to Problem 2
1. Running time of QuickSort when all elements of an array
have the same value.
Understanding the Behavior of QuickSort
QuickSort is a divide-and-conquer sorting algorithm that partitions the array
around a pivot and recursively sorts the subarrays. The efficiency of QuickSort
depends on how well the partitioning step divides the array.
• Best Case: If the pivot divides the array into nearly equal halves, the re-
cursion depth is O(log n), leading to a total time complexity of O(n log n).
• Worst Case: If the partitioning is unbalanced, the recursion depth can
be O(n), leading to a worst-case time complexity of O(n2 ).

Case: All elements are the same

• The partitioning step does not reduce the problem size significantly.
• All elements end up in one partition, except for the pivot.
• The recursion tree degenerates into n recursive calls, each reducing the
array size by only one element.
Thus, the recurrence relation for this worst case is:

T (n) = T (n − 1) + O(n)
Expanding the recurrence:

T (n) = T (n − 1) + n

T (n − 1) = T (n − 2) + (n − 1)

..
.

T (1) = O(1)
Summing all terms:

T (n) = O(n + (n − 1) + (n − 2) + · · · + 1)
Using the sum formula:
 
n(n + 1)
T (n) = O = O(n2 )
2
Final Answer: The running time of QuickSort when all elements are iden-
tical is O(n2 ).

3
 2. What value of q does Partition return when all elements
in A[p..r] have the same value?
The Partition algorithm works by:
1. Selecting the pivot as A[r].
2. Moving elements ≤ pivot to the left and those > pivot to the right.

3. Swapping the pivot into its correct position.

If all elements are the same:
• Every element satisfies A[j] ≤ x, so the loop moves i from p − 1 to r − 1.
• The final swap does not alter the array.

Thus, the partition will always return:

q=r

when all elements are identical.

3. Modifying Partition to Ensure q = ⌊(p + r)/2⌋

To modify Partition, we must:
• Detect when all elements in A[p..r] are the same.

• Force the return value to be q = ⌊(p + r)/2⌋.

Modified Partition Algorithm

1 def partition (A , p , r ) :
2 x = A [ r ] # Pivot element
3 i = p - 1 # B o u n d a r y for e l e m e n t s <= pivot
4 all_same = True # Flag to check if all e l e m e n t s are i d e n t i c a l
5
6 for j in range (p , r ) :
7 if A [ j ] != x :
8 all_same = False # Found a d i f f e r e n t element
9 if A [ j ] <= x :
10 i += 1
11 A [ i ] , A [ j ] = A [ j ] , A [ i ] # Swap e l e m e n t s
12
13 A [ i + 1] , A [ r ] = A [ r ] , A [ i + 1] # Place pivot in correct
position
14
15 if all_same : # If all e l e m e n t s are i d e n t i c a l
16 return ( p + r ) // 2
17 return i + 1 # Normal p a r t i t i o n result

4
Explanation of Modifications
1. Tracking identical elements: A flag all same is initialized to True.
2. Checking uniqueness: If any element differs from A[r], we set all same =
False.
3. Returning the correct index:
• If all elements are the same, we return:
q = ⌊(p + r)/2⌋
• Otherwise, we return the usual partition result.
This modification ensures that when all elements are identical, the pivot is
placed at the middle index instead of always at r.

4. Running time of QuickSort with modified Partition

when all elements are the same
Understanding the Modification to PARTITION
The modified partition ensures that when all elements are the same, the pivot
is placed at the middle index:

q = ⌊(p + r)/2⌋
instead of always placing it at r.

Effect on QuickSort Complexity

1. In the original worst-case scenario, QuickSort reduces the array size by
only one element per step:
T (n) = T (n − 1) + O(n)

2. With the modified partition, the pivot is always placed in the middle,
ensuring the array is split into two nearly equal halves:
T (n) = 2T (n/2) + O(n)

3. Using the Master Theorem for divide-and-conquer recurrences:

T (n) = O(n log n)

Conclusion
By forcing the pivot to be placed at the middle when all elements are identical:
• The recursion tree is balanced instead of degenerate.
• The depth of the recursion tree is reduced to O(log n).
• The overall time complexity improves from O(n2 ) to O(n log n).

5
Solution to Problem 3(1)
Illustrate the operation of COUNTING-SORT on the array:

A = ⟨6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2⟩

Step 1: Initialize the Auxiliary Array C

We initialize an auxiliary array C of size max(A) + 1 = 7, since the largest
number in A is 6. Initially, C is filled with zeros:

C = [0, 0, 0, 0, 0, 0, 0]

Step 2: Count Occurrences

We iterate through A and count the occurrences of each number:

C = [2, 2, 2, 2, 1, 0, 2]

Step 3: Compute Cumulative Counts

Now, we modify C so that each C[i] contains the number of elements less than
or equal to i:

C[i] = C[i] + C[i − 1]

C = [2, 4, 6, 8, 9, 9, 11]

Table 1: Step-by-step updates for arrays B and C

Iter Ele Placed at Index Updated Array B Updated C
1st 2 C[2] = 6 → 5 2 [2, 4, 5, 8, 9, 9, 11]
2nd 3 C[3] = 8 → 7 23 [2, 4, 5, 7, 9, 9, 11]
3rd 1 C[1] = 4 → 3 1 23 [2, 3, 5, 7, 9, 9, 11]
4th 6 C[6] = 11 → 10 1 23 6 [2, 3, 5, 7, 9, 9, 10]
5th 4 C[4] = 9 → 8 1 23 4 6 [2, 3, 5, 7, 8, 9, 10]
6th 3 C[3] = 7 → 6 1 2334 6 [2, 3, 5, 6, 8, 9, 10]
7th 1 C[1] = 3 → 2 11 2334 6 [2, 2, 5, 6, 8, 9, 10]
8th 0 C[0] = 2 → 1 011 2334 6 [1, 2, 5, 6, 8, 9, 10]
9th 2 C[2] = 5 → 4 01122334 6 [1, 2, 4, 6, 8, 9, 10]
10th 0 C[0] = 1 → 0 001122334 6 [0, 2, 4, 6, 8, 9, 10]
11th 6 C[6] = 10 → 9 00112233466 [0, 2, 4, 6, 8, 9, 9]

6
Step 4: Build Sorted Output Array B
We process A in reverse order, placing each element at the correct position
in B, and decrementing C[A[j]] after placing each element:

Final Array B:
B = [0, 0, 1, 1, 2, 2, 3, 3, 4, 6, 6]

Final Array C:
C = [0, 2, 4, 6, 8, 9, 9]

7
Solution to Problem 3(2)
Yes, COUNTING-SORT is a stable sorting algorithm.

Why is COUNTING-SORT Stable?

1. Elements are placed in the output array in reverse order (from
right to left in the input array).
• During the final placement step (lines 10–12 in the algorithm),
elements are processed from right to left in the input array A.
• This ensures that if two elements have the same value, the one that
appears later in A is placed later in B, preserving their relative order.

2. Cumulative counting ensures proper placement.

• The auxiliary array C stores the cumulative count of elements,
which is used to determine the final position of each element in the
sorted output.
• Since C[A[j]] is decremented after placing an element, the place-
ment order follows the order of occurrences in the input array.

Example Demonstrating Stability

Consider the input array: A = ⟨(5, a), (2, a), (2, b), (8, a), (5, b)⟩, where elements
have labels to distinguish identical values.

Step 1: Counting Occurrences

We count each value and compute cumulative sums:

C = [0, 0, 2, 2, 2, 4, 4, 4, 5]

Step 2: Build Output Array

Processing from right to left in A:

Table 2: Step-by-step placement in COUNTING-SORT

Processing Placed at Index Updated Output B
(5,b) C[5] = 4 (5, b)
(8,a) C[8] = 5 (5, b), (8, a)
(2,b) C[2] = 2 (2, b) (5, b), (8, a)
(2,a) C[2] = 1 (2, a), (2, b) (5, b), (8, a)
(5,a) C[5] = 3 (2, a), (2, b), (5, a), (5, b), (8, a)

8
Final Sorted Output
B = ⟨(2, a), (2, b), (5, a), (5, b), (8, a)⟩
Since (2,a) appears before (2,b) in the input, it remains before (2,b) in the
output, proving stability.

9
Solution to Problem 4(1)
The original unsorted list of words:

COW, DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW, FOX.

We apply Radix Sort, processing from the least significant letter (right-
most) to the most significant letter (leftmost).

Step 1: Sorting by the 3rd (Last) Letter

Sorting based on the last letter of each word:

BAR, COW, SEA, MOB, TAB, BIG, DIG, RUG, DOG, ROW, NOW, FOX, EAR, TAR, TEA

Step 2: Sorting by the 2nd (Middle) Letter

Sorting based on the second letter while maintaining previous order:

BAR, MOB, TAB, BIG, DIG, COW, DOG, FOX, NOW, EAR, SEA, RUG, ROW, TAR, TEA

Step 3: Sorting by the 1st (First) Letter

Sorting based on the first letter while maintaining previous order:

BAR, BIG, COW, DIG, DOG, EAR, FOX, MOB, NOW, RUG, ROW, SEA, TAB, TAR, TEA

Final Sorted Order

After processing all three letters, the final sorted order is:

BAR, BIG, COW, DIG, DOG, EAR, FOX, MOB, NOW, RUG, ROW, SEA, TAB, TAR, TEA.

10
Solution to Problem 4(2)
We are given an array of n integers, where each integer falls within the range:

0 ≤ x ≤ n3 − 1
Our goal is to sort these numbers in O(n) time.

Key Idea: Radix Sort with Base n

Since the maximum number in the range is n3 − 1, each number can be repre-
sented in base n using at most three digits:

x = d2 · n2 + d1 · n + d0
where:
• d0 is the least significant digit (units place in base n).
• d1 is the middle digit.

• d2 is the most significant digit.

Since each number consists of at most 3 digits in base n, we can use Radix Sort
with three passes, sorting by each digit using Counting Sort.

Radix Sort with Counting Sort

Radix Sort processes numbers digit by digit, from the least significant digit to
the most significant digit:
1. Sort based on the least significant digit (d0 ).

2. Sort based on the middle digit (d1 ).

3. Sort based on the most significant digit (d2 ).
Each step uses Counting Sort, which runs in O(n) time since the digit range is
0 to n − 1.

Time Complexity Analysis

Since Counting Sort runs in O(n) time and Radix Sort requires three passes,
the total complexity is:

O(3n) = O(n)

11