lOMoARcPSD|19990856

Unit-1 DAA Notes - daa unit 1 note

data structure (Dr. A.P.J. Abdul Kalam Technical University)

Studocu is not sponsored or endorsed by any college or university

Downloaded by Harsh Pandey ([email protected])
 Berman, Paul,= Algorithms=, Cengage Learning.
Aho, Hopcraft, Ullman, <The Design and Analysis of Computer Algorithms= Pearson

¯
¯

¯ The <Big White Book=

¯ Second edition: now <Smaller Green Book=
¯

lOMoARcPSD|19990856

NOTES (UNIT-I) Introduction

1.1 Algorithm
An algorithm is any well-defined computational procedure that takes some value, or set of
values, as input and produces some value, or set of values, as output. An algorithm is thus a
sequence of computational steps that transform the input into the output.
For example, given the input sequence {31, 41, 59, 26, 41, 58), a sorting algorithm returns as
output the sequence {26, 31, 41, 41, 58, 59}. Such an input sequence is called an instance of the
sorting problem. ,
Instance : An instance of a problem consists of the input needed to compute a solution to the
problem.
An algorithm is said to be correct if, for every input instance, it halts with the correct output.
There are two aspects of algorithmic performance:
• Time Downloaded by Harsh Pandey ([email protected])

- Instructions take time.

•
 lOMoARcPSD|19990856

- What kind of data structures can be used?

- How does choice of data structure affect the runtime?

1.1.1 Analysis of Algorithms

Analysis is performed with respect to a computational model
• We will usually use a generic uniprocessor random-access machine (RAM)
¯ All memory equally expensive to access
¯ No concurrent operations
¯ All reasonable instructions take unit time
o Except, of course, function calls
¯ Constant word size
Unless we are explicitly manipulating bits
Input Size:
• Time and space complexity
¯ This is generally a function of the input
size o E.g., sorting, multiplication
¯ How we characterize input size depends:
o Sorting: number of input items
o Multiplication: total number of bits
o Graph algorithms: number of nodes & edges
o Etc
Running Time:
• Number of primitive steps that are executed
¯ Except for time of executing a function call most statements roughly require the
same amount of time
o y=m*x+b
o c = 5 / 9 * (t - 32 ) o
z = f(x) + g(y)
• We can be more exact if need be
Analysis:
• Worst case
¯ Provides an upper bound on running time
¯ An absolute guarantee
• Average case
¯ Provides the expected running time
¯ Very useful, but treat with care: what is
<average=? o Random (equally likely) inputs
o Real-life inputs

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

1.1.2 Analyzing algorithm

Example: Insertion Sort:
InsertionSort(A, n) {
for i = 2 to n {
key = A[i]
j = i - 1;
while (j > 0) and (A[j] > key) {
A[j+1] = A[j]
j=j-1
}
A[j+1] = key
}

}
Analysis
Statement Effort
InsertionSort(A, n) {
for i = 2 to n { c1n
key = A[i] c2(n-1)
j = i - 1; c3(n-1)
while (j > 0) and (A[j] > key) { c4T
A[j+1] = A[j] c5(T-(n-1))
j=j-1 c6(T-(n-1))
} 0
A[j+1] = key c7(n-1)
} 0
}

T = t2 + t3 + … + tn where ti is number of while expression evaluations for the ith for loop
iteration
T(n) = c1 n + c2(n-1) + c3(n-1) + c4T + c5(T - (n-1)) + c6(T - (n-1)) + c7(n-1) = c8T + c9n + c10

Best case -- inner loop body never executed

ti = 1 ➔

= an-b = ÷(n)

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

T(n) is a linear function

Worst case -- inner loop body executed for all previous elements
ti = i ➔

= an2 +bn 3c= O(n2)

T(n) is a quadratic function
Average case: The <average case= is often roughly as bad as the worst case.

1.1.3 Designing algorithms

The divide and conquer approach
The divide-and-conquer paradigm involves three steps at each level of the recursion:
Divide the problem into a number of subproblems that are smaller instances of the same
problem.
Conquer the subproblems by solving them recursively. If the subproblem sizes are small
enough, however, just solve the subproblems in a straightforward manner.
Combine the solutions to the subproblems into the solution for the original problem.

1.2 Merge sort

The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively, it
operates as follows.
Divide: Divide the n-element sequence to be sorted into two subsequences of n=2 elements each.
Conquer: Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.
The key operation of the merge sort algorithm is the merging of two sorted sequences in the
<combine= step. We merge by calling an auxiliary procedure MERGE (A, p, q, r) where A is an
array and p, q, and r are indices into the array such that pf q < r. The procedure assumes that the
subarrays A (p…. q) and A (q+1……… r) are in sorted order. It merges them to form a single
sorted subarray that replaces the current subarray A (p …….r). Our MERGE procedure takes
time ÷(n), where n = r- p+1 is the total number of elements being merged.

MERGE(A, p, q, r)
1 n1 ← q - p + 1
2 n2 ← r - q

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

3 create arrays L[1……. n1 + 1] and R[1……… n2 + 1]

4 for i ← 1 to n1
5 do L[i] ← A[p + i - 1]
6 for j ← 1 to n2
7 do R[j] ← A[q + j]
8 L[n1 + 1] ← >
9 R[n2 + 1] ← >
10 i ← 1
11 j ← 1
12 for k ← p to r
13 do if L[i] f R[j]
14 then A[k] ← L[i]
15 i ← i + 1
16 else A[k] ← R[j]
17 j ← j + 1

Example:

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

Fig: The Merge procedure applies on given array and sort and combines the solution in recursive
iteration.

MERGE-SORT(A, p, r)
1 if p < r
2 then q ← (p + r)/2
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

1.2.1 Analysis of Merge-sort

When we have n > 1 elements, we break down the running time as follows.
Divide: The divide step just computes the middle of the subarray, which takes constant time.
Thus, D(n)=÷(1).
Conquer: We recursively solve two subproblems, each of size n/2, which contributes 2T(n/2) to
the running time.
Combine: We have already noted that the MERGE procedure on an n-element subarray takes
time ÷(n) and so C(n)=÷(n).
The recurrence for the worst-case running time T(n) of merge sort:

The solution for above recurrence is ÷ (n log n).

1.3 Growth of functions

The notations we use to describe the asymptotic running time of an algorithm are defined in
terms of functions whose domains are the set of natural numbers N=(0, 1, 2……). Such
notations are convenient for describing the worst-case running-time function T(n), which usually
is defined only on integer input sizes.

1.3.1 Asymptotic notations

1.3.1.1 Upper Bound Notation or O-notation
We say InsertionSort9s run time is O(n2). Properly we should say run time is in O(n2). Read O as
<Big-O= (you9ll also hear it as <order=)
In general a function f(n) is O(g(n)) if there exist positive constants c and n0 such that f(n) £ c ×
g(n) for all n ³ n0
Formally
O(g(n)) = { f(n): $ positive constants c and n0 such that f(n) £ c × g(n) " n ³ n0

Example. 1. functions in O(n2)

n2/ 1000, n1.9, n2, n2+n, 1000 n2+50n
2. Show 2n2 = O (n3)
0 f h(n) f cg(n) Definition of O(g(n))

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

2 3
0 f 2n f cn Substitute
3 2 3 3 3
0/n f 2n /n f cn /n Divide by n3
Determine c
0 f 2/n f c 2/n = 0
2/n maximum when n=1
0 f 2/1 f c = 2 Satisfied by c=2
Determine n0
0 f 2/ n0 f 2
0 f 2/2 f n0
0 f 1 f n0 = 1 Satisfied by n0=1
0 f 2n2 f 2n3 ∀ n g n0=1

If f(n) f cg(n), c > 0, ∀ n g n0 then f(n) ∈ O(g(n))

3. 1000n2 + 50n = O(n2)

0 f h(n) f cg(n)
0 f 1000n2 + 50n f cn2 Substitute
0/n2 f 1000 n2/ n2 + 50n/ n2 f c n2/ n2 Divide by n2
0 f 1000 + 50/n f c Note that 50/n → 0 as n → >
Greatest when n = 1
0 f 1000 + 50/1 = 1050 f c = 1050 Satisfied by c=1050
0 f 1000 + 50/n0 f 1050 Find n0 ∀ n g n0
-1000 f 50/ n0 f 50
-20 f 1/ n0 f 1
-20 n0 f 1 f n0 = 1 Satisfied by n0=1
0 f 1000 n2 + 50n f 1050 n2 ∀ n g n0=1, c=1050
If f(n) f cg(n), c > 0, ∀ n g n0 then f(n) ∈ O(g(n))

Big O Fact
A polynomial of degree k is O(nk)
Proof:
Suppose f(n) = bknk + bk-1nk-1 + … + b1n + b0
Let ai = | bi |
f(n)  aknk + ak-1nk-1 + … + a1n + a0
i
n
 n k
åai nk
 nk åai  cnk

1.3.1.2 Lower Bound Notation or Ω-notation

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

We say Insertion Sort9s run time is W(n). In general a function f(n) is W(g(n)) if $ positive
constants c and n0 such that 0 £ c×g(n) £ f(n) " n ³ n0

Proof: Suppose run time is an + b. Assume a and b are positive (what if b is negative?).
an £ an + b
Example. 1. Functions in Ω(n2)
n2/ 1000, n1.999, n2+n, 1000 n2+50n
2. n3 = Ω(n2) with c=1 and n0=1
0 f cg(n) f h(n)
0 f 1*12 = 1 f 1 = 13
0 f cg(n) f h(n)
0 f c n2 f n3
0/ n2 f c n2/ n2 f n3/ n2
0fcfn
0 f 1 f 1 with c=1 and n0=1 since n increases.

1.3.1.3 Asymptotic Tight Bound or -notation

A function f(n) is Q(g(n)) if $ positive constants c1, c2, and n0 such
that c1 g(n) £ f(n) £ c2 g(n) " n ³ n0

Theorem: f(n) is Q(g(n)) iff f(n) is both O(g(n)) and W(g(n))

Example . 1. Show that ½n2 - 3n ∈ Θ(n2)

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

Determine ∃ c1, c2, n0 positive constants such that:

c1 n2 f ½ n2 - 3n f c2 n2
c1 f ½ - 3/n f c2 Divide by n2
O: Determine c2 = ½
½ - 3/n f c2
as n → >, 3/n → 0
½ - 3/n = ½
therefore ½ f c2 or c2 = ½ ½ - 3/n maximum for as n → >
Ω: Determine c1 = 1/14
0 < c1 f ½ - 3/n ½ - 3/n > 0 minimum for n0 = 7
0 < c1 = ½ - 3/7 = 7/14 - 6/14 = 1/14
n0: Determine n0 = 7
c1 f ½ - 3/ n0 f c2
1/14 f ½ - 3/ n0 f ½
½n2-3n = Θ(n2)
c1=1/14, c2=1/2 and n
Θ: ½n2 - 3n ∈ Θ(n2) when c1 = 1/14, c2 = ½ and n0 = 7

1.3.1.4 Other Asymptotic Notations

o-notation: A function f(n) is o(g(n)) if $ positive constants c and n0 such that f(n) < c g(n) " n ³
n0
ω-notation: This notation is A function f(n) is w(g(n)) if $ positive constants c and n0 such that
c g(n) < f(n) " n ³ n0
Intuitively,
• o() is like <
• w() is like >
• Q() is like =
• W() is like ³
• O() is like £
•
1.4 Recurrences
Recurrences
A recurrence is an equation or inequality that describes a function in terms of its value on
smaller inputs. For example, the worst-case running time T (n) of the MERGE-SORT procedure
by the recurrence

ì c n=1
ï
ï

T (n) = í æ n ö
ï2T ç ÷ + cn n>1
ï
î è2ø

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

Whose solution is to be T (n)=O(n lg n).

1.4.1 Solving Recurrences: following methods are used to solve recurrences and find its
asymptotic performance
1. Substitution method
2. Recursion Tree
3. Master method
4. Iteration Method

1.4.1.1 The substitution method

This method is called <making a good guess method= and solving recurrences comprises two
steps:
1. Guess the form of the solution.
2. Use mathematical induction to find the constants and show that the solution
We can use the substitution method to establish either upper or lower bounds on a recurrence. As
an example, let us determine an upper bound on the recurrence
T(n) = 2T(ën/2û) + n
We guess that the solution is T(n)=O(n lg n). The substitution method requires us to prove T(n) f
c n lg n for an appropriate choice of the constant c > 0. We start by assuming that this bound
holds for all positive m < n, in particular for m = ën/2û, yielding T(ën/2û) =c(ën/2û) lg (ën/2û).
Substituting into the recurrence yields
T(n) f 2 c(ën/2û) lg (ën/2û)+ n
f cn lg (n/2) +n
= cn lg n _ cn lg 2 + n
f cn lg n _ cn + n
f cn lgn
where the last step holds as long as c g 1.
1.4.1.2 Changing variables:
Sometimes, a little algebraic manipulation can make an unknown recurrence similar to one you
have seen before. As an example, consider the recurrence

which looks difficult. We can simplify this recurrence, though, with a change of variables. For
convenience Renaming m= lg n yields
T(2m) = T(2m/2)+m
We can now rename S(m) = T(2m) to produce the new
recurrence S(m)= S (m/2) +m
The solution is to be S (m)= O (m lg m)
After replacing m= log n the solution becomes

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

T(n) = O(lg n lg lg n)

1.4.1.3 The recursion-tree method: Substitution method is not coming up with good guess.
Drawing out a recursion tree provides a method to devise a good guess. In a recursion tree, each
node represents the cost of a single subproblem somewhere in the set of recursive function
invocations. We sum the costs within each level of the tree to obtain a set of per-level costs, and
then we sum all the per-level costs to determine the total cost of all levels of the recursion.
For example, let us see how a recursion tree would provide a good guess for the recurrence
T(n)= 3T( n/4 ) + ÷(n2)
we create a recursion tree for the recurrence T(n)= 3T(n/4) + cn2, having written out the implied
constant coefficient c > 0.

Fig: Constructing a recursion tree for the recurrence T(n)= 3T(n/4) + cn2. Part (a) shows T (n),
which progressively expands in (b)–(d) to form the recursion tree. The fully expanded tree in
part (d) has height log4n (it has log4n +1 levels).

The above fig shows how we derive the recursion tree for T(n)= 3T(n/4) + cn2 .For convenience,
we assume that n is an exact power of 4 so that all subproblem sizes are integers. Part (a) of the
figure shows T(n), which we expand in part (b) into an equivalent tree representing the
recurrence. The cn2 term at the root represents the cost at the top level of recursion, and the three
subtrees of the root represent the costs incurred by the subproblems of size n=4. Part (c) shows

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

this process carried one step further by expanding each node with cost T(n/4) from part (b). The
cost for each of the three children of the root is c(n/42). We continue expanding each node in the
tree by breaking it into its constituent parts as determined by the recurrence.
Because subproblem sizes decrease by a factor of 4 each time the subproblem size for a node at
depth i is (n/4i). Thus for subproblem size at last level n=1 n/4i =1 then i = log4n and the tree has
log4n+1 levels. The cost of each node is derived by generalized term at depth i where i= 0, 1,
2…….log4n-1 by c (n/4i)2 . the total cost over all nodes at depth i, for i= 0, 1, 2…….log4n-1 is 3i
(n/4i )2 =(3/16)i cn2. The last level i.e. at depth log4n cost is 3log4n= nlog43 nodes each contributing
cost T(1), for a total cost nlog43 T(1) which is ÷(nlog43 ) since we assume T(1) is constant.
Now we add up the costs over all levels to determine the cost for the entire tree:

Thus, we have derived a guess of T(n)= O(n2). Now we can use the substitution method to verify
that our guess was correct, that is, T(n)= O(n2) is an upper bound for the recurrence T(n)= 3T(
n/4 ) + ÷(n2). We want to show that T(n)f dn2 for some constant d > 0. Using the same constant
c > 0 as before, we have

Where the last step holds as long as d = (16/13)c.

1.4.1.4 The master method

For divide and conquer algorithm, An algorithm that divides the problem of size n into a
subproblems, each of size n/b Let the cost of each stage (i.e., the work to divide the problem +
combine solved subproblems) be described by the function f(n), then, the Master Theorem gives
us a cookbook for the algorithm9s running time in the form of recurrence given below
T(n) = a T(n/b) + f(n)
Where ag1and b>1 are constants and f (n) is an asymptotically positive function.
1.4.1.4.1 The master theorem:
The master method depends on the following theorem.

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

Let ag1and b>1 be constants, let f (n) be a function, and let T(n) be defined on the nonnegative
integers by the recurrence
T(n) = a T(n/b) + f(n)
where we interpret n/b to mean either floor (n/b) or ceil (n/b). Then T(n) has the following
asymptotic bounds:
1. If f (n) = O(nlog a− ) for some constant ø>0 then T(n)= (nlog
b b
a

(
2. If f (n) =  nlogb a ) ). then T(n)= ÷(nlogba log n).
3. If f (n) = (nlog a+ ) for some constant ø>0 and if a T (n/b) fc f(n)(regularity function)
b

for some constant c<1 and all sufficiently large n then T(n)= ÷(f (n)).

In each of the three cases, we compare the function f (n) with the function nlogba. Intuitively, the
larger of the two functions determines the solution to the recurrence. In case 1the function nlogba
( )
is larger, solution is T(n)=  nlogb a . In case 3 function f(n) is larger, solution is T(n)= ÷(f (n)).
In case 2 both functions has same value, solution is T(n)= ÷(nlogba log n).

In the first case, not only must f(n) be smaller than n logba, it must be polynomially smaller. In
the third case, not only must f (n) be larger than nlogba , it also must be polynomially larger and
in addition satisfy the <regularity= condition that a T (n/b) fc f(n). An addition to that all three
cases do not cover all possibilities. Some function might be lies in between case 1 and 2 and
some other lies in between case 2 and 3 because the comparison is not polynomial larger or
smaller and in case 3 the regularity condition fails.
Example. 1. . The given recurrence is
T(n) = 9T(n/3) + n
Sol: a=9, b=3, f(n) = n
nlogb a = nlog3 9 = (n2)
Since f(n) = O(nlog3 9 - ), where =1, case 1 applies:

(
T (n) =  nlogb a ) when f (n) = O(nlog a− ) b

Thus the solution is T(n) = (n2)

2. T(n)= T(2n/3)+1
in which a = 1, b= 3/2, f(n)= 1, and nlogba = nlog3/2 =n0 = 1. Case 2
applies, since f (n)=  (nlogba )= (1) and thus the solution to the recurrence is T(n) =(lg n)
3. The master method does not apply to the recurrence:
T(n)= 2T(n/2) +n log n
Sol: a=2, b=2, f(n)= n log n , nlogba=nlog 2=n
Since f(n) is larger than nlogba you mistakenly apply case 3 but the f(n) is larger but not
polynomialy larger. The ratio f(n)/ nlogb a= log n is asymptotically less than nø for any positive
constant ø. Consequently, the recurrence falls into the gap between case 2 and case 3.

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

1.4.1.5 Iteration method

Another option is the <iteration method= which expand the recurrence by using iterative
equations, work some algebra to express as a summation and finally evaluate the summation. It9s
a iterative procedure which recursively used and prorogate to a final single value.
For example

1.5 Heap sort

A heap can be seen as a nearly binary tree:

An array A that represents a heap is an object with two attributes: A.length, which (as usual)
gives the number of elements in the array, and A.heap-size, which represents how many
elements in the heap are stored within array A. That is, although A (1……..A.length) may

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

contain numbers, only the elements in A(1……….A.heap-size), where 0f A.heap-sizef

A.length, are valid elements of the heap. The root of the tree is A(1), and given the index i of a
node, we can easily compute the indices of its parent, left child, and right child:

Parent(i)
return floor (i/2)

Left(i)
return 2i

Right(i)
return 2i+1

There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the
nodes satisfy a heap property, the specifics of which depend on the kind of heap. In a max-heap,
the max-heap property is that for every node i other than the root,
A[parent(i)]gA[i]
That is the value of a node is lesser or equal to parent.

A min-heap is organized in the opposite way; the min-heap property is that for every node i other
than the root,
A[parent(i)]fA[i]
For the heapsort algorithm, we use max-heaps.

1.5.1 Maintaining the heap property:

1.5.1.1 MAX-HEAPIFY(A, i)
{
l = Left(i); r = Right(i);
if (l <= A.heap-size && A[l] > A[i])
largest = l;
else
largest = i;
if (r <= A.heap-size && A[r] > A[largest])
largest = r;
if (largest != i)
exchange A[i] with A[largest];
MAX-HEAPIFY(A, largest);
}

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

Figure: The action of MAX-HEAPIFY(A, 2), where heap-size[A] = 10. (a) The initial
configuration, with A[2] at node i = 2 violating the max-heap property since it is not larger than
both children. The max-heap property is restored for node 2 in (b) by exchanging A[2] with A[4],
which destroys the max-heap property for node 4. The recursive call MAXHEAPIFY( A, 4) now
has i = 4. After swapping A[4] with A[9], as shown in (c), node 4 is fixed up, and the recursive
call MAX-HEAPIFY(A, 9) yields no further change to the data structure.

1.5.1.2 Complexity
We can describe the running time of MAX-HEAPIFY by the
recurrence T(n)f2T(n/3)+÷(1)
The solution to this recurrence, by case 2 of the master theorem is T(n)= O(lg n)

1.5.2 Building a heap:

We can build a heap in a bottom-up manner by running Heapify() on successive subarrays. For
array of length n, all elements in range A[ën/2û + 1 .. n] are heaps.

1.5.2.1 BUILD-MAX-HEAP(A)
1. A.heap-size = A.length
2. for i = ëlength[A]/2û downto 1
3. MAX-HEAPIFY(A, i)
The time required by MAX-HEAPIFY when called on a node of height h is O(h), the running
time of above algorithm is O(n).

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

Figure: The operation of BUILD-MAX-HEAP, showing the data structure before the call to
MAX-HEAPIFY in line 3 of BUILD-MAX-HEAP. (a) A 10- element input array A and the
binary tree it represents. The figure shows that the loop index i refers to node 5 before the call
MAX-HEAPIFY(A, i). (b) The data structure that results. The loop index i for the next iteration
refers to node 4. (c)-(e) Subsequent iterations of the for loop in BUILD-MAXHEAP. Observe
that whenever MAX-HEAPIFY is called on a node, the two subtrees of that node are both max-
heaps. (f) The max-heap after BUILD-MAX-HEAP finishes.

1.5.3 The heapsort Algorithm

The heapsort algorithm starts to build max heap by using procedure BUILD-MAX -HEAP and
then picks the root element which has the higher value. Then remove root value from the tree and
built again it max heap. This process performs up to last value and sorted array is formed.

1.5.3.1 HEAPSORT(A)
1. BUILD-MAX-HEAP(A)
2. for i = length(A) downto 2
3. Exchange (A[1] with A[i]);
4. A.heap-size= A.heap-size -1;
5. MAX-HEAPIFY (A, 1);

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

Figure: The operation of HEAPSORT. (a) The max-heap data structure just after it has been built
by BUILD -MAX-HEAP. (b)-(j) The max-heap just after each call of MAXHEAPIFY in line 5.
The value of i at that time is shown. Only lightly shaded nodes remain in the heap. (k) The
resulting sorted array A.

1.6 Quick sort

Quicksort is also a divide-and-conquer algorithm. An unsorted array A taken in which p and r is
the lower bound and upper bound of the elements respectivally.
Divide:The array A[p..r] is partitioned into two non-empty subarrays A[p..q] and A[q+1..r].
Invariant: All elements in A[p..q] are less than all elements in A[q+1..r].
Conquer: The subarrays are recursively sorted by calls to quicksort.
Combine: Unlike merge sort, no combining step: two subarrays form an already-sorted array.

The following procedure implements quicksort:

QUICKSORT(A, p, r)
1. if (p < r)
2. q = PARTITION(A, p, r)

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

3. QUICKSORT(A, p, q)
4. QUICKSORT(A, q+1, r)
To sort an entire array A, the initial call is QUICKSORT (A, 1, A.length).

Partitioning the array:

The key to the algorithm is the PARTITION procedure, which rearranges the subarray A(p….r)
in place.
PARTITION(A, p, r)
1 x ← A[r]
2i←p-1
3 for j ← p to r - 1
4 do if A[j] f x
5 then i ← i + 1
6 exchange A[i] ↔ A[j]
7 exchange A[i + 1] ↔ A[r]
8 return i + 1

Figure: The operation of PARTITION on a sample array. Lightly shaded array elements are all in
the first partition with values no greater than x. Heavily shaded elements are in the second
partition with values greater than x. The unshaded elements have not yet been put in one of the
first two partitions, and the final white element is the pivot. (a) The initial array and variable
settings. None of the elements have been placed in either of the first two partitions. (b) The value
2 is "swapped with itself" and put in the partition of smaller values. (c)-(d) The values 8 and 7
are added to the partition of larger values. (e) The values 1 and 8 are swapped, and the smaller
partition Grows. (f) The values 3 and 8 are swapped, and the smaller partition grows. (g)-(h) The

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

larger partition grows to include 5 and 6 and the loop terminates. (i) In lines 7-8, the pivot
element is swapped so that it lies between the two par titions.

1.6.1 Performance of Quicksort:

The running time of quicksort depends on whether the partitioning is balanced or unbalanced,
which in turn depends on which elements are used for partitioning.

1.6.1.1 Worst Case Partitioning:

The worst-case behavior for quicksort occurs when the partitioning routine produces one
subproblem with n - 1 elements and one with 0 elements. The recurrence for the running time is
T(n)=T(n-1)+T(0) + (1)= (n2) i.e T(n) = (n2)

1.6.1.2 Best case partitioning:

in the best case it partition the array into equal sub arrays. The recurrence for balanced
portioning is
T(n) = 2T(n/2) + (n)= (n lg n) i.e. T(n) = (n lg n)

1.7 Shell sort

Shellsort, also known as Shell sort or Shell's method, is an in-place comparison sort. It can be
seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion
(insertion sort).The method starts by sorting elements far apart from each other and progressively
reducing the gap between them.

# Sort an array a[0...n-1].

gaps = [701, 301, 132, 57, 23, 10, 4, 1]

# Start with the largest gap and work down to a gap of 1

foreach (gap in gaps)
{
# Do a gapped insertion sort for this gap size.
# The first gap elements a[0..gap-1] are already in gapped order
# keep adding one more element until the entire array is gap
sorted for (i = gap; i < n; i += 1)
{
# add a[i] to the elements that have been gap sorted
# save a[i] in temp and make a hole at position i
temp = a[i]
# shift earlier gap-sorted elements up until the correct location for a[i] is
found for (j = i; j >= gap and a[j - gap] > temp; j -= gap)

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

{
a[j] = a[j - gap]
}
# put temp (the original a[i]) in its correct
location a[j] = temp
}

An example run of Shellsort with gaps 5, 3 and 1 is shown below

The first pass, 5-sorting, performs insertion sort on separate subarrays (a1, a6, a11), (a2, a7, a12), (a3,
a8), (a4, a9), (a5, a10). For instance, it changes the subarray (a1, a6 , a11) from (62, 17, 25) to (17,
25, 62). The next pass, 3-sorting, performs insertion sort on the subarrays (a1, a4, a7, a10),
(a2, a5, a8, a11), (a3, a6, a9, a12). The last pass, 1-sorting, is an ordinary insertion sort of the
entire array (a1,..., a12).
The complexity of this algorithm is O (n1.25).

1.8 Sorting in linear time

The algorithms that can sort n numbers in O(n lg n) time is Merge sort and heap sort and achieve
this upper bound in the worst case; Quick sort achieves it on average. These algorithms share an
interesting property: the sorted order they determine is based only on comparisons between the
input elements. We call such sorting algorithms comparison sorts. All the sorting algorithms
introduced thus far are comparison sorts.
We shall prove that any comparison sort must make Θ(n lg n) comparisons in the worst case to
sort n elements. Thus, merge sort and heap sort are asymptotically optimal, and no comparison
sort exists that is faster by more than a constant factor.
Here three sorting algorithms-counting sort, radix sort, and bucket sort-that run in linear time.
These algorithms use operations other than comparisons to determine the sorted order.
Consequently, the Θ(n lg n) lower bound does not apply to them

1.8.1 Counting sort

Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for
some integer k. When k = O(n), the sort runs in ‚÷ (n) time.

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

1.8.1.1 The algorithm:

1. Input: A[1..n], where A[j]  {1, 2, 3, …, k}
2. Output: B[1..n], sorted (notice: not sorting in place)
3. Also: Array C[1..k] for auxiliary storage

COUNTING-SORT(A, B, k)
1 for i ← 0 to k
2 do C[i] ← 0
3 for j ← 1 to length[A]
4 do C[A[j]] ← C[A[j]] + 1
5 //C[i] now contains the number of elements equal to i.
6 for i ← 1 to k
7 do C[i] ← C[i] + C[i - 1]
8 //C[i] now contains the number of elements less than or equal to i.
9 for j ← length[A] downto 1
10 do B[C[A[j]]] ← A[j]
11 C[A[j]] ← C[A[j]] 3 1

1.8.1.2 Running time of Counting Sort

The for loop of lines 1-2 takes time Θ(k), the for loop of lines 3-4 takes time Θ(n), the for loop of
lines 6-7 takes time Θ(k), and the for loop of lines 9-11 takes time Θ(n). Thus, the overall time is
Θ(k+n). In practice, we usually use counting sort when we have k = O(n), in which case the
running time is Θ(n).
Example:

Figure: The operation of COUNTING-SORT on an input array A[1,…..., 8], where each element
of A is a nonnegative integer no larger than k = 5. (a) The array A and the auxiliary array C after
line 4. (b) The array C after line 7. (c)-(e) The output array B and the auxiliary array C after one,

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

two, and three iterations of the loop in lines 9-11, respectively. Only the lightly shaded elements
of array B have been filled in. (f) The final sorted output array B.

1.8.2 Radix Sort

Radix sort solves the problem of card sorting4by sorting on the least significant digit first. The
algorithm then combines the cards into a single deck, with the cards in the 0 bin preceding the
cards in the 1 bin preceding the cards in the 2 bin, and so on. The process continues until the
cards have been sorted on all d digits. Only d passes through the deck are required to sort. The
algorithm is
RadixSort(A, d)
for i=1 to d
StableSort(A) on digit i
Given n d-digit numbers in which each digit can take on up to k possible values,
RADIXSORT correctly sorts these numbers in Θ(d(n + k)) time.
Example:

Figure: The operation of radix sort on a list of seven 3-digit numbers. The leftmost column is the
input. The remaining columns show the list after successive sorts on increasingly significant digit
positions. Shading indicates the digit position sorted on to produce each list from the previous
one.

1.8.3 Bucket sort

Assumption: input is n reals from [0, 1)
Basic idea: Create n linked lists (buckets) to divide interval [0,1) into subintervals of size 1/n.
Add each input element to appropriate bucket and sort buckets with insertion sort. Uniform input
distribution → O(1) bucket size. Therefore the expected total time is O(n). These ideas will
return when we study hash tables.
BUCKET-SORT(A)
1 n ← length[A]
2 for i ← 1 to n
3 do insert A[i] into list
4 for i ← 0 to n - 1
5 do sort list B[i] with insertion sort
6 concatenate the lists B[0], B[1], . . ., B[n - 1] together in order

Downloaded by Harsh Pandey ([email protected])

 lOMoARcPSD|19990856

Example:

Figure: The operation of BUCKET-SORT for n= 10. (a) The input array A(1……..10). (b) The
array B(0…… 9) of sorted lists (buckets) after line 8 of the algorithm. Bucket i holds values in
the half-open interval [i/10,.i + 1/10). The sorted output consists of a concatenation in order of
the lists B[0], B[1]…….B[9]
To analyze the running time, observe that all lines except line 5 take O (n) time in the worst case.

Downloaded by Harsh Pandey ([email protected])