Data Structure and Algorithm Using Java

Table of Content
• AIM
* Classification of Sorting Methods,
* Bubble Sort,
* Selection Sort,
* Insertion Sort,
* Quick Sort,
* Merge Sort,
* Heap Sort
* Radix Sort,
* Classification of Searching,
* Linear Search, Binary Search,
* Hashing Functions – Division Reminder, Mid Square Method, Folding Method;
* Collision Resolution Techniques.
* String search and matching.
CHAPTER 4

Sorting and Searching

Sorting
• Sorting takes an unordered
collection and makes it an ordered
one.
1 2 3 4 5 6

77 42 35 12 101 5

1 2 3 4 5 6

5 12 35 42 77 101
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 6 2

Largest

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Comparison

Data Movement

Sorted
Selection Sort

5 1 3 4 2 6

Largest

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Largest

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Largest

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

2 1 3 4 5 6

Largest

Comparison

Data Movement

Sorted
Selection Sort

1 2 3 4 5 6

Comparison

Data Movement

Sorted
Selection Sort

1 2 3 4 5 6
DONE!
Comparison

Data Movement

Sorted
Bubble Sort
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

77 42 35 12 101 5
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 Swap42
77 77 35 12 101 5
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 7735 Swap35
77 12 101 5
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 35 12 Swap12
77 77 101 5
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 35 12 77 101 5

No need to swap
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 35 12 77 5 Swap 101
101 5
"Bubbling Up" the Largest
Element
• Traverse a collection of elements
• Move from the front to the end
• “Bubble” the largest value to the end using pair-wise
comparisons and swapping

1 2 3 4 5 6

42 35 12 77 5 101

Largest value correctly placed

The “Bubble Up” Algorithm
index = 0
last_index = n – 1

loop
exitif(index > last_index)
if(A[index] > A[index + 1]) then
Swap(A[index], A[index + 1])
endif
index = index + 1
endloop
 LB

No, Swap isn’t built in.

Procedure Swap(a, b isoftype in/out Num)
t isoftype Num
t = a
a = b
b = t
endprocedure // Swap
Items of Interest
• Notice that only the largest value is
correctly placed
• All other values are still out of order
• So we need to repeat this process

1 2 3 4 5 6

42 35 12 77 5 101

Largest value correctly placed

Repeat “Bubble Up”
How Many Times?
• If we have N elements…

• And if each time we bubble an

element, we place it in its correct
location…

• Then we repeat the “bubble up”

process N – 1 times.

• This guarantees we’ll correctly

place all N elements.
“Bubbling” All the Elements
1 2 3 4 5 6
42 35 12 77 5 101

1 2 3 4 5 6
35 12 42 5 77 101

1 2 3 4 5 6
N-1

12 35 5 42 77 101

1 2 3 4 5 6
12 5 35 42 77 101

1 2 3 4 5 6
5 12 35 42 77 101
Reducing the Number of
Comparisons
1 2 3 4 5 6
77 42 35 12 101 5
1 2 3 4 5 6
42 35 12 77 5 101

1 2 3 4 5 6
35 12 42 5 77 101

1 2 3 4 5 6
12 35 5 42 77 101

1 2 3 4 5 6
12 5 35 42 77 101
Reducing the Number
of Comparisons
• On the Nth “bubble up”, we only
need to
do MAX-N comparisons.

• For example:
• This is the 4th “bubble up”
• MAX is 6
•1 Thus
2
we have
3
2 comparisons
4 5 6
to do
12 35 5 42 77 101
Putting It All
Together
N is … // Size of Array

Arr_Type definesa Array[1..N] of Num

Procedure Swap(n1, n2 isoftype in/out Num)

temp isoftype Num
temp = n1
n1 = n2
n2 = temp
endprocedure // Swap
procedure Bubblesort(A isoftype in/out Arr_Type)
to_do, index isoftype Num
to_do = N – 1

loop
exitif(to_do == 0)
index = 0
loop
exitif(index > to_do)

Outer loop
Inner loop
if(A[index] > A[index + 1]) then
Swap(A[index], A[index + 1])
endif
index = index + 1
endloop
to_do = to_do - 1
endloop
endprocedure // Bubblesort
Already Sorted Collections?
• What if the collection was already
sorted?
• What if only a few elements were
out of place and after a couple of
“bubble ups,” the collection was
sorted?

1 2 3 4 5 6
• We want to be able to detect this
42 77 101
and5 “stop
12 35
early”!
Using a Boolean “Flag”
• We can use a boolean variable to determine if any
swapping occurred during the “bubble up.”

• If no swapping occurred, then we know that the

collection is already sorted!

• This boolean “flag” needs to be reset after each

“bubble up.”
did_swap isoftype Boolean
did_swap = true

loop
exitif ((to_do == 0) OR NOT(did_swap))
index = 0
did_swap = false
loop
exitif(index > to_do)
if(A[index] > A[index + 1]) then
Swap(A[index], A[index + 1])
did_swap = true
endif
index = index + 1
endloop
to_do = to_do - 1
endloop
An Animated Example
N 8 did_swap true

to_do 7

index

98 23 45 14 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap false

to_do 7

index 1

98 23 45 14 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap false

to_do 7

index 1

Swap

98 23 45 14 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 1

Swap

23 98 45 14 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 2

23 98 45 14 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 2

Swap

23 98 45 14 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 2

Swap

23 45 98 14 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 3

23 45 98 14 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 3

Swap

23 45 98 14 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 3

Swap

23 45 14 98 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 4

23 45 14 98 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 4

Swap

23 45 14 98 6 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 4

Swap

23 45 14 6 98 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 5

23 45 14 6 98 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 5

Swap

23 45 14 6 98 67 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 5

Swap

23 45 14 6 67 98 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 6

23 45 14 6 67 98 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 6

Swap

23 45 14 6 67 98 33 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 6

Swap

23 45 14 6 67 33 98 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 7

23 45 14 6 67 33 98 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 7

Swap

23 45 14 6 67 33 98 42

1 2 3 4 5 6 7 8
An Animated Example
N 8 did_swap true

to_do 7

index 7

Swap

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
After First Pass of Outer Loop
N 8 did_swap true

to_do 7

index 8 Finished first “Bubble Up”

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap false

to_do 6

index 1

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap false

to_do 6

index 1

No Swap

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap false

to_do 6

index 2

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap false

to_do 6

index 2

Swap

23 45 14 6 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 2

Swap

23 14 45 6 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 3

23 14 45 6 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 3

Swap

23 14 45 6 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 3

Swap

23 14 6 45 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 4

23 14 6 45 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 4

No Swap

23 14 6 45 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 5

23 14 6 45 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 5

Swap

23 14 6 45 67 33 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 5

Swap

23 14 6 45 33 67 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 6

23 14 6 45 33 67 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 6

Swap

23 14 6 45 33 67 42 98

1 2 3 4 5 6 7 8
The Second “Bubble Up”
N 8 did_swap true

to_do 6

index 6

Swap

23 14 6 45 33 42 67 98

1 2 3 4 5 6 7 8
After Second Pass of Outer
Loop
N 8 did_swap true

to_do 6

index 7 Finished second “Bubble Up”

23 14 6 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap false

to_do 5

index 1

23 14 6 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap false

to_do 5

index 1

Swap

23 14 6 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 1

Swap

14 23 6 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 2

14 23 6 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 2

Swap

14 23 6 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 2

Swap

14 6 23 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 3

14 6 23 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 3

No Swap

14 6 23 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 4

14 6 23 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 4

Swap

14 6 23 45 33 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 4

Swap

14 6 23 33 45 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 5

14 6 23 33 45 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 5

Swap

14 6 23 33 45 42 67 98

1 2 3 4 5 6 7 8
The Third “Bubble Up”
N 8 did_swap true

to_do 5

index 5

Swap

14 6 23 33 42 45 67 98

1 2 3 4 5 6 7 8
After Third Pass of Outer
Loop
N 8 did_swap true

to_do 5

index 6 Finished third “Bubble Up”

14 6 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fourth “Bubble Up”
N 8 did_swap false

to_do 4

index 1

14 6 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fourth “Bubble Up”
N 8 did_swap false

to_do 4

index 1

Swap

14 6 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fourth “Bubble Up”
N 8 did_swap true

to_do 4

index 1

Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fourth “Bubble Up”
N 8 did_swap true

to_do 4

index 2

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fourth “Bubble Up”
N 8 did_swap true

to_do 4

index 2

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fourth “Bubble Up”
N 8 did_swap true

to_do 4

index 3

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fourth “Bubble Up”
N 8 did_swap true

to_do 4

index 3

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fourth “Bubble Up”
N 8 did_swap true

to_do 4

index 4

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fourth “Bubble Up”
N 8 did_swap true

to_do 4

index 4

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
After Fourth Pass of Outer
Loop
N 8 did_swap true

to_do 4

index 5 Finished fourth “Bubble Up”

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fifth “Bubble Up”
N 8 did_swap false

to_do 3

index 1

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fifth “Bubble Up”
N 8 did_swap false

to_do 3

index 1

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fifth “Bubble Up”
N 8 did_swap false

to_do 3

index 2

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fifth “Bubble Up”
N 8 did_swap false

to_do 3

index 2

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fifth “Bubble Up”
N 8 did_swap false

to_do 3

index 3

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
The Fifth “Bubble Up”
N 8 did_swap false

to_do 3

index 3

No Swap

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
After Fifth Pass of Outer Loop
N 8 did_swap false

to_do 3

index 4 Finished fifth “Bubble Up”

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
Finished “Early”
N 8 did_swap false

to_do 3
We didn’t do any swapping,
index 4 so all of the other elements
must be correctly placed.

We can “skip” the last two

passes of the outer loop.

6 14 23 33 42 45 67 98

1 2 3 4 5 6 7 8
Summary
• “Bubble Up” algorithm will move
largest value to its correct location
(to the right)
• Repeat “Bubble Up” until all
elements are correctly placed:
• Maximum of N-1 times
• Can finish early if no swapping
occurs
• We reduce the number of elements
we compare each time one is
correctly placed
 LB

Truth in CS Act
• NOBODY EVER USES BUBBLE SORT

• NOBODY

• NOT EVER

• BECAUSE IT IS EXTREMELY INEFFICIENT

Insertion Sort and its Analysis
Insertion sort
• A good algorithm for sorting a small number of
elements.

• It works the way you might sort a hand of playing cards:

• Start with an empty left hand and the cards face down
on the table.
• Then remove one card at a time from the table, and
insert it into the correct position in the left hand.
• To find the correct position for a card, compare it with
each of the cards already in the hand, from right to left.
• At all times, the cards held in the left hand are sorted,
and these cards were originally the top cards of the pile
on the table.
Insertion sort (Example)
Insertion sort (Example)
Insertion sort
(Algorithm)
Divide and Conquer strategy
(Merge Sort)
 Overview
• Learn the technique of “divide and
conquer”
in the context of merge sort.
A Sorting Problem
(Divide and Conquer Approach)
• Divide the problem into a number of sub
problems.
• Conquer the sub problems by solving
them recursively.
• Base case: If the sub problems are small
enough, just solve them by brute force.
• Combine the sub problem solutions to
give a solution to the original problem.
Merge sort
• A sorting algorithm based on divide and conquer. Its worst-
case running time has a lower order of growth than insertion
sort.
• Because we are dealing with sub problems, we state each
sub problem as sorting a sub array A[p . . r ].
• Initially, p = 1 and r = n, but these values change as we
recurse through sub problems.
To sort A[p . . r ]:
• Divide by splitting into two sub arrays A[p . . q] and A[q + 1
. . r ], where q is the halfway point of A[p . . r ].
• Conquer by recursively sorting the two sub arrays A[p . . q]
and A[q + 1 . . r ].
• Combine by merging the two sorted sub arrays A[p . . q]
and A[q + 1 . . r ] to produce a single sorted sub array
A[p . . r ]. To accomplish this step, we’ll define a procedure
MERGE(A, p, q, r ).
Merge Sort (Algorithm)
The recursion bottoms out when the subarray has
just 1 element, so that it’s trivially sorted.
Merging
Input: Array A and indices p, q, r such that
• p≤q<r.
• Subarray A[p . . q] is sorted and subarray A[q + 1 . .
r ] is sorted. By the restrictions on p, q, r , neither
subarray is empty.

Output: The two subarrays are merged into a single

sorted subarray in A[p . . r ].

We implement it so that it takes (n) time, where

n = r − p + 1 = the number of elements
being merged.
Pseudocode (Merging)
 98 23 45 14 6 67 33 42

Access User Info

Administrator
Display Retrieve User Info
Account
User Profile
Info

User Account Info

Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

Administrator
Display Retrieve User Info
Account
User Profile
Info

User Account Info

Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
Display Retrieve User Info
Account
User Profile
Info

User Account Info

Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 Display Retrieve User Info
Account
User Profile
Info

User Account Info

Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 Display Retrieve User Info
Account
User Profile
Info

User Account Info

Merge

Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 Display Retrieve User Info
Account
User Profile
Info
23
User Account Info
Merge

Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 Display Retrieve User Info
Account
User Profile
Info
23 98
User Account Info
Merge

Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 45 14
Display Retrieve User Info
Account
User Profile
Info
23 98
User Account Info

Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 45 14
Display Retrieve User Info
Account
User Profile
Info
23 98
User Account Info
Merge
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 45 14
Display Retrieve User Info
Account
User Profile
Info
23 98 14
User Account Info
Merge
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 45 14
Display Retrieve User Info
Account
User Profile
Info
23 98 14 45
User Account Info
Merge
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 45 14
Display Retrieve User Info
Account
User Profile
Info
23 98 14 45
User Account Info

Validate
Update
Merge User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 45 14
Display Retrieve User Info
Account
User Profile
Info
23 98 14 45
User Account Info
14
Validate
Update
Merge User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 45 14
Display Retrieve User Info
Account
User Profile
Info
23 98 14 45
User Account Info
14 23
Validate
Update
Merge User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 45 14
Display Retrieve User Info
Account
User Profile
Info
23 98 14 45
User Account Info
14 23 45
Validate
Update
Merge User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14
Administrator
98 23 45 14
Display Retrieve User Info
Account
User Profile
Info
23 98 14 45
User Account Info
14 23 45 98
Validate
Update
Merge User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display Retrieve User Info
Account
User Profile
Info
23 98 14 45
User Account Info
14 23 45 98
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User Info
Account
User Profile
Info
23 98 14 45
User Account Info
14 23 45 98
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User Info
Account
User Profile
Info
23 98 14 45
User Account Info
14 23 45 98 Merge
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User Info
Account
User Profile
Info
23 98 14 45 6
User Account Info
14 23 45 98 Merge
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User Info
Account
User Profile
Info
23 98 14 45 6 67
User Account Info
14 23 45 98 Merge
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67
User Account Info
14 23 45 98
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67
User Account Info
14 23 45 98 Merge
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33
User Account Info
14 23 45 98 Merge
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 Merge
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98
Validate
Update
User Info
Merge
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6
Validate
Update
User Info
Merge
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33
Validate
Update
User Info
Merge
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42
Validate
Update
User Info
Merge
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
User Info
Merge
Enter/Update/ Delete
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
User Info
Enter/Update/ Delete
Update/Delete User Info
User Info

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
6
Enter/Update/ Delete User Info
Update/Delete User Info
User Info

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
6
Enter/Update/ Delete 14 User Info
Update/Delete User Info
User Info

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
6
Enter/Update/ Delete 14 23
User Info
Update/Delete User Info
User Info

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
6
Enter/Update/ Delete 14 23 33
User Info
Update/Delete User Info
User Info

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
6
Enter/Update/ Delete 14 23 33
User Info 42
Update/Delete User Info
User Info

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
6
Enter/Update/ Delete 14 23 33
User Info 42 45
Update/Delete User Info
User Info

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
6
Enter/Update/ Delete 14 23 33
User Info 42 45 67
Update/Delete User Info
User Info

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
6
Enter/Update/ Delete 14 23 33
User Info 42 45 67 98
Update/Delete User Info
User Info

Merge
 98 23 45 14 6 67 33 42

98 23 45 14 6 67 33 42
Access User Info

98 23 45 14 6 67 33 42
Administrator
98 23 45 14
Display 6 Retrieve
67 User
33 Info 42
Account
User Profile
Info
23 98 14 45 6 67 33 42
User Account Info
14 23 45 98 6 33 42 67
Validate
Update
6
Enter/Update/ Delete 14 23 33
User Info 42 45 67 98
Update/Delete User Info
User Info
 98 23 45 14 6 67 33 42

Access User Info

Administrator
Display Retrieve User Info
Account
User Profile
Info

User Account Info

Validate
Update
6
Enter/Update/ Delete 14 23 33
User Info 42 45 67 98
Update/Delete User Info
User Info
Example [A call of MERGE(9, 12, 16)]
Analyzing divide-and-conquer
algorithms
Analyzing merge sort
Recursion tree (Step 1)
Recursion tree (Step 2)
Recursion tree (Step n)
Divide and Conquer strategy
(Quick Sort)
 Overview

• Worst-case running time: 2

Θ(𝑛 )
• Expected running time:
Θ ¿
• Constants hidden in are small.

• Sorts in place.
Description of
quicksort
Performance of quicksort
The running time of quicksort depends on the
partitioning of the subarrays:
• If the subarrays are balanced, then
quicksort can run as fast as mergesort.
• If they are unbalanced, then quicksort can run
as slowly as insertion sort.
Randomized version of quicksort
• We have assumed that all input permutations are equally
likely.
• This is not always true.
• To correct this, we add randomization to quicksort.
• We could randomly permute the input array.
• Instead, we use random sampling, or picking one
element at random.
• Don’t always use A[r ] as the pivot. Instead, randomly
pick an element from the subarray that is being sorted.

We add this randomization by not always using A[r ] as the

pivot, but instead randomly picking an element from the
subarray that is being sorted
Analysis of quicksort
We will analyze
• the worst-case running time of RANDOMIZED-
QUICKSORT is average-case running time of QUICKSORT
that is O(n lg n) .
Algorithm Analysis and Design

Linear Time Sorting

(Counting Sort)
 Overview
• Running time of counting sort is O(n+k).
• Required extra space for sorting.
• Is a stable sorting.
Counting Sort

• Counting sort is a type of sorting

technique which is based on keys
between a specific range.
• It works by counting the number of
objects having distinct key values
(i.e. one kind of hashing).
Counting Sort

• Consider the input set : 4, 1, 3, 4, 3. Then n=5 and

k=4.
• Counting sort determines for each input element ,
the number of elements less than .
• This information is uses to place element directly
into its position in the output array.
• For example if there exits 17 elements less that x
then x is placed into the 18th position into the
output array.
Counting Sort
• Assumptions:
• n records
• Each record contains keys or data
• All keys are in the range of 0 to k, where k is
the highest key value of the array.
• Space:
For coding this algorithm uses three array:
• Input Array: A[1..n] store input data , where n is the
length of the array.
• Output Array: B[1..n] finally store the sorted data
• Temporary Array: C[0..k] store data temporarily
Counting Sort
• Let us illustrate the counting sort with an
example.
Apply the concept of counting sort on the given
1 2 3 4 5 6 7 8
A 2 5 3array.
0 2 3 0 3
Counting Sort
• Let us illustrate the counting sort with an example.
Apply the concept of counting sort on the given array.
1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3

•First create a new array C[0…..k] , where k is the

highest key value. And initialize with 0(i.e.
zero)
0 1 2 3 4 5
for i=0 to
C k0 0 0 0 0 0
C[i]= 0;
Counting Sort
• Let us illustrate the counting sort with an
example.
Apply the concept of counting sort on the given
1 2 3 4 5 6 7 8
A 2 5 3array.
0 2 3 0 3

• Findforthe
j=1 tofrequencies
A. length of each object and store
it in CC[ array.
A[j] ] = C[ A[j] ] + 1;
0 1 2 3 4 5
C 2 0 2 3 0 1
Counting Sort
• Let us illustrate the counting sort with an
example.
Apply the concept of counting sort on the given
1 2 3 4 5 6 7 8
A 2 5 array.
3 0 2 3 0 3

• Findforthe
j=1 tofrequencies
A. length of each object and store
0 1 2 3 4 5
it in C array.
C[ A[j] ] = C[ A[j] ] + 1; C 2 0 2 3 0 1

0 1 2 3 4 5
• And then cumulatively add CC array.
2 2 4 7 7 8

for i=1 to k
C[i] = C[i] + C[i-1];
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j]; 1 2 3 4 5 6 7 8
C[ A[j] ] = C[ A[j] ] - 1; A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 3 C 2 2 4 7 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j]; 1 2 3 4 5 6 7 8
C[ A[j] ] = C[ A[j] ] - 1; A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 3 C 2 2 4 7 7 8

1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 3 C 2 2 4 6 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j]; 1 2 3 4 5 6 7 8
C[ A[j] ] = C[ A[j] ] - 1; A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 3 C 2 2 4 6 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j]; 1 2 3 4 5 6 7 8
C[ A[j] ] = C[ A[j] ] - 1; A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 3 C 2 2 4 6 7 8

1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 3 C 1 2 4 6 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j]; 1 2 3 4 5 6 7 8
C[ A[j] ] = C[ A[j] ] - 1; A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 3 3 C 1 2 4 6 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
1 2 3 4 5 6 7 8
C[ A[j] ] = C[ A[j] ] - 1;
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 3 3 C 1 2 4 6 7 8

1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 3 3 C 1 2 4 5 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
1 2 3 4 5 6 7 8
C[ A[j] ] = C[ A[j] ] - 1;
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 2 3 3 C 1 2 4 5 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
1 2 3 4 5 6 7 8
C[ A[j] ] = C[ A[j] ] - 1;
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 2 3 3 C 1 2 4 5 7 8

1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 2 3 3 C 1 2 3 5 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
C[ A[j] ] = C[ A[j] ] - 1; 1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 3 3 C 1 2 3 5 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
C[ A[j] ] = C[ A[j] ] - 1; 1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 3 3 C 1 2 3 5 7 8

1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 3 3 C 0 2 3 5 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
C[ A[j] ] = C[ A[j] ] - 1; 1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 3 3 3 C 0 2 3 5 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
C[ A[j] ] = C[ A[j] ] - 1; 1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 3 3 3 C 0 2 3 5 7 8

1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 3 3 3 C 0 2 3 4 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
C[ A[j] ] = C[ A[j] ] - 1; 1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 3 3 3 5 C 0 2 3 4 7 8
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
C[ A[j] ] = C[ A[j] ] - 1; 1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 3 3 3 5 C 0 2 3 4 7 8

1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 3 3 3 5 C 0 2 3 4 7 7
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
1 2 3 4 5 6 7 8
C[ A[j] ] = C[ A[j] ] - 1;
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 2 3 3 3 5 C 0 2 3 4 7 7
Counting Sort
for j=A. length down to 1
B[C[ A[j] ]] = A[j];
1 2 3 4 5 6 7 8
C[ A[j] ] = C[ A[j] ] - 1;
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 2 3 3 3 5 C 0 2 3 4 7 7

1 2 3 4 5 6 7 8
A 2 5 3 0 2 3 0 3
j

1 2 3 4 5 6 7 8 0 1 2 3 4 5
B 0 0 2 2 3 3 3 5 C 0 2 2 4 7 7
Counting Sort
Counting-Sort(A, B, k)
1. Let C[0…..k] be a new array
2. for i=0 to k
3. C[i]= 0;
4. for j=1 to A. length
5. C[ A[j] ] = C[ A[j] ] + 1;
6. for i=1 to k
7. C[i] = C[i] + C[i-1];
8. for j=A. length down to 1
9. B[C[ A[j] ]] = A[j];
10. C[ A[j] ] = C[ A[j] ] - 1;
Counting Sort
Counting-Sort(A, B, k)
1. Let C[0…..k] be a new array
2. for i=0 to k [Loop 1]
3. C[i]= 0;
4. for j=1 to A. length [Loop 2]
5. C[ A[j] ] = C[ A[j] ] + 1;
6. for i=1 to k [Loop 3]
7. C[i] = C[i] + C[i-1];
8. for j=A. length down to 1 [Loop 4]
9. B[C[ A[j] ]] = A[j];
10. C[ A[j] ] = C[ A[j] ] - 1;
Complexity Analysis
Counting-Sort(A, B, k)
1. Let C[0…..k] be a new array
2. for i=0 to k [Loop 1]
3. C[i]= 0;
4. for j=1 to A. length [Loop 2]
5. C[ A[j] ] = C[ A[j] ] + 1;
6. for i=1 to k [Loop 3]
7. C[i] = C[i] + C[i-1];
8. for j=A. length down to 1 [Loop 2]
9. B[C[ A[j] ]] = A[j];
10. C[ A[j] ] = C[ A[j] ] - 1;
 Complexity Analysis
• So the counting sort takes a total time of: O(n + k)
• Counting sort is called stable sort.
( A sorting algorithm is stable when numbers with the

same values appear in the output array in the same

order as they do in the input array.)
 Pro’s and Con’s of Counting
Sort

• Pro’s
• Asymptotically fast Fast - O(n + k)
• Simple to code
• Con’s
• Doesn’t sort in place.
• Requires O(n + k) extra storage space.
Linear Time Sorting
(Radix Sort)
 Overview
• Running time of counting sort is
• Required extra space for sorting.
• Is a stable sorting.
Radix Sort
• Radix sort is non comparative
sorting method
• Two classifications of radix sorts are
least significant digit (LSD) radix
sorts and most significant digit
(MSD) radix sorts.
• LSD radix sorts process the integer
representations starting from the
least digit and move towards the
most significant digit. MSD radix
sorts work the other way around.
Radix Sort (Algorithm)

Radix_Sort(A,d)
Radix Sort
•In input array A, each element is a number of d
digit.

329
457
657
839
436
720
355
Radix Sort
•In input array A, each element is a number of d
digit.

329 720
457 355
657 436
839 457
436 657
720 329
355 839
Radix Sort
•In input array A, each element is a number of d
digit.

329 720 720

457 355 329
657 436 436
839 457 839
436 657 355
720 329 457
355 839 657
Radix Sort
•In input array A, each element is a number of d
digit.

329 720 720 329

457 355 329 355
657 436 436 436
839 457 839 457
436 657 355 657
720 329 457 720
355 839 657 839
Radix Sort (Analysis)
Radix_Sort(A,d)
Divide and Conquer strategy
(Heap Sort)
 Overview
• O(n lg n) worst case-like merge sort.

• Sorts in place-like insertion sort.

• Combines the best of both algorithms.

Heap data structure
Example
Example
• Given an array of size N. The task is to sort the array
elements by using Heap Sort.
• Input:
• N=10
• Arr[]:{16, 4, 10, 14, 7, 9, 3, 2, 8, 1}
• Output: 1 2 3 4 7 8 9 10 14 16
Example
• Given an array of size N. The task is to sort the array
elements by using Heap Sort.
• Input:
• N = 10
• arr[] = {10,9,8,7,6,5,4,3,2,1}
• Output:1 2 3 4 5 6 7 8 9 10
Heap property

• For max-heaps (largest element at root),

max-heap property: for all nodes i ,
excluding the root, A[PARENT(i )] ≥ A[i ].
• For min-heaps (smallest element at root),
min-heap property: for all nodes i ,
excluding the root, A[PARENT(i )] ≤ A[i ].
Maintaining the heap
property
Building a heap
Example
Building a max-heap from the following unsorted array results in
the
first heap example.
 Analysis
• Simple bound: O(n) calls to MAX-
HEAPIFY, each of which takes O(lg n) time
⇒ O(n lg n).
•Tighter analysis observation:
An n element heap has height and at
most nodes of any height h.
Tighter analysis Proof
BUILD-MAX-HEAP(A,n) 9

do MAX-HEAPIFY
(A,i,n)
6 5
i

0 8 2 1
1 2 3 4 5 6 7 8
9 6 5 0 8 2 1 3
3
Tighter analysis Proof
• For easy understanding, Let us take a complete
binary Tree,

• The height of a node is the number of edges from

the node to the deepest leaf.
• The depth of a node is the no of edges from the
root of the node.
Tighter analysis Proof
• All the leaves are of height 0,
therefore there are 8 nodes at height
0.
• 4 numbers of nodes at height 1.
• 2 numbers of nodes at height 2.
• and one node at height 3.
Tighter analysis Proof
• Hence the question is how many nodes are there at
height ‘h’ in a complete binary tree?
• The answer is :
• If there are n nodes in tree, then at most nodes are
available at height h.
Tighter analysis Proof
• Now if we apply MAX-HEAPIFY() on any node
of any level, then the time taken by MAX-
HEAPIFY() is the height of the node.
• Hence in case of root the time taken is
• Hence
by M ax -
o r k done n the
W fy () o
He a p i
d es of
of n o
b e r
nu m i gh t h.
h e
Tighter analysis Proof

Hence the running time of BUILD-MAX-

HEAP(A,n) is in tight bound .
The heapsort algorithm
Given an input array, the heapsort algorithm acts
as follows:
• Builds a max-heap from the array.
• Starting with the root (the maximum element),
the algorithm places the maximum element into
the correct place in the array by swapping it
with the element in the last position in the array.
• “Discard” this last node (knowing that it is in
its correct place) by decreasing the heap size,
and calling MAX-HEAPIFY on the new (possibly
incorrectly-placed) root.
• Repeat this “discarding” process until only one
node (the smallest element) remains, and
therefore is in the correct place in the array.
Example
Analysis
• BUILD-MAX-HEAP: O(n)
• for loop: n − 1 times
• exchange elements: O(1)
• MAX-HEAPIFY: O(lg n)

Total time: O(n lg n).

Heap implementation of
priority queue
• Heaps efficiently implement priority
queues. These notes will deal with max
priority queues implemented with max-
heaps. Min-priority queues are
implemented with min-heaps similarly.
• A heap gives a good compromise
between fast insertion but slow
extraction and vice versa. Both
operations take O(lg n) time.
Priority queue
• Maintains a dynamic set S of elements.
• Each set element has a key-an associated value.
• Max-priority queue supports dynamic-set operations:
• INSERT(S, x): inserts element x into set S.
• MAXIMUM(S): returns element of S with largest key.
• EXTRACT-MAX(S): removes and returns element of
S with largest key.
• INCREASE-KEY(S, x, k): increases value of element
x’s key to k. Assume k ≥ x’s current key value.
• Example max-priority queue application: schedule jobs on
shared computer.
• Min-priority queue supports similar operations:
• INSERT(S, x): inserts element x into set
S.
• MINIMUM(S): returns element of S with
smallest key.
• EXTRACT-MIN(S): removes and returns
element of S with smallest key.
• DECREASE-KEY(S, x, k): decreases value
of element x’s key to k. Assume k ≤ x’s
current key value.
• Example min-priority queue application:
event - driven simulator.
Finding the maximum element

Getting the maximum element is easy: it’s

the root.
HEAP-MAXIMUM(A)
return A[1]
Time: (1).
Extracting max element
Given the array A:
• Make sure heap is not empty.
• Make a copy of the maximum element (the root).
• Make the last node in the tree the new root.
• Re-heapify the heap, with one fewer node.
• Return the copy of the maximum element.
HEAP-EXTRACT-MAX(A, n)
if n < 1
then error .heap underflow.
max ← A[1]
A[1] ← A[n]
MAX-HEAPIFY(A, 1, n − 1) remakes heap
return max
• HEAP-INCREASE-KEY(A,i,key)
1. If key<A[i]
2. error” new key is smaller than the
current key”.
3. A[i]= key
4. While i>1 and A[parent(i)]<A[i]
5. swap(A[parent(i)], A[i])
6. i=parent(i)
The running time of HEAP-INCREASE-
KEY(A,i,key) is
• MAX-HEAP-INSERT(A,key)
1. [Link]-size= [Link]-size+1
2. A[heap-size]=-
3. HEAP-INCREASE-KEY(A,heap-size,key)
The running time of MAX-HEAP-
INSERT(A,key) is .
Linear Search, Binary Search
Problem: Search
• We are given a list of records.
• Each record has an associated key.
• Give efficient algorithm for searching for a record
containing a particular key.
• Efficiency is quantified in terms of average time analysis
(number of comparisons) to retrieve an item.
Search
[0] [1] [2] [3] [4] [ 700 ]

…
Number 281942902 Number 233667136 Number 580625685
Number 701466868 Number 506643548 Number 155778322

Each record in list has an associated key. Number 580625685

In this example, the keys are ID numbers.

Given a particular key, how can we efficiently

retrieve the record from the list?
Serial Search
• Step through array of records, one at a time.
• Look for record with matching key.
• Search stops when
• record with matching key is found
• or when search has examined all records without success.
for
Serial
Search
// Search for a desired item in the n array elements
// starting at a[first].
// Returns pointer to desired record if found.
// Otherwise, return NULL
…
for(i = first; i < n; ++i )
if(a[first+i] is desired item)
return &a[first+i];

// if we drop through loop, then desired item was not found

return NULL;
Serial Search Analysis
• What are the worst and average case running times for
serial search?
• We must determine the O-notation for the number of
operations required in search.
• Number of operations depends on n, the number of
entries in the list.
Worst Case Time for
Serial Search
• For an array of n elements, the worst
case time for serial search requires n
array accesses: O(n).
• Consider cases where we must loop
over all n records:
• desired record appears in the last position
of the array
• desired record does not appear in the array
at all
Average Case for Serial
Search
Assumptions:
1. All keys are equally likely in a search
2. We always search for a key that is in the array
Example:
• We have an array of 10 records.
• If search for the first record, then it requires
1 array access; if the second, then 2 array
accesses. etc.
The average of all these searches is:
(1+2+3+4+5+6+7+8+9+10)/10 = 5.5
 Average Case Time for
Serial Search
Generalize for array size n.

Expression for average-case running time:

(1+2+…+n)/n = n(n+1)/2n = (n+1)/2

Therefore, average case time complexity for serial search is

O(n).
Binary Search
• Perhaps we can do better than O(n) in the average
case?
• Assume that we are give an array of records that is
sorted. For instance:
• an array of records with integer keys sorted from smallest to
largest (e.g., ID numbers), or
• an array of records with string keys sorted in alphabetical
order (e.g., names).
Binary Search
Pseudocode
…
if(size == 0)
found = false;
else {
middle = index of approximate midpoint of array segment;
if(target == a[middle])
target has been found!
else if(target < a[middle])
search for target in area before midpoint;
else
search for target in area after midpoint;
}
…
Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53
Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Find approximate midpoint

Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Is 7 = midpoint key? NO.

Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Is 7 < midpoint key? YES.

Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Search for the target in the area before midpoint.

Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Find approximate midpoint

Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Target = key of midpoint? NO.

Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Target < key of midpoint? NO.

Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Target > key of midpoint? YES.

Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Search for the target in the area after midpoint.

Binary
Search
Example: sorted array of integer keys. Target=7.

[0] [1] [2] [3] [4] [5] [6]

3 6 7 11 32 33 53

Find approximate midpoint.

Is target = midpoint key? YES.
 Binary Search
Implementation
void search(const int a[ ], size_t first, size_t size, int target, bool& found, size_t& location)
{
size_t middle;
if(size == 0) found = false;
else {
middle = first + size/2;
if(target == a[middle]){
location = middle;
found = true;
}
else if (target < a[middle])
// target is less than middle, so search subarray before middle
search(a, first, size/2, target, found, location);
else
// target is greater than middle, so search subarray after middle
search(a, middle+1, (size-1)/2, target, found, location);
}
}
Binary
Search
Tree
Array of previous example:
3 6 7 11 32 33 53

Corresponding complete binary search tree

11
6 33

3 7 32 53
 Search for target = 7
Find midpoint:
3 6 7 11 32 33 53

Start at root:

11
6 33

3 7 32 53
 Search for target = 7
Search left subarray:
3 6 7 11 32 33 53

Search left subtree:

11
6 33

3 7 32 53
 Search for target = 7
Find approximate midpoint of
subarray:
3 6 7 11 32 33 53

Visit root of subtree:

11
6 33

3 7 32 53
 Search for target = 7
Search right subarray:
3 6 7 11 32 33 53

Search right subtree:

11
6 33

3 7 32 53
Binary Search: Analysis
• Worst case complexity?
• What is the maximum depth of recursive calls in binary
search as function of n?
• Each level in the recursion, we split the array in half
(divide by two).
• Therefore maximum recursion depth is floor(log2n) and
worst case = O(log2n).
• Average case is also = O(log2n).
 Hash Tables
• Constant time accesses! hash table
• A hash table is an array of some
fixed size, usually a prime number.0
• General idea:

hash function:
h(K)
…

key space (e.g., integers, strings) TableSize –1

312
 Example
•
0
key space = integers
•

•
TableSize = 10

h(K) = K mod 10
1
• Insert: 7, 18, 41, 94 2
3
4
5
6
7
8
9

313
 Another Example
• key space = integers
• TableSize = 6

• h(K) = K mod 6 0
• Insert: 7, 18, 41, 34

1
2
3
4
5

314
 Hash Functions
1. simple/fast to compute,
2. Avoid collisions
3. have keys distributed evenly among
cells.

Perfect Hash function:

315
 Sample Hash Functions:
• key space = strings
• s = s0 s1 s2 … s k-1

1. h(s) = s0 mod TableSize

 k1 
  si 
2. h(s) =  i 0  mod
TableSizek  1
 i 
  si 37 
 i 0 
316 3. h(s) = mod
TableSize
 Collision Resolution
Collision: when two keys map to the same location in
the hash table.

Two ways to resolve collisions:

1. Separate Chaining
2. Open Addressing (linear probing, quadratic probing,
double hashing)

317
 Separate Chaining
Insert:
0 10
1 22
107
2 12
3 42
4 • Separate
5 chaining: All keys
6 that map to the
same hash value
7 are kept in a list
8 (or “bucket”).
9
318
 Analysis of find
• Defn: The load factor, , of a hash table
is the ratio:N  no. of elements
M  table size
For separate chaining,  = average # of
elements in a bucket
• Unsuccessful find:

• Successful find:

319
 How big should the hash table be?
• For Separate Chaining:

320
 tableSize: Why
Prime?
• Suppose
• data stored in hash table: 7160, 493, 60, 55,
321, 900, 810

• tableSize = 10 Real-life data tends

data hashes to 0, 3, 0, 5, 1, 0, 0 to have a pattern

• tableSize = 11 Being a multiple of

data hashes to 10, 9, 5, 0, 2, 9, 7 11 is usually not the
pattern 

321
 Open Addressing
Insert:
38
0 19
1 8
2 109
10
3
4 • Linear Probing:
5 after checking
6 spot h(k), try spot
h(k)+1, if that is
7
full, try h(k)+2,
8 then h(k)+3, etc.
9
322
 Terminology Alert!

“Open Hashing” “Closed

equals Hashing”
Weiss “Separate equals
Chaining” “Open
Addressing”

323
 Linear Probing
f(i) = i

• Probe sequence:
0th probe = h(k) mod TableSize
1th probe = (h(k) + 1) mod TableSize
2th probe = (h(k) + 2) mod TableSize
...
ith probe = (h(k) + i) mod TableSize

324
 g–
Cluster
ing
no collision
collision in small cluster
no collision

collision in large cluster

[R. Sedgewick]
325
 Load Factor in Linear
Probing
• For any  < 1, linear probing will find an empty slot
• Expected # of probes (for large table sizes)
• successful search:

1 1 
 1  
• unsuccessful search: 2  1   

1 1 
 1  
• Linear probing suffers from 1     clustering
2  primary 2

• Performance quickly degrades for  > 1/2

326
 Quadratic Probing Less likely to
encounter
Primary
f(i) = i2
Clustering

• Probe sequence:
0th probe = h(k) mod TableSize
1th probe = (h(k) + 1) mod TableSize
2th probe = (h(k) + 4) mod TableSize
3th probe = (h(k) + 9) mod TableSize
...
ith probe = (h(k) + i2) mod TableSize

327
 Quadratic Probing
0 Insert:
1 89
18
2
49
3 58
4 79
5
6
7
8
9
328
 Quadratic
insert(76)
Probing
insert(40) insert(48)
Example
insert(5) insert(55)
76%7 = 6 40%7 = 5 48%7 = 6 5%7 = 5 55%7 = 6
0

But… insert(47)
1
47%7 = 5
2

6
76

329
 Success guarantee
for  < ½
• If size is prime and  < ½, then quadratic
probing will find an empty slot in size/2
probes or fewer.
• show for all 0  i,j  size/2 and i  j
(h(x) + i2) mod size  (h(x) + j2) mod size
• by contradiction: suppose that for some i  j:
(h(x) + i2) mod size = (h(x) + j2) mod size
 i2 mod size = j2 mod size
 (i2 - j2) mod size = 0
 [(i + j)(i - j)] mod size = 0

Because size is prime(i-j)or (i+j) must be zero, and

neither can be
330
 Quadratic Probing: Properties
• For any  < ½, quadratic probing will find an
empty slot; for bigger , quadratic probing may
find a slot

• Quadratic probing does not suffer from primary

clustering: keys hashing to the same area are
not bad

• But what about keys that hash to the same

spot?
• Secondary Clustering!

331
 Double Hashing
f(i) = i * g(k)
where g is a second hash function

• Probe sequence:
0th probe = h(k) mod TableSize
1th probe = (h(k) + g(k)) mod TableSize
2th probe = (h(k) + 2*g(k)) mod TableSize
3th probe = (h(k) + 3*g(k)) mod TableSize
...
ith probe = (h(k) + i*g(k)) mod TableSize

332
 g
Exampl
e h(k) = k mod 7 and g(k) = 5 – (k mod 5)

76 93 40 47 10 55

0 0 0 0 0 0
1 1 1 1 47 1 47 1 47
2 2 93 2 93 2 93 2 93 2 93
3 3 3 3 3 10 3 10
4 4 4 4 4 4 55
5 5 5 40 5 40 5 40 5 40
6 76 6 76 6 76 6 76 6 76 6 76
Probes 1 1 1 2 1 2
333
 Resolving Collisions with Double
Hashing
0 Hash Functions:
1 H(K) = K mod M
2 H2(K) = 1 + ((K/M) mod
(M-1))
3
M=
4 Insert these values into the hash table
5 in this order. Resolve any collisions
with double hashing:
6 13
7 28
8 33
9 147
43
334
 Rehashing
Idea: When the table gets too full, create
a bigger table (usually 2x as large) and
hash all the items from the original table
into the new table.
• When to rehash?
• half full ( = 0.5)
• when an insertion fails
• some other threshold
• Cost of rehashing?

335
 Java hashCode()
Method
• Class Object defines a hashCode method
• Intent: returns a suitable hashcode for the
object
• Result is arbitrary int; must scale to fit a
hash table (e.g. [Link]() % nBuckets)
• Used by collection classes like HashMap
• Classes should override with calculation
appropriate for instances of the class
• Calculation should involve semantically
“significant” fields of objects

336
 hashCode() and equals()
• To work right, particularly with collection classes like
HashMap, hashCode() and equals() must obey this rule:
if [Link](b) then it must be true that
[Link]() == [Link]()
• Why?
• Reverse is not required

337