Scribd
Upload
6 views16 pages

Quicksort Algorithm Explained

Quicksort is a divide and conquer algorithm that sorts an array by partitioning it into subarrays based on a pivot element. The algorithm recursively sorts the subarrays and has a best and average case runtime of O(n log n), while the worst case occurs when the pivot is the smallest or largest element. Modifications can be made to sort in decreasing order by adjusting the partitioning condition.

Uploaded by

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

Quicksort Algorithm Explained

Quicksort is a divide and conquer algorithm that sorts an array by partitioning it into subarrays based on a pivot element. The algorithm recursively sorts the subarrays and has a best and average case runtime of O(n log n), while the worst case occurs when the pivot is the smallest or largest element. Modifications can be made to sort in decreasing order by adjusting the partitioning condition.

Uploaded by

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

Quicksort

Algorithm
Quicksort applies divide and conquer to sort an array A [ p : r ]

● Divide: Partition A [ p : r ] into two subarrays A [ p : q - 1 ] and A [ q+1 : r ] such


that
○ Elements in A [ p : q - 1 ] <= Pivot A [ q ]
○ Pivot A [ q ] <= Elements in A [ q + 1 : r ]
● Conquer: Call quicksort recursively to sort each subarrays A [ p : q - 1 ] and A
[ q+1 : r ]
● Combine by doing nothing
Algorithm
Partition
Illustration
Illustration
Illustration
Question
Illustrate the operation of partition on the array

A = [ 13, 19, 9, 5, 12, 8, 7, 4, 11 ]

Answer: [ 9 5 8 7 4 11 19 12 13 ]
Question
Q: What value of q does Partition return when all elements in the array A [ p : r ]
have the same value?

A: r
Question
What is runtime of Partition on a subarray of size n?

A:
Question
Modify Quicksort to sort array into monotonically decreasing order.

A: Modify Line 4 in Partition function to → “if A[j] > x”

Sample array [ 13 19 9 5 12 8 7 4 [ 11 ] ]

Step 1 : [ 13 19 12 ] [ 11 ] [9874 5 ]

Step 2 : [ 19 13 ] [ 12 ] [ 11 ] [ 9 8 7 ] [ 5 ] [ 4 ]
Performance of Quicksort: Worst case partitioning
Worst case behavior
Before partitioning [ 12345678 ]
n elements
Pivot = 8
After partitioning [ 1234567 ] [ 8 ] [ ]
n -1 elements 0 elements

T (n) = +T(n-1)+T(0) = +T(n-1)+ = T (n-1) +


Best case partitioning
Best case:

A [ 1739 ] [ 11 ] [ 13 15 14 20 ]

n/2 elements Pivot n/2 elements

T ( n ) = T ( n/2 ) + T ( n/2 ) +

= 2 T ( n/2 ) +

Solution: as we have found in merge sort


Average case: Balanced partitioning
A = [ 13 6 7 8 21 32 77 24 10 ] [ 80 ] [ 100 ]

9 elements ` Pivot 1 elements

Partitioning splits the array in 9:1 ratio at each step


Each level costs at
most n =

Recursion terminates
at level

Quicksort runs in
O(n log n ) in this case

Any split of constant


proportionality yields
recursion tree of depth
Where each
level cost

Run-time O(n log n)


Questions
What is the running-time of quicksort if all elements of an array A have same
value?

Show that running time of quick sort is if elements are distinct and sorted in
decreasing order.

You might also like