SORTING
For More Visit : [Link] | Fair Use Policy
Bubble Sort
● Starting with the first element(index = 0), compare
the current element with the next element of the
array.
● If the current element is greater than the next
element of the array, swap them.
● If the current element is less than the next element,
move to the next element. Repeat Step 1.
For More Visit : [Link] | Fair Use Policy
Bubble Sort [cont..]
● BUBBLE_SORT(A, N)
Step 1: Repeat Step 2 For i = 0 to N-1
Step 2: Repeat For j = 0 to N - I- i
Step 3: IF A[ j ] > A[ j + 1 ]
SWAP A[ j ] and A[ j+1]
[END OF INNER LOOP]
[END OF OUTER LOOP]
For More Visit : [Link] | Fair Use Policy
Complexity of Bubble Sort
● In Bubble Sort, n-1 comparisons will be done in the
1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on.
So the total number of comparisons will be,
f(n) = (n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1
f(n) = n(n-1)/2
i.e O(n2)
For More Visit : [Link] | Fair Use Policy
Selection Sort
● algorithm will first find the smallest element in the
array and swap it with the element in the first
position, then it will find the second smallest
element and swap it with the element in the
second position, and it will keep on doing this until
the entire array is sorted.
● It is called selection sort because it repeatedly
selects the next-smallest element and swaps it into
For More Visit : [Link] | Fair Use Policy
the right place.
How Selection Sort works?
● Starting from the first element, we search the
smallest element in the array, and replace it with
the element in the first position.
● We then move on to the second position, and look
for smallest element present in the subarray,
starting from index 1, till the last index.
● We replace the element at the second position in
the originalForarray, or we can say at the first position
More Visit : [Link] | Fair Use Policy
in the subarray, with the second smallest element.
Selection Sort
SMALLEST (ARR, K, N, POS) SELECTION SORT(ARR, N)
Step 1: [INITIALIZE]
SET SMALL = ARR[K] Step 1: Repeat Steps 2 and 3 for K = 0 to N-1
Step 2: [INITIALIZE] SET POS = K Step 2: CALL SMALLEST(ARR, K, N,POS)
Step 3: Repeat for J = K+1 to N -1 Step 3: SWAP A[K] with ARR[POS]
IF SMALL > ARR[J] [END OF LOOP]
SET SMALL = ARR[J] Step 4: Exit
SET POS = J
[END OF IF]
[END OF LOOP]
Step 4: RETURN POS
For More Visit : [Link] | Fair Use Policy
Example
For More Visit : [Link] | Fair Use Policy
Complexity of Selection Sort
● In Pass 1, selecting the element with the smallest
value calls for scanning all n elements;thus, n–1
comparisons are required in the first pass.
● Then, the smallest value is swapped with the element
in the first position. In Pass 2, selecting the second
smallest value requires scanning the remaining n – 1
elements and so on. Therefore,
● f(n) = (n – 1) + (n – 2) + ... + 2 + 1
● f(n) = n(n – 1) / 2 = O(n2 ) comparisons
For More Visit : [Link] | Fair Use Policy
Insertion Sort
● Insertion sort is a simple sorting algorithm that
works the way we sort playing cards in our hands
For More Visit : [Link] | Fair Use Policy
Insertion Sort
To insert 12, we need to
make room for it by moving
first 36 and then 24.
For More Visit : [Link] | Fair Use Policy
Insertion Sort
For More Visit : [Link] | Fair Use Policy
Insertion Sort
For More Visit : [Link] | Fair Use Policy
Insertion Sort
input array
5 2 4 6 1 3
at each iteration, the array is divided in two sub-arrays:
left sub-array right sub-array
sorted unsorted
For More Visit : [Link] | Fair Use Policy
Insertion Sort
For More Visit : [Link] | Fair Use Policy
INSERTION-SORT (ARR, N)
Step 1: Repeat Steps 2 to 5 for K = 1 to N – 1
Step 2: SET TEMP = ARR[K]
Step 3: SET J = K - 1
Step 4: Repeat while TEMP <= ARR[J] and J>=0
SET ARR[J + 1] = ARR[J]
SET J = J - 1
[END OF INNER LOOP]
Step 5: SET ARR[J + 1] = TEMP
[END OF LOOP]
Step 6: EXIT For More Visit : [Link] | Fair Use Policy
Complexity of Insertion Sort
● The best case input is an array that is already sorted. In this case
insertion sort has a linear running time (i.e., O(n)).
● During each iteration, the first remaining element of the input is only
compared with the right-most element of the sorted subsection of the
array.
● The set of all worst case inputs consists of all arrays where each
element is the smallest or second-smallest of the elements before it.
In these cases every iteration of the inner loop will scan and shift the
entire sorted subsection of the array before inserting the next
element. This gives insertion sort a quadratic running time (i.e.,
O(n2)).
● The average case is also quadratic
For More Visit : [Link] | Fair Use Policy
Quick Sort
The quick sort algorithm works as follows:
1. Select an element pivot from the array elements.
2. Rearrange the elements in the array in such a way that all elements
that are less than the pivot appear before the pivot and all elements
greater than the pivot element come after it (equal values can go
either way). After such a partitioning, the pivot is placed in its final
position.
This is called the partition operation.
3. Recursively sort the two sub-arrays thus obtained. (One with sub-
list of values smaller than that of the pivot element and the other
having higher value elements.)
For More Visit : [Link] | Fair Use Policy
Quick Sort
For More Visit : [Link] | Fair Use Policy
Quick Sort
QUICK_SORT (ARR, BEG, END)
Step 1: IF (BEG < END)
Q = PARTITION (ARR, P , R )
QUICKSORT(ARR, P, Q-1)
QUICKSORT(ARR, Q+1, R)
[END OF IF]
Step 2: END For More Visit : [Link] | Fair Use Policy
PARTITION (ARR, P, R)
{
X = ARR[R]
i=P-1
For j = P to R - 1
{
If ( ARR[ j ] <= X )
{
i=i+1
Exchange ARR[ i ] with ARR[ j ]
}
}
Exchange ARR[ i + 1] with ARR[ R ]
Return i + 1 For More Visit : [Link] | Fair Use Policy
Complexity of Quick Sort
● In the best case, every time we partition the array,
we divide the list into two nearly equal pieces. That
is, the recursive call processes the sub-array of half
the size. At the most, only log n nested calls can be
made before we reach a sub-array of size 1. It
means the depth of the call tree is O(log n) . And
because at each level, there can only be O(n) , the
resultant time is given as O(nlog n) time.
For More Visit : [Link] | Fair Use Policy
Complexity
● Its worst-case efficiency is given as O(n 2 ) . The
worst case occurs when the array is already sorted
(either in ascending or descending order) and the
left-most element is chosen as the pivot
For More Visit : [Link] | Fair Use Policy
Merge Sort
● Merge sort is a sorting algorithm that uses the divide, conquer, and
combine algorithmic paradigm.
● Divide means partitioning the n -element array to be sorted into two
sub-arrays of n/2 elements. If A is an array containing zero or one
element, then it is already sorted. However, if there are more
elements in the array, divide A into two sub-arrays, A 1 and A2 , each
containing about half of the elements of A .
● Conquer means sorting the two sub-arrays recursively using merge
sort.
● Combine means merging the two sorted sub-arrays of size n/2 to
produce the sorted array
For More Visit of n elements.
: [Link] | Fair Use Policy
Algorithm for Merge Sort
MERGE_SORT(ARR, P, R)
mergesort(p,q)
if(p<q) // if there exist more than on element
m=(p+q)/2 // Dividing
mergesort(p,m)
mergesort(m+1,q)
merge(p,m,q) // Merging
End
For More Visit : [Link] | Fair Use Policy
Algorithm for Merge Sort[cont…]
MERGE (ARR, P, Q, R)
merge(low,m,high) if(i>m) // Finished 1st half and copying
i=low // the remaining nos of 2nd half
j=m+1 for(p=j; p<=high; p++)
k=low b[k++]=a[p]
while(i<=m&&j<=high) // comparing else // Finished 2nd half and copying
elements // the remaining nos of 1st half
if(a[i]<=a[j]) for(p=i; p<=m; p++)
b[k++]=a[i++] b[k++]=a[p]
else for(p=low; p<=high; p++)
b[k++]=a[j++] a[p]=b[p]
// copy the elements of array b to a
}
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy
Complexity of Merge Sort
The list of size N is divided into a max of log N parts,
and the merging of all sublists into a single list takes
O(N) time, the worst case run time of this algorithm is
O(N log N)
For More Visit : [Link] | Fair Use Policy
Heapsort
For More Visit : [Link] | Fair Use Policy
Heap data structure
Binary tree
Balanced
Left-justified or Complete
(Max) Heap property: no node has a value
greater than the value in its parent
For More Visit : [Link] | Fair Use Policy
30
Balanced binary trees
• Recall:
– The depth of a node is its distance from the root
– The depth of a tree is the depth of the deepest node
• A binary tree of depth n is balanced if all the nodes at depths 0
through n-2 have two children
n-2
n-1
n
Balanced Balanced Not balanced
For More Visit : [Link] | Fair Use Policy
31
Left-justified binary trees
• A balanced binary tree of depth n is left-justified if:
– it has 2n nodes at depth n (the tree is “full”), or
– it has 2k nodes at depth k, for all k < n, and all the
leaves at depth n are as far left as possible
Left-justified Not left-justified
For More Visit : [Link] | Fair Use Policy
32
Building up to heap sort
• How to build a heap
• How to maintain a heap
• How to use a heap to sort data
For More Visit : [Link] | Fair Use Policy
33
The heap property
• A node has the heap property if the value in the node
is as large as or larger than the values in its children
12 12 12
8 3 8 12 8 14
Blue node has Blue node has Blue node does not
heap property heap property have heap property
• All leaf nodes automatically have the heap property
• A binary tree is a heap if all nodes in it have the heap property
For More Visit : [Link] | Fair Use Policy
34
siftUp
• Given a node that does not have the heap property, you
can give it the heap property by exchanging its value
with the value of the larger child
12 14
8 14 8 12
Blue node does not Blue node has
have heap property heap property
• This is sometimes called sifting up
For More Visit : [Link] | Fair Use Policy
35
Constructing a heap I
• A tree consisting of a single node is automatically a heap
• We construct a heap by adding nodes one at a time:
– Add the node just to the right of the rightmost node in the
deepest level
– If the deepest level is full, start a new level
• Examples:
Add a new Add a new
node here node here
For More Visit : [Link] | Fair Use Policy
36
Constructing a heap II
• Each time we add a node, we may destroy the heap property of its
parent node
• To fix this, we sift up
• But each time we sift up, the value of the topmost node in the sift
may increase, and this may destroy the heap property of its parent
node
• We repeat the sifting up process, moving up in the tree, until either
– We reach nodes whose values don’t need to be swapped (because the
parent is still larger than both children), or
– We reach the root
For More Visit : [Link] | Fair Use Policy
37
Constructing a heap III
8 8 10 10
10 8 8 5
1 2 3
10 10 12
8 5 12 5 10 5
12 8 8
4
For More Visit : [Link] | Fair Use Policy
38
Other children are not affected
12 12 14
10 5 14 5 12 5
8 14 8 10 8 10
• The node containing 8 is not affected because its parent gets larger, not smaller
• The node containing 5 is not affected because its parent gets larger, not smaller
• The node containing 8 is still not affected because, although its parent got smaller,
its parent is still greater than it was originally
For More Visit : [Link] | Fair Use Policy
39
A sample heap
• Here’s a sample binary tree after it has been heapified
25
22 17
19 22 14 15
18 14 21 3 9 11
• Notice that heapified does not mean sorted
• Heapifying does not change the shape of the binary tree; this binary
tree is balanced and left-justified because it started out that way
For More Visit : [Link] | Fair Use Policy
40
Removing the root (animated)
• Notice that the largest number is now in the root
• Suppose we discard the root:
11
22 17
19 22 14 15
18 14 21 3 9 11
• How can we fix the binary tree so it is once again balanced and left-
justified?
• Solution: remove the rightmost leaf at the deepest level and use it for
the new root For More Visit : [Link] | Fair Use Policy
41
The reHeap method I
• Our tree is balanced and left-justified, but no longer a heap
• However, only the root lacks the heap property
11
22 17
19 22 14 15
18 14 21 3 9
• We can siftDown() the root
• After doing this, one and only one of its children may have lost
the heap property
For More Visit : [Link] | Fair Use Policy
42
The reHeap method II
• Now the left child of the root (still the number 11) lacks the
heap property
22
11 17
19 22 14 15
18 14 21 3 9
• We can siftDown() this node
• After doing this, one and only one of its children may have lost
the heap property
For More Visit : [Link] | Fair Use Policy
43
The reHeap method III
• Now the right child of the left child of the root (still the
number 11) lacks the heap property:
22
22 17
19 11 14 15
18 14 21 3 9
• We can siftDown() this node
• After doing this, one and only one of its children may have lost
the heap property
For More—but
Visit it
: doesn’t, because
[Link] it’sPolicy
| Fair Use a leaf
44
The reHeap method IV
• Our tree is once again a heap, because every node in it has
the heap property
22
22 17
19 21 14 15
18 14 11 3 9
• Once again, the largest (or a largest) value is in the root
• We can repeat this process until the tree becomes empty
• This producesFora More
sequence
Visit : of values in order
[Link] | Fair largest to smallest
Use Policy
45
Sorting
• What do heaps have to do with sorting an array?
– Because the binary tree is balanced and left justified, it
can be represented as an array
– All our operations on binary trees can be represented as
operations on arrays
– To sort:
heapify the array;
while the array isn’t empty {
remove and replace the root;
reheap the new root node;
} For More Visit : [Link] | Fair Use Policy
46
Sorting
For More Visit : [Link] | Fair Use Policy
47
For More Visit : [Link] | Fair Use Policy
48
Analysis
• To reheap the root node, we have to follow one path from the
root to a leaf node (and we might stop before we reach a
leaf)
• The binary tree is perfectly balanced
• Therefore, this path is O(log n) long
– And we only do O(1) operations at each node
– Therefore, reheaping takes O(log n) times
• Since we reheap inside a while loop that we do n times, the
total time for the while loop is n*O(log n), or O(n log n)
For More Visit : [Link] | Fair Use Policy
49
Analysis
• Construct the heap O(n log n)
• Remove and re-heap O(log n)
– Do this n times O(n log n)
• Total timeFor More Visit
O(n :log n) + O(n log n)
[Link] | Fair Use Policy
50
HASHING
For More Visit : [Link] | Fair Use Policy
Introduction
For More Visit : [Link] | Fair Use Policy
Introduction
● Sequential search requires, on the average O(n) comparisons to locate an element. So many
comparisons are not desirable for a large database of elements.
● Binary search requires much fewer comparisons on the average O (log n) but there is an additional
requirement that the data should be sorted. Even with best sorting algorithm, sorting of elements
require 0(n log n) comparisons.
● There is another widely used technique for storing of data called hashing. It does away with the
requirement of keeping data sorted (as in binary search) and its best case timing
complexity is of constant order (0(1)). In its worst case, hashing algorithm starts behaving like linear
search.
● Best case timing behavior of searching using hashing = O( 1)
● Worst case timing Behavior of searching using hashing = O(n)
● In hashing, the record for a key value "key", is directly referred by calculating the address
from the key value. Address or location of an element or record, x, is obtained by computing some
arithmetic function f. f(key) gives the address of x in the table.
For More Visit : [Link] | Fair Use Policy
Hashing
For More Visit : [Link] | Fair Use Policy
Different Hash Functions
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy
Mid Square Method
For More Visit : [Link] | Fair Use Policy
Mid Square Method
For More Visit : [Link] | Fair Use Policy
Folding Method
For More Visit : [Link] | Fair Use Policy
Folding Method
For More Visit : [Link] | Fair Use Policy
Digit Analysis Method
For More Visit : [Link] | Fair Use Policy
Properties of a Good Hash Function
For More Visit : [Link] | Fair Use Policy
Properties of a Good Hash Function
For More Visit : [Link] | Fair Use Policy
Properties of a Good Hash Function
For More Visit : [Link] | Fair Use Policy
Collision
For More Visit : [Link] | Fair Use Policy
Collision Resolution by Open Addressing /
Closed Hashing
For More Visit : [Link] | Fair Use Policy
Collision Resolution by Open Addressing /
Closed Hashing
For More Visit : [Link] | Fair Use Policy
●
●
●
●
For More Visit : [Link] | Fair Use Policy
Linear Probing
For More Visit : [Link] | Fair Use Policy
Quadratic Probing
For More Visit : [Link] | Fair Use Policy
Double Hashing
●
●
●
For More Visit : [Link] | Fair Use Policy
Double Hashing
For More Visit : [Link] | Fair Use Policy
Rehashing
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy
Collision Resolution by Chaining
For More Visit : [Link] | Fair Use Policy
●
●
For More Visit : [Link] | Fair Use Policy
Eg:
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy
For More Visit : [Link] | Fair Use Policy