Quick Sort
B. Tech-CSE, Semester: Vth
Course: ADA
Learning Objectives
Introduction
Pivot selection
Algorithm Quick-sort
Complexity analysis
Characteristics
Summary
2
Introduction
• Quick sort is a highly efficient sorting algorithm.
• It follows divide and conquer algorithm.
• Quicksort partitions an array and then calls itself
recursively twice to sort the two resulting subarrays
• In Quicksort all the real work happens in the divide step.
In fact, the combine step in quicksort does absolutely
nothing.
• It picks an element as pivot and partitions the given array
around the picked pivot.
3
Pivot Selection
There are four possibilities where we can
choose the pivot element.
•Pick first element as pivot.
•Pick last element as pivot
•Pick a random element as pivot.
•Pick median as pivot.
4
Introduction
On the basis of Divide and conquer approach, quicksort algorithm can
be explained as [1]:
•Divide
The array is divided into subparts taking pivot as the partitioning point.
The elements smaller than the pivot are placed to the left of the pivot
and the elements greater than the pivot are placed to the right.
•Conquer
The left and the right subparts are again partitioned using the by
selecting pivot elements for them. This can be achieved by recursively
passing the subparts into the algorithm.
•Combine
This step does not play a significant role in quicksort. The array is
already sorted at the end of the conquer step.
5
Quicksort
Sort a collection of n items into increasing order
– Algorithm steps:
• Break the list into 2 pieces based on a pivot
– The pivot is usually the first item in the list
• All items smaller than the pivot go in the left and all items
larger go in the right
• Sort each piece (recursion again)
• Combine the results together
Quicksort
Following are the basic steps [2]:
•Select a pivot (partitioning element) – here, the first
element
•Rearrange the list so that all the elements in the first s
positions are smaller than or equal to the pivot and all the
elements in the remaining n-s positions are larger than or
equal to the pivot
p
A[i]p A[i]p
•Exchange the pivot with the last element in the first (i.e., )
subarray — the pivot is now in its final position
•Sort the two subarrays recursively
Algorithm Quick-sort
The quick sort algorithm is as follows [2]:
Complexity analysis
time in the worst case:
(n-1)+(n-2)+...+1 = n(n-1) = O(n2)
2
time in the best case:
In each partition, the problem is always
divided into two sub-problems with almost
equal size.
n
n
2 ×2 = n
log2n n ×4 = n
4
.
..
... ...
Analysis of Quicksort
T(n): time required for sorting n elements
T(n)≦ cn+2T(n/2), for some constant c.
≦ cn+2(c ． n/2 + 2T(n/4))
≦ 2cn + 4T(n/4)
.
..
≦ cnlog2n + nT(1) = O(nlogn)
time in the average case: random arrays — Θ(n log n)
Example
Ex 1. 50, 23, 9, 18, 61, 32
Ex 2. 10, 70, 30, 80, 40, 45, 65
How will partition the array?
Characteristics
• Improvements:
– better pivot selection
– switch to insertion sort on small sub-files
– elimination of recursion
• Quicksort is considered the method of choice for internal
sorting of large files (n ≥ 10000)
References
[1] https://www.programiz.com
[2] A. Levitin “Introduction to the Design & Analysis of
Algorithms,” 3rd ed., Ch. 5 ©2012 Pearson Education, Inc.
Upper Saddle River, NJ. All Rights Reserved.
Summary
• QuickSort is a Divide and Conquer algorithm.
• It picks an element as pivot and partitions the given
array around the picked pivot.
• There are many different versions of quickSort that
pick pivot in different ways.
Always pick first element as pivot.
Always pick last element as pivot (implemented below)
Pick a random element as pivot.
Pick median as pivot.
14
