DESIGN AND ANALYSIS OF ALGORITHMS NOTES

MODULE-2
SORTING AND SEARCHING TECHNIQUES

2.1 Selection Sort

Selection sort is a simple sorting algorithm. This sorting algorithm, like insertion sort, is an in-place
comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end
and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire
[Link] smallest element is selected from the unsorted array and swapped with the leftmost element,
and that element becomes a part of the sorted array. This process continues moving unsorted array
boundaries by one element to the right.

This algorithm is not suitable for large data sets as its average and worst case complexities are of O(n2),
where n is the number of items.

WORKING

1. Set MIN to location 0.

2. Search the minimum element in the list.

3. Swap with value at location MIN.

4. Increment MIN to point to next element.

5. Repeat until the list is sorted.

Algorithm: Selection-Sort (A)

for i← 1 to n-1 do
min j ←i;
min x ← A[i]
for j ←i + 1 to n do
if A[j] < min x then
min j ← j
min x ← A[j]
A[min j] ← A [i]
A[i] ← min x

Analysis
Selection sort is among the simplest of sorting techniques and it works very well for small files. It has
a quite important application as each item is actually moved at the most once.
Section sort is a method of choice for sorting files with very large objects (records) and small keys. The
worst case occurs if the array is already sorted in a descending order and we want to sort them in an
ascending order.

Nonetheless, the time required by selection sort algorithm is not very sensitive to the original order of
the array to be sorted: the test if [] < A[j] < min x is executed exactly the same number of times in every
case.

Selection sort spends most of its time trying to find the minimum element in the unsorted part of the
array. It clearly shows the similarity between Selection sort and Bubble sort.

Input: Given n input elements.

Output: Number of steps incurred to sort a list.

Logic: If we are given n elements, then in the first pass, it will do n-1 comparisons; in the second pass,
it will do n-2; in the third pass, it will do n-3 and so on. Thus, the total number of comparisons can be
found by;

Therefore, the selection sort algorithm encompasses a time complexity of O(n2) and a space complexity
of O(1) because it necessitates some extra memory space for temp variable for swapping.

Time Complexities:

o Best Case Complexity: The selection sort algorithm has a best-case time complexity
of O(n2) for the already sorted array.
o Average Case Complexity: The average-case time complexity for the selection sort algorithm
is O(n2), in which the existing elements are in jumbled ordered, i.e., neither in the ascending
order nor in the descending order.
o Worst Case Complexity: The worst-case time complexity is also O(n2), which occurs when
we sort the descending order of an array into the ascending order.
2.2 Bubble Sort
Bubble Sort, also known as Exchange Sort, is a simple sorting algorithm. It works by repeatedly
stepping throughout the list to be sorted, comparing two items at a time and swapping them if they are
in the wrong order. The pass through the list is duplicated until no swaps are desired, which means the
list is sorted. This is the easiest method among all sorting algorithms.

Algorithm: Sequential-Bubble-Sort (A)

for i ← 1 to length [A] do
for j ← length [A] down-to i +1 do
if A[A] < A[j-1] then
Exchange A[j] ⟷ A[j-1]
Consider the following example of an unsorted array that we will sort with the help of the Bubble Sort
algorithm.

Initially,

Pass 1:

o Compare a0 and a1

As a0 < a1 so the array will remain as it is.

o Compare a1 and a2
Now a1 > a2, so we will swap both of them.

o Compare a2 and a3

As a2 < a3 so the array will remain as it is.

o Compare a3 and a4

Here a3 > a4, so we will again swap both of them.

Pass 2:

Compare a0 and a1
As a0 < a1 so the array will remain as it is.

o Compare a1 and a2

Here a1 < a2, so the array will remain as it is.

o Compare a2 and a3

In this case, a2 > a3, so both of them will get swapped.

Pass 3:

o Compare a0 and a1

As a0 < a1 so the array will remain as it is.

o Compare a1 and a2
Now a1 > a2, so both of them will get swapped.

Pass 4:

o Compare a0 and a1

Here a0 > a1, so we will swap both of them.

Hence the array is sorted as no more swapping is required.

Complexity Analysis of Bubble Sort

Input: Given n input elements.

Output: Number of steps incurred to sort a list.

Logic: If we are given n elements, then in the first pass, it will do n-1 comparisons; in the second pass,
it will do n-2; in the third pass, it will do n-3 and so on. Thus, the total number of comparisons can be
found by;

Therefore, the bubble sort algorithm encompasses a time complexity of O(n2) and a space complexity
of O(1) because it necessitates some extra memory space for temp variable for swapping.

Time Complexities:

o Best Case Complexity: The bubble sort algorithm has a best-case time complexity of O(n) for
the already sorted array.
 o Average Case Complexity: The average-case time complexity for the bubble sort algorithm
is O(n2), which happens when 2 or more elements are in jumbled, i.e., neither in the ascending
order nor in the descending order.
o Worst Case Complexity: The worst-case time complexity is also O(n2), which occurs when
we sort the descending order of an array into the ascending order.
Advantages of Bubble Sort

1. Easily understandable.
2. Does not necessitates any extra memory.
3. The code can be written easily for this algorithm.
4. Minimal space requirement than that of other sorting algorithms.

Disadvantages of Bubble Sort

1. It does not work well when we have large unsorted lists, and it necessitates more resources that
end up taking so much of time.
2. It is only meant for academic purposes, not for practical implementations.
3. It involves the n2 order of steps to sort an algorithm.

2.3 Insertion Sort

Insertion sort is one of the simplest sorting algorithms for the reason that it sorts a single element at a
particular instance. It is not the best sorting algorithm in terms of performance, but it's slightly more
efficient than selection sort and bubble sort in practical scenarios.

Insertion Sort Algorithm

Now we have a bigger picture of how this sorting technique works, so we can derive simple steps by
which we can achieve insertion sort.
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2− Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted

ALGORITHM: INSERTION SORT (A)

1. for j = 2 to [Link]
2. key = A[j]
3. // Insert A[j] into the sorted sequence A[1.. j - 1]
4. i = j - 1
5. while i > 0 and A[i] > key
6. A[i + 1] = A[i]
7. i = i -1
8. A[i + 1] = key

Consider the following example of an unsorted array that we will sort with the help of the Insertion Sort
algorithm.

A = (41, 22, 63, 14, 55, 36)

Initially,
1st Iteration:

Set key = 22

Compare a1 with a0

Since a0 > a1, swap both of them.

2nd Iteration:

Set key = 63

Compare a2 with a1 and a0

Since a2 > a1 > a0, keep the array as it is.

3rd Iteration:

Set key = 14

Compare a3 with a2, a1 and a0

Since a3 is the smallest among all the elements on the left-hand side, place a3 at the beginning of the
array.

4th Iteration:

Set key = 55

Compare a4 with a3, a2, a1 and a0.

As a4 < a3, swap both of them.

5th Iteration:

Set key = 36

Compare a5 with a4, a3, a2, a1 and a0.

Since a5 < a2, so we will place the elements in their correct positions.
 Hence the array is arranged in ascending order, so no more swapping is required.

Complexity Analysis of Insertion Sort

Input: Given n input elements.

Output: Number of steps incurred to sort a list.

Logic: If we are given n elements, then in the first pass, it will make n-1 comparisons; in the second
pass, it will do n-2; in the third pass, it will do n-3 and so on. Thus, the total number of comparisons
can be found by;

Output;
(n-1) + (n-2) + (n-3) + (n-4) + ...... + 1

Sum=
i.e., O(n2)
Therefore, the insertion sort algorithm encompasses a time complexity of O(n2) and a space complexity
of O(1) because it necessitates some extra memory space for a key variable to perform swaps.

Time Complexities:

o Best Case Complexity: The insertion sort algorithm has a best-case time complexity
of O(n) for the already sorted array because here, only the outer loop is running n times, and
the inner loop is kept still.
o Average Case Complexity: The average-case time complexity for the insertion sort algorithm
is O(n2), which is incurred when the existing elements are in jumbled order, i.e., neither in the
ascending order nor in the descending order.
o Worst Case Complexity: The worst-case time complexity is also O(n2), which occurs when
we sort the ascending order of an array into the descending order.
In this algorithm, every individual element is compared with the rest of the elements, due to
which n-1 comparisons are made for every nth element.
The insertion sort algorithm is highly recommended, especially when a few elements are left for sorting
or in case the array encompasses few elements.

Space Complexity

The insertion sort encompasses a space complexity of O(1) due to the usage of an extra variable key.

2.4 Sequential Search

Linear search is a type of sequential searching algorithm. In this method, every element within the input
array is traversed and compared with the key element to be found. If a match is found in the array the
search is said to be successful; if there is no match found the search is said to be unsuccessful and gives
the worst-case time complexity.
 Linear Search Algorithm

The algorithm for linear search is relatively simple. The procedure starts at the very first index of the
input array to be searched.

Step 1 − Start from the 0th index of the input array, compare the key value with the value present in
the 0th index.

Step 2 − If the value matches with the key, return the position at which the value was found.

Step 3 − If the value does not match with the key, compare the next element in the array.

Step 4 − Repeat Step 3 until there is a match found. Return the position at which the match was
found.

Step 5 − If it is an unsuccessful search, print that the element is not present in the array and exit the
program.

Linear search traverses through every element sequentially therefore, the best case is when the element
is found in the very first iteration. The best-case time complexity would be O(1).

However, the worst case of the linear search method would be an unsuccessful search that does not find
the key value in the array, it performs n iterations. Therefore, the worst-case time complexity of the
linear search algorithm would be O(n).

2.5 Binary Search

Binary Search algorithm is an interval searching method that performs the searching in intervals only.
The input taken by the binary search algorithm must always be in a sorted array since it divides the
array into subarrays based on the greater or lower values. The algorithm follows the procedure below −

Step 1 − Select the middle item in the array and compare it with the key value to be searched. If it is
matched, return the position of the median.

Step 2 − If it does not match the key value, check if the key value is either greater than or less than the
median value.

Step 3 − If the key is greater, perform the search in the right sub-array; but if the key is lower than the
median value, perform the search in the left sub-array.

Step 4 − Repeat Steps 1, 2 and 3 iteratively, until the size of sub-array becomes 1.

Step 5 − If the key value does not exist in the array, then the algorithm returns an unsuccessful search.
procedure binary_search (array, target)
low = 0
high = array. length - 1

while low <= high:

mid = (low + high) / 2 (use integer division)

if array[mid] == target:
return mid // target found

else if target < array[mid]:

high = mid - 1 // discard right half

else:
low = mid + 1 // discard left half

return -1 // target not found

end procedure
ANALYSIS

At least there will be only one term left that's why that term will compare out, and only one comparison be

done that's why

Is the last term of the equation and it will be equal to 1

2.6 Depth First Search

The depth-first search (DFS) algorithm starts with the initial node of graph G and goes deeper until we find
the goal node or the node with no children.

Because of the recursive nature, stack data structure can be used to implement the DFS algorithm. The
process of implementing the DFS is similar to the BFS algorithm.

The step by step process to implement the DFS traversal is given as follows -

1. First, create a stack with the total number of vertices in the graph.
2. Now, choose any vertex as the starting point of traversal, and push that vertex into the stack.
 3. After that, push a non-visited vertex (adjacent to the vertex on the top of the stack) to the top of the
stack.
4. Now, repeat steps 3 and 4 until no vertices are left to visit from the vertex on the stack's top.
5. If no vertex is left, go back and pop a vertex from the stack.
6. Repeat steps 2, 3, and 4 until the stack is empty.

Algorithm

Step 1: SET STATUS = 1 (ready state) for each node in G

Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until STACK is empty

Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)

Step 5: Push on the stack all the neighbors of N that are in the ready state (whose STATUS = 1) and set their
STATUS = 2 (waiting state)

[END OF LOOP]

Step 6: EXIT

EXAMPLE-

Now, let's start examining the graph starting from Node H.

Step 1 - First, push H onto the stack.

1. STACK: H

Step 2 - POP the top element from the stack, i.e., H, and print it. Now, PUSH all the neighbors of H onto the
stack that are in ready state.
1. Print: H]STACK: A

Step 3 - POP the top element from the stack, i.e., A, and print it. Now, PUSH all the neighbors of A onto the
stack that are in ready state.

1. Print: A
2. STACK: B, D

Step 4 - POP the top element from the stack, i.e., D, and print it. Now, PUSH all the neighbors of D onto the
stack that are in ready state.

1. Print: D
2. STACK: B, F

Step 5 - POP the top element from the stack, i.e., F, and print it. Now, PUSH all the neighbors of F onto the
stack that are in ready state.

1. Print: F
2. STACK: B

Step 6 - POP the top element from the stack, i.e., B, and print it. Now, PUSH all the neighbors of B onto the
stack that are in ready state.

1. Print: B
2. STACK: C

Step 7 - POP the top element from the stack, i.e., C, and print it. Now, PUSH all the neighbors of C onto the
stack that are in ready state.

1. Print: C
2. STACK: E, G

Step 8 - POP the top element from the stack, i.e., G and PUSH all the neighbors of G onto the stack that are
in ready state.

1. Print: G
2. STACK: E

Step 9 - POP the top element from the stack, i.e., E and PUSH all the neighbors of E onto the stack that are
in ready state.

1. Print: E
2. STACK:

Now, all the graph nodes have been traversed, and the stack is empty.

Complexity of Depth-first search algorithm:

The time complexity of the DFS algorithm is O(V+E), where V is the number of vertices and E is the number
of edges in the graph.

The space complexity of the DFS algorithm is O(V).

2.7 Breadth First Search

In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited
to essentially two operations:

(a) visit and inspect a node of a graph; (

(b) gain access to visit the nodes that neighbor the currently visited node.
The BFS begins at a root node and inspects all the neighboring nodes.

Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited,
and so on.

Compare BFS with the equivalent, but more memory-efficient.

BFS ALGORITHM:

Step 1: SET STATUS = 1 (ready state) for each node in G

Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)

Step 3: Repeat Steps 4 and 5 until QUEUE is empty

Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).

Step 5: Enqueue all the neighbours of N that are in the ready state (whose STATUS = 1) and set

their STATUS = 2

(waiting state)
 [END OF LOOP]

Step 6: EXIT

Example of BFS algorithm

Now, let's understand the working of BFS algorithm by using an example. In the example given below, there
is a directed graph having 7 vertices.

In the above graph, minimum path 'P' can be found by using the BFS that will start from Node A and end at
Node E. The algorithm uses two queues, namely QUEUE1 and QUEUE2. QUEUE1 holds all the nodes that are
to be processed, while QUEUE2 holds all the nodes that are processed and deleted from QUEUE1.

Now, let's start examining the graph starting from Node A.

Step 1 - First, add A to queue1 and NULL to queue2.

1. QUEUE1 = {A}
2. QUEUE2 = {NULL}

Step 2 - Now, delete node A from queue1 and add it into queue2. Insert all neighbors of node A to queue1.

1. QUEUE1 = {B, D}
2. QUEUE2 = {A}

Step 3 - Now, delete node B from queue1 and add it into queue2. Insert all neighbors of node B to queue1.

1. QUEUE1 = {D, C, F}
2. QUEUE2 = {A, B}

Step 4 - Now, delete node D from queue1 and add it into queue2. Insert all neighbors of node D to queue1.
The only neighbour of Node D is F since it is already inserted, so it will not be inserted again.
1. QUEUE1 = {C, F}
2. QUEUE2 = {A, B, D}

Step 5 - Delete node C from queue1 and add it into queue2. Insert all neighbors of node C to queue1.

1. QUEUE1 = {F, E, G}
2. QUEUE2 = {A, B, D, C}

Step 5 - Delete node F from queue1 and add it into queue2. Insert all neighbors of node F to queue1. Since
all the neighbors of node F are already present, we will not insert them again.

1. QUEUE1 = {E, G}
2. QUEUE2 = {A, B, D, C, F}

Step 6 - Delete node E from queue1. Since all of its neighbors have already been added, so we will not insert
them again. Now, all the nodes are visited, and the target node E is encountered into queue2.

1. QUEUE1 = {G}
2. QUEUE2 = {A, B, D, C, F, E}

Complexity of BFS algorithm

Time complexity of BFS depends upon the data structure used to represent the graph. The time complexity
of BFS algorithm is O(V+E), since in the worst case, BFS algorithm explores every node and edge. In a graph,
the number of vertices is O(V), whereas the number of edges is O(E).

The space complexity of BFS can be expressed as O(V), where V is the number of vertices.

2.8 Balanced Search Trees

A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in

which the height of the left and right subtree of any node differ by not more than 1.

To learn more about the height of a tree/node, visit Tree Data Structure. Following are the conditions

for a height-balanced binary tree:

1. difference between the left and the right subtree for any node is not more than one

2. the left subtree is balanced

3. the right subtree is balanced

Balanced Binary Tree with depth at each level

Unbalanced Binary Tree with depth at each level

2.9 AVL Trees

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between
heights of left and right subtrees for any node cannot be more than one.

Balance Factor = left subtree height - right subtree height

For a Balanced Tree(for every node): -1 ≤ Balance Factor ≤ 1
An AVL tree is given in the following figure. We can see that; balance factor associated with each node
is in between -1 and +1. therefore, it is an example of AVL tree.
AVL tree controls the height of the binary search tree by not letting it to be skewed. The time taken for
all operations in a binary search tree of height h is O(h). However, it can be extended to O(n) if the
BST becomes skewed (i.e. worst case). By limiting this height to log n, AVL tree imposes an upper
bound on each operation to be O(log n) where n is the number of nodes.

AVL Rotations
We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0, and 1. There are
basically four types of rotations which are as follows:

1. L L rotation: Inserted node is in the left subtree of left subtree of A.

2. R R rotation: Inserted node is in the right subtree of right subtree of A.
3. L R rotation: Inserted node is in the right subtree of left subtree of A.
4. R L rotation: Inserted node is in the left subtree of right subtree of A.

Where node A is the node whose balance Factor is other than -1, 0, 1.

The first two rotations LL and RR are single rotations and the next two rotations LR and RL are double
rotations. For a tree to be unbalanced, minimum height must be at least 2, Let us understand each
rotation

Let's discuss each tree rotation in detail.

1. RR Rotation

When BST becomes unbalanced, due to a node is inserted into the right subtree of the right subtree of
A, then we perform RR rotation, RR rotation is an anticlockwise rotation, which is applied on the edge
below a node having balance factor -2
 In above example, node A has balance factor -2 because a node C is inserted in the right subtree of A
right subtree. We perform the RR rotation on the edge below A.

2. LL Rotation

When BST becomes unbalanced, due to a node is inserted into the left subtree of the left subtree of C,
then we perform LL rotation, LL rotation is clockwise rotation, which is applied on the edge below a
node having balance factor 2.

In above example, node C has balance factor 2 because a node A is inserted in the left subtree of C left
subtree. We perform the LL rotation on the edge below A.

2.10 Red-Black Trees

The red-Black tree is a binary search tree. The prerequisite of the red-black tree is that we should know
about the binary search tree. In a binary search tree, the values of the nodes in the left subtree should be
less than the value of the root node, and the values of the nodes in the right subtree should be greater
than the value of the root node.

Each node in the Red-black tree contains an extra bit that represents a color to ensure that the tree is
balanced during any operations performed on the tree like insertion, deletion, etc. In a binary search
tree, the searching, insertion and deletion take O(log2n) time in the average case, O(1) in the best case
and O(n) in the worst case.

Properties of Red-Black Tree

o It is a self-balancing Binary Search tree. Here, self-balancing means that it balances the tree
itself by either doing the rotations or recoloring the nodes.
o This tree data structure is named as a Red-Black tree as each node is either Red or Black in
color. Every node store one extra information known as a bit that represents the color of the
 node. For example, 0 bit denotes the black color while 1 bit denotes the red color of the node.
Other information stored by the node is similar to the binary tree, i.e., data part, left pointer and
right pointer.
o In the Red-Black tree, the root node is always black in color.
o In a binary tree, we consider those nodes as the leaf which have no child. In contrast, in the
Red-Black tree, the nodes that have no child are considered the internal nodes and these nodes
are connected to the NIL nodes that are always black in color. The NIL nodes are the leaf nodes
in the Red-Black tree.
o If the node is Red, then its children should be in Black color. In other words, we can say that
there should be no red-red parent-child relationship.
o Every path from a node to any of its descendant's NIL node should have same number of black
nodes.

Show the red-black trees that result after successively inserting the keys
41,38,31,12,19,8 into an initially empty red-black tree.

Solution:
Insert 41
Insert 19

Thus the final tree is

 2.11 Heaps and Heap Sort

A heap is a complete binary tree, and a binary tree is a tree in which each node can
have the at most two children. A complete binary tree is a binary tree in which all the
levels except the last level, i.e., the leaf node, should be filled, and all the nodes should
be left-justified.

Heap Sort is an in-place sorting algorithm.

Algorithm
1. Heapsort(arr) {
2. BuildHeap(arr)
3. for j <- length(arr) downto 2 {
4. exchange arr[1] <-> arr[j]
5. heapsize <- heapsize -1
6. Heapify(arr, 1)
7. }
8. BuildHeap(arr) {
9. heapsize <- length(arr)
10. for j <- floor( length / 2 ) downto 1
11. Heapify(arr, j)
12. }
13. Heapify(A, j) {
14. le <- left(j)
15. ri <- right(j)
16. if (le <= heapsize) and (arr[le] > A[j])
17. largest <- le
18. else
19. largest <- j
20. if (ri <= heapsize) and (arr[ri] > A[largest])
21. largest <- ri
22. if (largest != j) {
23. exchange arr[j] <-> arr[largest]
24. Heapify(arr, largest)
25. }
26. }

Steps of Heap Sort

Step 1: Convert the array into a binary tree.

Step 2: Convert the binary tree into a max heap. It will ensure that all parent nodes are
larger than or equal to their child nodes.

Step 3: Swap the root node (the largest element) with the last element in the heap. It
will destroy the property of the max heap.

Step 4: In order to restore the property of a max heap, invoke the heapify() method.

Step 5: Keep repeating steps 3 and 4 until the heap is sorted, and in each iteration,
exclude the last element from the heap.

Step 6: After each swap and heapify() call, make sure that the property max heap is
maintained.

Working of the Heap Sort Algorithm

Now, let's see the workings of the Heap Sort Algorithm.

Step 1: Observe the input array as a binary tree. We have taken a[] = {19, 4, 13, 18, 10,
12, 15} as input array.
The root will be positioned at index 0. The left and right child of any root positioned
at the ith index will be at the index (2 * i + 1) and (2 * i + 2), respectively. The above
diagram illustrates the same.

Step 2: Apply heapify() to convert it into a max heap. It will rearrange the elements of
the input array to imitate the max heap.

Step 3: Now, replace the root element with the last element of the heap. Note that we
have an element 19 at its appropriate position in the sorted array. Hence, reduce the
heap size by 1.
Step 4: Observe that the current heap is not following the property of the max heap.
Therefore, apply heapify() again to rearrange the elements to form a max heap.

Step 5: Replace the last element of the heap with the topmost element of the heap.
We will get the second-last element of the sorted array placed at the second-last
position. Hence, the size of the heap will also be reduced by 1.
Step 6: Apply heapify() again to rearrange elements to follow the properties of a max
heap.

Step 7: Again, swap the last element with the topmost element of the heap. We will
get the third-last element of the sorted array.
Step 8: Apply heapify() on the remaining elements of the heap.

Step 9: Do the swapping of the topmost and the last element of the heap. At this
point, we have sorted the last four elements of the array.
Step 10: Rearrange elements to follow the max heap by applying heapify() again.

Step 11: Apply swapping of the topmost element and the last element of the heap.
Only the last two elements remain in a heap to be sorted.
 Step 12: Apply heapify() and then do the swapping of the elements, and we will get
the desired result.

Now, the array is sorted.

2.12 Divide and Conquer Paradigm of problem solving

There are two fundamental of Divide & Conquer Strategy:

1. Relational Formula
2. Stopping Condition

1. Relational Formula: It is the formula that we generate from the given technique. After
generation of Formula we apply D&C Strategy, i.e. we break the problem recursively & solve
the broken subproblems.

2. Stopping Condition: When we break the problem using Divide & Conquer Strategy, then
we need to know that for how much time, we need to apply divide & Conquer. So the condition
where the need to stop our recursion steps of D&C is called as Stopping Condition.

Applications

Following algorithms are based on the concept of the Divide and Conquer Technique:

1. Binary Search: The binary search algorithm is a searching algorithm, which is also
called a half-interval search or logarithmic search. It works by comparing the target
 value with the middle element existing in a sorted array. After making the comparison,
if the value differs, then the half that cannot contain the target will eventually eliminate,
followed by continuing the search on the other half. We will again consider the middle
element and compare it with the target value. The process keeps on repeating until the
target value is met. If we found the other half to be empty after ending the search, then
it can be concluded that the target is not present in the array.
2. Quicksort: It is the most efficient sorting algorithm, which is also known as partition-
exchange sort. It starts by selecting a pivot value from an array followed by dividing
the rest of the array elements into two sub-arrays. The partition is made by comparing
each of the elements with the pivot value. It compares whether the element holds a
greater value or lesser value than the pivot and then sort the arrays recursively.
3. Merge Sort: It is a sorting algorithm that sorts an array by making comparisons. It
starts by dividing an array into sub-array and then recursively sorts each of them. After
the sorting is done, it merges them back.

Binary search

1. In Binary Search technique, we search an element in a sorted array by recursively dividing the
interval in half.

2. Firstly, we take the whole array as an interval.

3. If the Pivot Element (the item to be searched) is less than the item in the middle of the interval,
We discard the second half of the list and recursively repeat the process for the first half of the list
by calculating the new middle and last element.
 4. If the Pivot Element (the item to be searched) is greater than the item in the middle of the
interval, we discard the first half of the list and work recursively on the second half by calculating the
new beginning and middle element.

5. Repeatedly, check until the value is found or interval is empty.

Algorithm

1. Binary_Search(a, lower_bound, upper_bound, val) // 'a' is the given array, 'lower_bound' is the index
of the first array element, 'upper_bound' is the index of the last array element, 'val' is the value to s
earch
2. Step 1: set beg = lower bound, end = upper bound, pos = - 1
3. Step 2: repeat steps 3 and 4 while beg <=end
4. Step 3: set mid = (beg + end)/2
5. Step 4: if a[mid] = val
6. set pos = mid
7. print pos
8. go to step 6
9. else if a[mid] > val
10. set end = mid - 1
11. else
12. set beg = mid + 1
13. [end of if]
14. [end of loop]
15. Step 5: if pos = -1
16. print "value is not present in the array"
17. [end of if]
18. Step 6: exit
At least there will be only one term left that's why that term will compare out, and only one comparison be

done that's why

Is the last term of the equation and it will be equal to 1

Merge Sort

Merge sort is another sorting algorithm that falls under the category of Divide and
Conquer technique. It is one of the best sorting techniques that successfully build a recursive
algorithm.

In this technique, we segment a problem into two halves and solve them individually. After finding the
solution of each half, we merge them back to represent the solution of the main problem.

Suppose we have an array A, such that our main concern will be to sort the subsection, which starts at
index p and ends at index r, represented by A [p..r].
 Divide:

If assumed q to be the central point somewhere in between p and r, then we will fragment the
subarray A[p..r] into two arrays A[p..q] and A[q+1, r].

Conquer

After splitting the arrays into two halves, the next step is to conquer. In this step, we individually sort
both of the subarrays A[p..q] and A[q+1, r]. In case if we did not reach the base situation, then we
again follow the same procedure, i.e., we further segment these subarrays followed by sorting them
separately.

Combine

As when the base step is acquired by the conquer step, we successfully get our sorted
subarrays A[p..q] and A[q+1, r], after which we merge them back to form a new sorted array [p..r].

Merge Sort algorithm

The MergeSort function keeps on splitting an array into two halves until a condition is met where we try to
perform Merge Sort on a subarray of size 1, i.e., p == r.

And then, it combines the individually sorted sub arrays into larger arrays until the whole array is merged.

ALGORITHM-MERGE SORT
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)

FUNCTIONS: MERGE (A, p, q, r)

1. n 1 = q-p+1
2. n 2= r-q
3. create arrays [1.....n 1 + 1] and R [ 1.....n 2 +1 ]
4. for i ← 1 to n 1
5. do [i] ← A [ p+ i-1]
6. for j ← 1 to n2
7. do R[j] ← A[ q + j]
8. L [n 1+ 1] ← ∞
9. R[n 2+ 1] ← ∞
10. I ← 1
11. J ← 1
12. For k ← p to r
13. Do if L [i] ≤ R[j]
14. then A[k] ← L[ i]
15. i ← i +1
16. else A[k] ← R[j]
17. j ← j+1
Analysis:

Let T (n) be the total time taken by the Merge Sort algorithm.

o Sorting two halves will take at the most 2T time.

o When we merge the sorted lists, we come up with a total n-1 comparison because the last element
which is left will need to be copied down in the combined list, and there will be no comparison.

Thus, the relational formula will be

But we ignore '-1' because the element will take some time to be copied in merge lists.

So T (n) = 2T + n...equation 1

ut 2 equation in 1 equation

Putting 4 equation in 3 equation

From Stopping Condition:

Apply log both sides:

Logn=log2i
logn=ilog2

=i

log2n=i

From 6 equation

Best Case Complexity: The merge sort algorithm has a best-case time complexity of O(n*log n) for the
already sorted array.

Average Case Complexity: The average-case time complexity for the merge sort algorithm is O(n*log n),
which happens when 2 or more elements are jumbled, i.e., neither in the ascending order nor in the
descending order.

Worst Case Complexity: The worst-case time complexity is also O(n*log n), which occurs when we sort the
descending order of an array into the ascending order.

Space Complexity: The space complexity of merge sort is O (n).

 QUICK SORT

• The divide-and-conquer approach can be used to arrive at an efficient sorting

method different from merge sort.

• In merge sort, the file a[1:n] was divided at its midpoint into sub arrays which were

independently sorted & later merged.

• In Quick sort, the division into 2 sub arrays is made so that the sorted sub arrays do

not need to be merged later.

• This is accomplished by rearranging the elements in a[1:n] such that a[I]<=a[j] for

all I between 1 & n and all j between (m+1) & n for some m, 1<=m<=n.

• Thus the elements in a[1:m] & a[m+1:n] can be independently

No merge is needed. This rearranging is referred to as partitioning.

Function partition of Algorithm accomplishes an in-place partitioning of the

elements of a[m:p-1]

• It is assumed that a[p]>=a[m] and that a[m] is the partitioning element. If m=1 &

p-1=n, then a[n+1] must be defined and must be greater than or equal to all elements

in a[1:n]

• The assumption that a[m] is the partition element is merely for convenience, other

choices for the partitioning element than the first item in the set are better in practice.

• The function interchange (a,I,j) exchanges a[I] with a[j].

Algorithm:
1. QUICKSORT (array A, start, end)
2. {
3. 1 if (start < end)
4. 2{
5. 3 p = partition(A, start, end)
6. 4 QUICKSORT (A, start, p - 1)
7. 5 QUICKSORT (A, p + 1, end)
8. 6}
9. }
PARTITION (array A, start, end)
1. {
2. 1 pivot =A[end]
3. 2 i = start-1
4. 3 for j = start to end -1 {
5. 4 do if (A[j] < pivot) {
6. 5 then i = i + 1
7. 6 swap A[i] with A[j]
8. 7 }}
9. 8 swap A[i+1] with A[end]
10. 9 return i+1
11. }

Working of Quick Sort

To understand the working of quick sort, let's take an unsorted array. It will make the concept more clear and
understandable.

Let the elements of array are -

In the given array, we consider the leftmost element as pivot. So, in this case, a[left] = 24, a[right] = 27 and
a[pivot] = 24.

Since, pivot is at left, so algorithm starts from right and move towards left.

Now, a[pivot] < a[right], so algorithm moves forward one position towards left, i.e. -
Now, a[left] = 24, a[right] = 19, and a[pivot] = 24.

Because, a[pivot] > a[right], so, algorithm will swap a[pivot] with a[right], and pivot moves to right, as -

Now, a[left] = 19, a[right] = 24, and a[pivot] = 24. Since, pivot is at right, so algorithm starts from left and
moves to right.

As a[pivot] > a[left], so algorithm moves one position to right as -

Now, a[left] = 9, a[right] = 24, and a[pivot] = 24. As a[pivot] > a[left], so algorithm moves one position to
right as -
Now, a[left] = 29, a[right] = 24, and a[pivot] = 24. As a[pivot] < a[left], so, swap a[pivot] and a[left], now pivot
is at left, i.e. -

Since, pivot is at left, so algorithm starts from right, and move to left. Now, a[left] = 24, a[right] = 29, and
a[pivot] = 24. As a[pivot] < a[right], so algorithm moves one position to left, as -

Now, a[pivot] = 24, a[left] = 24, and a[right] = 14. As a[pivot] > a[right], so, swap a[pivot] and a[right], now
pivot is at right, i.e. -

Now, a[pivot] = 24, a[left] = 14, and a[right] = 24. Pivot is at right, so the algorithm starts from left and move
to right.
Now, a[pivot] = 24, a[left] = 24, and a[right] = 24. So, pivot, left and right are pointing the same element. It
represents the termination of procedure.

Element 24, which is the pivot element is placed at its exact position.

Elements that are right side of element 24 are greater than it, and the elements that are left side of element
24 are smaller than it.

Now, in a similar manner, quick sort algorithm is separately applied to the left and right sub-arrays.
After sorting gets done, the array will be -