Scribd
Upload
2K views12 pages

Quicksort Complexity and Analysis

Quicksort is a divide-and-conquer sorting algorithm that works by recursively dividing an array into two subarrays of smaller size, sorting each subarray, and merging the sorted subarrays back together. It has an average time complexity of O(N log N) but a worst-case time complexity of O(N^2). The key steps are picking a pivot element and partitioning the array into subarrays based on element values relative to the pivot. A random pivot is generally used to avoid worst-case behavior on presorted inputs. Insertion sort is used for small subarrays. Quicksort is typically faster than mergesort due to its simpler in-place partitioning versus mergesort's extra data movement.

Uploaded by

sailaja002
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
2K views12 pages

Quicksort Complexity and Analysis

Quicksort is a divide-and-conquer sorting algorithm that works by recursively dividing an array into two subarrays of smaller size, sorting each subarray, and merging the sorted subarrays back together. It has an average time complexity of O(N log N) but a worst-case time complexity of O(N^2). The key steps are picking a pivot element and partitioning the array into subarrays based on element values relative to the pivot. A random pivot is generally used to avoid worst-case behavior on presorted inputs. Insertion sort is used for small subarrays. Quicksort is typically faster than mergesort due to its simpler in-place partitioning versus mergesort's extra data movement.

Uploaded by

sailaja002
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 12

Quicksort

By Ch.Sailaja

Introduction
Fastest

known sorting algorithm in practice Average case: O(N log N) (we dont prove it) Worst case: O(N2)

But, the worst case seldom happens.

Another

divide-and-conquer recursive algorithm, like mergesort

Quicksort

Divide step:

Pick any element (pivot) v in S Partition S {v} into two disjoint groups S1 = {x S {v} | x <= v} S2 = {x S {v} | x v}

Conquer step: recursively sort S1 and S2 v Combine step: the sorted S1 (by the time returned from recursion), followed by v, followed by the sorted S2 (i.e., nothing extra needs to be done) S1 S2

To simplify, we may assume that we dont have repetitive elements, So to ignore the equality case!

Two key steps


How

to pick a pivot? to partition?

How

Pick a pivot

Use the first element as pivot

if the input is random, ok if the input is presorted (or in reverse order)


all

the elements go into S2 (or S1) this happens consistently throughout the recursive calls Results in O(n2) behavior (Analyze this case later)

Choose the pivot randomly


generally safe random pivot would consistently provide a poor partition and can be expensive does not reduce the average running time of the rest of the algorithm.

Small arrays
For

very small arrays, quicksort does not perform as well as insertion sort
how small depends on many factors, such as the time spent making a recursive call, the compiler, etc

Do

not use quicksort recursively for small arrays


Instead, use a sorting algorithm that is efficient for small arrays, such as insertion sort

A practical implementation
Choose pivot

Partitioning

Recursion For small arrays

Quicksort Analysis
Assumptions:

A random pivot (no median-of-three partitioning) No cutoff for small arrays

Running

time

pivot selection: constant time, i.e. O(1) partitioning: linear time, i.e. O(N) running time of the two recursive calls

T(N)=T(i)+T(N-i-1)+cN

where c is a constant

i: number of elements in S1

Worst-Case Analysis
What

will be the worst case?

The pivot is the smallest element, all the time Partition is always unbalanced

10

Best-case Analysis
What

will be the best case?

Partition is perfectly balanced. Pivot is always in the middle (median of the array)

11

Average-Case Analysis
Assume

Each of the sizes for S1 is equally likely

This

assumption is valid for our pivoting (median-of-three) strategy On average, the running time is O(N log N) (covered in comp271)

12

Quicksort is faster than Mergesort


Both quicksort and mergesort take O(N log N) in the average case. Why is quicksort faster than mergesort?

The inner loop consists of an increment/decrement (by 1, which is fast), a test and a jump. There is no extra juggling as in mergesort.

inner loop

You might also like