Theory for
Algorithms
Lecture 5
Sorting–2
Sorting
Algorithm - 2
Divide and Conquer
paradigm
• A common approach to solving a
problem is to partition the problem
into smaller parts, find solutions for the
parts, and then combine the solutions
for the parts into a solution for the
whole.
• This approach, especially when used
recursively, often yields efficient
solutions to problems in which the
sub- problems are smaller versions
of the original problem.
Divide and Conquer
Recursive in structure
Divide the problem into sub-problems that are similar
to the original but smaller in size
Conquer the sub-problems by solving them recursively.
If they are small enough, just solve them in a
straightforward manner.
Combine the solutions to create a solution to the
original problem
In most algorithms, either the divide or the combine
step is trivial
An Example: Merge Sort
Sorting • decreasing order.
Problem: • Divide: Divide the n-element sequence to be
sorted
Sort a • into two subsequences of n/2 elements each
• Conquer:Sort the two subsequences
sequence recursively using
• merge sort.
or n • Combine: Merge the two sorted
subsequences to
elements • produce the sorted answer.
into non-
Merge Sort – Example
Original Sequence Sorted Sequence
18 26 32 6 43 15 9 1 1 6 9 15 18 26 32 43
18 26 32 6 43 15 9 1 6 18 26 32 1 9 15 43
43
18 26 32
18 2626 32 6 43 15 9 1 26
18 26 6 32 15 43 1 9
15
18 26 32 6 43 15 99 11 18 26 32 6 43 15 9 1
26 32 15 18 26
43
32
18 26 32 6 43 15 99 1
Merging Two sorted Arrays
Merge Sort
Least number of comparisons occur if each entry in the left
subarray is less than all the entries in the right subarray
The number of comparisons may be as high as (n-1)
To merge two sorted arrays n1 and n2 (n=n1+n2) the
number of comparisons is at least n1 and at most (n-1)
Merge Sort
Analysis of
Merge Sort Running time T(n) of Merge Sort:
Divide: computing the middle takes O(1)
Conquer: solving 2 subproblems takes 2T(n/2)
Combine: merging n elements takes O(n)
Total:
T(n) = O(1) if n = 1
T(n) = 2T(n/2) + O(n) if n > 1
T(n) = O(n lg n)
p: Pivot (start element)
q: last element
x:Pivot value
i: Boundary between
the elements less than
pivot and greater
than pivot
j : Boundary between
the partitioned and
unpartitioned part
From p+1
till q
Swap if A(j) less than
pivot
Running time analysis
Worst-Case
(Data is sorted already)
„When the pivot is the smallest (or largest) element at
partitioning on a block of size n, the result yields one empty
sub-block, one element (pivot) in the “correct” place, and one
sub-block of size (n-1)
„Recurrence Equation:
Solution: O(n2)
Worse than Mergesort!!!
Running time analysis
Best case:
„The pivot is in the
middle (median) (at
each partition
step), i.e. after each
partitioning, on a
block of size n, the
result
yields two sub-blocks of approximately equal size and
the pivot element in the “middle” position
„Recurrence Equation becomes
Solution: O(n logn)
Comparable to Mergesort!!
Running time analysis
Best-Case
O(n logn)
Quick Sort vs Merge Sort
For simplicity, consider the data in the range
•0 to .9
•Input data: 2 ,5 ,7 ,2 ,1 ,4 ,1
Take a count array to store the count of each unique
•object .
•Index: 0 1 2 3 4 5 6 7 8 9
• Count: 0 2 2 0 1 1 0 1 0 0
Modify the count array such that each element at each
•index stores the sum of previous counts.
•Index: 0123456789
•Count: 0 2 4 4 5 6 6 7 7 7
•The modified count array indicates the position of each
•object in the output sequence.
Output each object from the input
sequence followed by decreasing its
count by .1
Process the input data: ,7 ,2 ,1 ,4
1 fo noitisoP .2 ,5is ,1
.2
Put data 1 at index 2 in output.
Decrease count by 1 to place next data
1 at an index 1 smaller than this
index .
Loop 1: C=0 …………………….……….. K …..
Loop 2: A
Loop 3: Accumulate C …….….….. K Range of Elements
Loop 4: A CC …………………..
B …... nN ……… Number of Elements
N=5
K=4
Loop 1
Loop 2: A C
Loop 3: Accumulate C
Loop 4: A C B
J=4 C((A(4))=C(4)=5
A(4)=4
B(5)=4
Analysis
Name Best Average Wo rst
Quicksort
Merge sort
Heapsort
Inserti on sort
Introsort
Selec ti o n sort
Timsort
B u bb l e sort
Binary tree sort
Sm o o ths o rt
Strand sort
Cocktail sort
C o m b sort
