Scribd
Upload
18 views3 pages

Understanding Quick Sort and Pivot Choice

Quick Sort is an efficient sorting algorithm that uses a pivot to partition an array into two subarrays: one with elements less than or equal to the pivot and another with elements greater than the pivot. The choice of pivot significantly affects the algorithm's performance, with a good pivot leading to O(n log n) time complexity in the best and average cases, while a bad pivot can lead to O(n²) in the worst case. The process involves recursively sorting the subarrays until the entire array is sorted.

Uploaded by

24cse188
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
18 views3 pages

Understanding Quick Sort and Pivot Choice

Quick Sort is an efficient sorting algorithm that uses a pivot to partition an array into two subarrays: one with elements less than or equal to the pivot and another with elements greater than the pivot. The choice of pivot significantly affects the algorithm's performance, with a good pivot leading to O(n log n) time complexity in the best and average cases, while a bad pivot can lead to O(n²) in the worst case. The process involves recursively sorting the subarrays until the entire array is sorted.

Uploaded by

24cse188
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Quick Sort

What is a Pivot?

The pivot is a selected element in the array that acts as a reference to divide (partition) the
array into two subarrays:

Left subarray: Elements less than or equal to the pivot.

Right subarray: Elements greater than the pivot.

After partitioning, the pivot element is placed in its correct sorted position, and the process
repeats recursively on both subarrays.

The pivot determines how well the array is divided during partitioning.
Its role is to help divide the array such that sorting becomes efficient.

If the pivot is chosen well, the array gets balanced subarrays, leading to fewer recursive
calls and better performance.

Partition
Pivot Choice Quality Time Complexity Remarks
Balance
Nearly equal
Good Pivot (middle value) O(n log n) Best / average case
halves
Bad Pivot (smallest or largest
Very unbalanced O(n²) Worst case
value)
O(n log n) on Common practical
Random Pivot Usually balanced
average choice

Time
Case Condition Explanation
Complexity
Pivot divides array into Each partition step takes O(n) for
Best Case two equal halves every O(n log n) comparison + log n levels of recursion
time (since the array is halved each time).
Average Pivot divides array On average, partitions are balanced
O(n log n)
Case roughly evenly on average enough to keep recursion depth ≈ log n.
Pivot is always smallest or Array becomes one-sided; recursion
Worst
largest element (highly O(n²) depth becomes n (like bubble or
Case
unbalanced) insertion sort).

Example: Quick Sort using last element as pivot

Given Array:
[10, 80, 30, 90, 40, 50, 70]

Quick Sort in 3 steps


A) Choose the last element as the pivot.
B) Partition the array.
C) Recursively sort the subarrays.
quickSort(arr, low, high)
if low < high:
p = partition(arr, low, high)
quickSort(arr, low, p - 1)
quickSort(arr, p + 1, high)

partition(arr, low, high)


pivot = arr[high]
i = low - 1
for j = low to high - 1:
if arr[j] ≤ pivot:
i=i+1
swap(arr[i], arr[j])
swap(arr[i + 1], arr[high])
return i + 1

Compare
j arr[j] Action i Array after step
with 70
i=0 →
[10, 80, 30, 90, 40, 50,
0 10 ≤ 70 swap(10,1 0
70]
0)
[10, 80, 30, 90, 40, 50,
1 80 > 70 no change 0
70]
i=1 →
[10, 30, 80, 90, 40, 50,
2 30 ≤ 70 swap(80,3 1
70]
0)
[10, 30, 80, 90, 40, 50,
3 90 > 70 no change 1
70]
i=2 →
[10, 30, 40, 90, 80, 50,
4 40 ≤ 70 swap(80,4 2
70]
0)
i=3 →
[10, 30, 40, 50, 80, 90,
5 50 ≤ 70 swap(90,5 3
70]
0)

Finally, swap pivot with arr[i+1] → swap(80,70)

After partition:
[10, 30, 40, 50, 70, 90, 80]
Pivot (70) position = index 4

Step 2 — Sort Left Subarray [10, 30, 40, 50]


(Low=0, High=3, Pivot=50)
j arr[j] Compare Action i Array after step
0 10 ≤ 50 i=0 swap(10,10) 0 [10, 30, 40, 50, 70, 90, 80]
1 30 ≤ 50 i=1 swap(30,30) 1 [10, 30, 40, 50, 70, 90, 80]
2 40 ≤ 50 i=2 swap(40,40) 2 [10, 30, 40, 50, 70, 90, 80]

Swap pivot (50) with arr[i+1] (same position)


After partition: [10, 30, 40, 50, 70, 90, 80]
Pivot position = index 3, So place 50 at index=3

And so on… finally we get the sorted list

You might also like