COMPUTER SCIENCE PRANAB SAHA(B.

Sc(H), MCA) Å 9088134887

1) Write short notes on Bubble sort & algorithm as well as time & space complexity
measurement.
Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm
in which each pair of adjacent elements is compared and the elements are swapped if they are
not in order. This algorithm is not suitable for large data sets as its average and worst case
complexity are of Ο(n2) where n is the number of items.

How Bubble Sort Works?

We take an unsorted array for our example. Bubble sort takes Ο(n 2) time so we're keeping it
short and precise.

Bubble sort starts with very first two elements, comparing them to check which one is greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare
33 with 27.

We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this −

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After one iteration,
the array should look like this −

Page no. -1
COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887

To be precise, we are now showing how an array should look like after each iteration. After the
second iteration, it should look like this −

Notice that after each iteration, at least one value moves at the end.

And when there's no swap required, bubble sorts learns that an array is completely sorted.

Now we should look into some practical aspects of bubble sort.

Algorithm

We assume list is an array of n elements. We further assume that swap function swaps the
values of the given array elements.

begin BubbleSort(list) //->procedure

for all elements of list

if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort

Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is
reverse sorted.
Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
Auxiliary Space: O(1)
Boundary Cases: Bubble sort takes minimum time (Order of n) when elements are already
sorted.

Page no. -2
COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887
2) Write short notes on Insertion sort & algorithm as well as time & space complexity
measurement.
This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is
always sorted. For example, the lower part of an array is maintained to be sorted. An element
which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has
to be inserted there. Hence the name, insertion sort.
The array is searched sequentially and unsorted items are moved and inserted into the sorted
sub-list (in the same array). This algorithm is not suitable for large data sets as its average and
worst case complexity are of Ο(n2), where n is the number of items.

How Insertion Sort Works?

We take an unsorted array for our example.

Insertion sort compares the first two elements.

It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.

Insertion sort moves ahead and compares 33 with 27.

And finds that 33 is not in the correct position.

It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the
sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list
remains sorted after swapping.

By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.

These values are not in a sorted order.

So we swap them.

Page no. -3
COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887

However, swapping makes 27 and 10 unsorted.

Hence, we swap them too.

Again we find 14 and 10 in an unsorted order.

We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items.

This process goes on until all the unsorted values are covered in a sorted sub-list. Now we shall
see some programming aspects of 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

Pseudocode:-

procedure insertionSort( A : array of items )

int holePosition
int valueToInsert
for i = 1 to inclusive do:
valueToInsert = A[i]
holePosition = i
while holePosition > 0 and A[holePosition-1] > valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
A[holePosition] = valueToInsert
end for
end procedure
Time Complexity: O(n*2)  O(2n)  O(log 2n)
Auxiliary Space: O(1)
Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse
order. And it takes minimum time (Order of n) when elements are already sorted.

Page no. -4
COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887

What is Binary Insertion Sort?

We can use binary search to reduce the number of comparisons in normal insertion sort. Binary
Insertion Sort uses binary search to find the proper location to insert the selected item at each
iteration. In normal insertion, sorting takes O(i) (at ith iteration) in worst case. We can reduce it
to O(logi) by using binary search. The algorithm, as a whole, still has a running worst case
running time of O(n2) because of the series of swaps required for each insertion.

3) Write short notes on Selection sort & algorithm as well as time & space complexity
measurement.
Selection sort is a simple sorting algorithm. This sorting algorithm 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 list.
The 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 boundary by one element to the right.
This algorithm is not suitable for large data sets as its average and worst case complexities are
of Ο(n2), where n is the number of items.
algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.

How Selection Sort Works?

Consider the following depicted array as an example.

For the first position in the sorted list, the whole list is scanned sequentially. The first position
where 14 is stored presently, we search the whole list and find that 10 is the lowest value.

So we replace 14 with 10. After one iteration 10, which happens to be the minimum value in
the list, appears in the first position of the sorted list.

For the second position, where 33 is residing, we start scanning the rest of the list in a linear
manner.

We find that 14 is the second lowest value in the list and it should appear at the second place.
We swap these values.

After two iterations, two least values are positioned at the beginning in a sorted manner.

Page no. -5
COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887

The same process is applied to the rest of the items in the array.
Following is a pictorial depiction of the entire sorting process −

Now, let us learn some programming aspects of selection sort.

Algorithm:-

Step 1 − Set MIN to location 0

Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

Pseudocode:-

procedure selection sort

list : array of items
n : size of list
for i = 1 to n - 1
Page no. -6
COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887
/* set current element as minimum*/
pos = i
/* check the element to be minimum */
for j = i+1 to n
if array[j] < array[ps] then
pos = j;
end if
end for
/* swap the minimum element with the current element*/
if pos != j then
swap  array[i];
array[i]  array[pos];
array[pos]  swap;
end if
end for

end procedure

Time Complexity: O(n2) as there are two nested loops.

Auxiliary Space: O(1)
The good thing about selection sort is it never makes more than O(n) swaps and can be useful
when memory write is a costly operation.

4) Write short notes on Merge sort & algorithm as well as time & space complexity
measurement.
Merge sort is a sorting technique based on divide and conquer technique. With worst-case time
complexity being Ο(n log n), it is one of the most respected algorithms.
Merge sort first divides the array into equal halves and then combines them in a sorted
manner.

How Merge Sort Works?

To understand merge sort, we take an unsorted array as the following −

We know that merge sort first divides the whole array iteratively into equal halves unless the
atomic values are achieved. We see here that an array of 8 items is divided into two arrays of
size 4.

This does not change the sequence of appearance of items in the original. Now we divide these
two arrays into halves.

We further divide these arrays and we achieve atomic value which can no more be divided.

Now, we combine them in exactly the same manner as they were broken down. Please note
the color codes given to these lists.
Page no. -7
COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887
We first compare the element for each list and then combine them into another list in a sorted
manner. We see that 14 and 33 are in sorted positions. We compare 27 and 10 and in the
target list of 2 values we put 10 first, followed by 27. We change the order of 19 and 35
whereas 42 and 44 are placed sequentially.

In the next iteration of the combining phase, we compare lists of two data values, and merge
them into a list of found data values placing all in a sorted order.

After the final merging, the list should look like this −

Now we should learn some programming aspects of merge sorting.

Algorithm :-

Merge sort keeps on dividing the list into equal halves until it can no more be divided. By
definition, if it is only one element in the list, it is sorted. Then, merge sort combines the
smaller sorted lists keeping the new list sorted too.
Step 1 − if it is only one element in the list it is already sorted, return.
Step 2 − divide the list recursively into two halves until it can no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.

Pseudocode :-

We shall now see the pseudocodes for merge sort functions. As our algorithms point out two
main functions − divide & merge.
Merge sort works with recursion and we shall see our implementation in the same way.
procedure mergesort( var a as array )
if ( n == 1 ) return a

var l1 as array = a[0] ... a[n/2]

var l2 as array = a[n/2+1] ... a[n]

l1 = mergesort( l1 )
l2 = mergesort( l2 )

return merge( l1, l2 )

end procedure

procedure merge( var a as array, var b as array )

var c as array
while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while
Page no. -8
COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887

while ( a has elements )

add a[0] to the end of c
remove a[0] from a
end while

while ( b has elements )

add b[0] to the end of c
remove b[0] from b
end while

return c

end procedure

Time Complexity: Sorting arrays on different machines. Merge Sort is a recursive algorithm
and time complexity can be expressed as following recurrence relation.
T(n)=2T(n/2)+ (n)
The above recurrence can be solved either using Recurrence Tree method or Master method. It
falls in case II of Master Method and solution of the recurrence is . (n Log n)
Time complexity of Merge Sort is (n Log n) in all 3 cases (worst, average and best) as merge
sort always divides the array into two halves and take linear time to merge two halves.
Auxiliary Space: O(n)
Algorithmic Paradigm: Divide and Conquer
Sorting In Place: No in a typical implementation
Stable: Yes
Applications of Merge Sort
1. Merge Sort is useful for sorting linked lists in O(nLogn) time .In the case of linked lists, the
case is different mainly due to the difference in memory allocation of arrays and linked lists.
Unlike arrays, linked list nodes may not be adjacent in memory. Unlike an array, in the
linked list, we can insert items in the middle in O(1) extra space and O(1) time. Therefore
merge operation of merge sort can be implemented without extra space for linked lists.
In arrays, we can do random access as elements are contiguous in memory. Let us say we
have an integer (4-byte) array A and let the address of A[0] be x then to access A[i], we can
directly access the memory at (x + i*4). Unlike arrays, we can not do random access in the
linked list. Quick Sort requires a lot of this kind of access. In linked list to access i’th index,
we have to travel each and every node from the head to i’th node as we don’t have a
continuous block of memory. Therefore, the overhead increases for quicksort. Merge sort
accesses data sequentially and the need of random access is low.

5) Write short notes & algorithm on binary search ?

Page no. -9
COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887
Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search
algorithm works on the principle of divide and conquer. For this algorithm to work properly, the
data collection should be in the sorted form.
Binary search looks for a particular item by comparing the middle most item of the collection.
If a match occurs, then the index of item is returned. If the middle item is greater than the
item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the
item is searched for in the sub-array to the right of the middle item. This process continues on
the sub-array as well until the size of the subarray reduces to zero.

How Binary Search Works?

For a binary search to work, it is mandatory for the target array to be sorted. We shall learn
the process of binary search with a pictorial example. The following is our sorted array and let
us assume that we need to search the location of value 31 using binary search.

First, we shall determine half of the array by using this formula −

mid = low + (high - low) / 2
Here it is, 0 + (9 - 0 ) / 2 = 4 (integer value of 4.5). So, 4 is the mid of the array.

Now we compare the value stored at location 4, with the value being searched, i.e. 31. We find
that the value at location 4 is 27, which is not a match. As the value is greater than 27 and we
have a sorted array, so we also know that the target value must be in the upper portion of the
array.

We change our low to mid + 1 and find the new mid value again.
low = mid + 1
mid = low + (high - low) / 2
Our new mid is 7 now. We compare the value stored at location 7 with our target value 31.

The value stored at location 7 is not a match, rather it is more than what we are looking for.
So, the value must be in the lower part from this location.

Hence, we calculate the mid again. This time it is 5.

Page no. -10

COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887

We compare the value stored at location 5 with our target value. We find that it is a match.

We conclude that the target value 31 is stored at location 5.

Binary search halves the searchable items and thus reduces the count of comparisons to be
made to very less numbers.
We basically ignore half of the elements just after one comparison.
1. Compare x with the middle element.
2. If x matches with middle element, we return the mid index.
3. Else If x is greater than the mid element, then x can only lie in right half subarray after the
mid element. So we recur for right half.
4. Else (x is smaller) recur for the left half.

Pseudocode :-

The pseudocode of binary search algorithms should look like this −

Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched

Set lowerBound = 1
Set upperBound = n

while x not found

if upperBound < lowerBound
EXIT: x does not exists.

set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

if A[midPoint] < x
set lowerBound = midPoint + 1

if A[midPoint] > x
set upperBound = midPoint - 1

if A[midPoint] = x
EXIT: x found at location midPoint
end while

end procedure

Time Complexity:
The time complexity of Binary Search can be written as
T(n) = T(n/2) + c
The above recurrence can be solved either using Recurrence T ree method or Master method. It
falls in case II of Master Method and solution of the recurrence is Theta(Log n).

Page no. -11

COMPUTER SCIENCE PRANAB SAHA([Link](H), MCA) Å 9088134887
Auxiliary Space: O(1) in case of iterative implementation. In case of recursive
implementation, O(Logn) recursion call stack space.

6) Write short notes & algorithm on Linear search ?

Linear search is a very simple search algorithm. In this type of search, a sequential search is
made over all items one by one. Every item is checked and if a match is found then that
particular item is returned, otherwise the search continues till the end of the data collection.

Algorithm

Linear Search ( Array A, Value x)

Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit

Pseudocode

procedure linear_search (list, value)

for each item in the list

if match item == value
return the item's location
end if
end for

end procedure
The time complexity of above algorithm is O(n).
Linear search is rarely used practically because other search algorithms such as the binary
search algorithm and hash tables allow significantly faster searching comparison to Linear
search.

Page no. -12