Scribd
Upload
18 views15 pages

Quick Sort

Quicksort is a divide-and-conquer algorithm that sorts elements in place by partitioning an array into subarrays based on a pivot element. Its performance varies with input distribution, having a best case of O(n log n) when partitions are even, and a worst case of O(n^2) when the input is already sorted or reverse sorted. Randomized versions of Quicksort help mitigate worst-case scenarios by ensuring that the pivot is chosen randomly, leading to expected running times that are consistently efficient.

Uploaded by

mpin364
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
18 views15 pages

Quick Sort

Quicksort is a divide-and-conquer algorithm that sorts elements in place by partitioning an array into subarrays based on a pivot element. Its performance varies with input distribution, having a best case of O(n log n) when partitions are even, and a worst case of O(n^2) when the input is already sorted or reverse sorted. Randomized versions of Quicksort help mitigate worst-case scenarios by ensuring that the pivot is chosen randomly, leading to expected running times that are consistently efficient.

Uploaded by

mpin364
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

Design and Analysis of Algorithms

Quicksort: Analysis
Quick Sort - Characteristics

● Sorts almost in “place”,


It does not require an additional array/memory.
● Very practical, average sort performance (with small constant factors)
But worst case
Quick Sort - The Principle

● To understand Quick Sort, let’s look at a high level description of the algorithm.
● A divide-and-conquer algorithm.
○ Divide: Partition array into 2 subarrays such that elements in the lower part
<= elements in the higher part.
○ Conquer: Recursively sort the 2 subarrays.
○ Combine: Trivial since sorting is done in place.
Partitioning
● Linear Time Partitioning Algorithm
● Partitioning is done around the pivot i i j j

element 17 12 6 19 23 8 5 10
i j
10 12 6 19 23 8 5 17

i j
10 5 6 19 23 8 12 17

j i
10 5 6 8 23 19 12 17

Time taken is
Quick Sort Algorithm

● Initial call Quicksort(A,1,length[A])


Analysis of Quicksort

● Assume that all input points are distinct.


● The running time depends on the distribution of the split.
Best Case
● If we are lucky, Partition splits the array evenly

Time taken
is
Worst Case
● One side of the partition has only one elements.
Worst Case

● When does the worst case appear?


○ Input is already sorted.
○ Input is reverse sorted.
● Same recurrence for the worst case of insertion sort.
● However, sorted input yields the best case for insertion sort.
Analysis of Quicksort
● Suppose the split is 1/10 : 9/10

n n

n/10 9n/10 n
log1/10n

log10/9n n/100 9n/100 9n/100 81n/100 n

1 81n/1000 729n/1000 n

1 n
An Average Case Scenario
● Suppose, we alternate lucky and unlucky cases
to get an average behaviour.

n n

1 n-1 (n-1)/2+1 (n-1)/2

(n-1)/2 (n-1)/2
An Average Case Scenario

● How can we make sure that we are usually lucky?


○ Partition around the middle (n/2th) element.
○ Partition around a random element (works well in practise).
● Randomised Algorithm
○ Running time is independent of the input ordering.
○ No specific input triggers worst-case behaviour.
○ The worst case is only determined by the output of the random-number
generator.
● Worst case running time of quicksort is
● Best case running time of quicksort is
● Expected running time of quicksort is
What does expected running time mean?

● The running time of quicksort does not depend on the input. It depends on the random
number provided by the generator.
● The average time taken over many different runs of the program would give us
expected time.
● Same as saying that we are taking average over all possible random numbers
sequences provided by the generator.
Thank you

You might also like