Analysis of Search Algorithms: Bubble Sort vs. Merge Sort in AI

This assignment delves into the realm of search algorithms within Artificial Intelligence, focusing on the comparison of two prominent sorting algorithms: Bubble Sort and Merge Sort. The core task involves applying these algorithms to an array to identify five elements whose sum of squares is minimized. The solution begins by squaring all elements of the array, followed by the application of Bubble Sort, which iteratively compares and swaps adjacent elements until the array is sorted. The document then presents the application of Merge Sort, a divide-and-conquer algorithm that recursively splits the array into smaller parts, sorts them, and merges them. Both algorithms are analyzed, and their efficiency is compared, highlighting Merge Sort's superior performance in terms of time complexity. The assignment provides pseudo-code for both algorithms, detailed steps of execution, and a conclusion summarizing the findings, making it a comprehensive analysis of search algorithms in AI.

Running head: ARTIFICIAL INTELLIGENCE
ARTIFICIAL INTELLIGENCE
Name of the Student
Name of the University
Author Note

1ARTIFICIAL INTELLIGENCE
Abstract:
Searching algorithm refers to any algorithm which solves a particular search problem. Search
problems can be of various types like to fetch some points or items from a data structure or
problems in combinatorial optimization, problems in constraint satisfaction, game theory
problems, industrial optimization problem etc. The search algorithms can be classified based
on the type of operation as linear searching, binary searching, comparison searching, digital
searching and hashing. Linear searching is the most simple and falls under comparison search
as comparison of items are performed in sequential manner. Binary searching cuts the entire
dataset into two halves repeatedly and then are merged after comparison. The digital
searching algorithms are applied based on the digit properties in data structure. In hashing no
comparison is performed but the elements are directly mapped to records by the hash
function.
Introduction:
Now, in this particular task two different searching algorithms are needed to be applied in
order the find five elements from a particular array (with length more than 5) such that the
sum of square of the elements is minimum.
The problem can be written mathematically by,
Find array x from S such that
∑
i=1
5
xi
2is Minimum.
Where, x is a set of 5 numbers such that
x → S ( a superset of x)

2ARTIFICIAL INTELLIGENCE
Now, for finding the five numbers from the array at first all of the elements are squared and
then two different sorting algorithms are applied to sort the squared array. Then the solution
can be easily found by just taking the first five elements of the sorted array. Hence, basically
two sorting algorithms are needed to be compared based on their operation and efficiency.
Thus two most common sorting algorithms bubble sort and merge sort are chosen which are
applied to a random array of more than 5 numbers to find the five numbers with minimum
sum of square.
Search 1 algorithm:
The first sorting algorithm which is applied to sort a given array is the bubble sort. In this
method each number is compared to the number next to it and swapping is performed if they
are not in order. This continues to the end of the array until no swapping is performed
(Mundra and Pal 2015).
Pseudo code of bubble sort:
Define sorted_array = bubblesort(array)
for i=length(array) -1 to 1:
for j=1 to i:
if array(j-1) > array(j)
tempval = array(j-1)
array(j-1) = array(j)
array(j) = tempval
end if
end for

3ARTIFICIAL INTELLIGENCE
end for
sorted_array = array
end bubblesort() return sorted_array
Now, let the given array is S = [-1,8,-9,10,2,7,-16,20,26].
Now, at first all the elements of the array are squared.
Hence, S2 = [1,64,81,100,4,49,256,400,676].
Now, bubble sort is applied to the above array. The first pass of bubble sort is shown below.
1,64,81,100,4,49,256,400,676
1,64,81,100,4,49,256,400,676
1,64,81,100,4,49,256,400,676
1,64,81,100,4,49,256,400,676
1,64,81,4,100,49,256,400,676
1,64,81,4,49,100,256,400,676
1,64,81,4,49,100,256,400,676
1,64,81,4,49,100,256,400,676
Now, after successive passes when no two elements are swapped then the array is sorted and
algorithm stops.
Finally, the sorted list = 1, 4, 49,64,81,100,256,400,676
Thus the minimum sum of square has the first five elements of the array which are 1, 4,
49,64,81 corresponding to -1,2,7,8 and -9 in the original array.

4ARTIFICIAL INTELLIGENCE

5ARTIFICIAL INTELLIGENCE
Search 2 algorithm:
Now, another algorithm for sorting can be applied for obtaining the same results is the merge
sort algorithm. Merge sort is a divide and conquer algorithm which repeatedly divides the
array into two halves until each list becomes single item and then they are merged with
comparison in the same order in which they are broken (Marszałek 2017). The final merge of
two lists gives the sorted data.
Pseudo code of merge sort:
Define mergesort(array)
n = length(array)
len1 = array[0 to n/2]
len2 = array[(n/2 + 1) to n]
len1 = mergesort(l1)
len2 = mergesort(l2)
end mergesort() return merge(l1,l2)
sorted_array = merge(l1,l2)
Define array3 = merge(array1,array2)
array3 = []
while array1 and array2 are non-empty:
if 1st array1 element > 1st array2 element:
concatenate 1st array2 element in end of array3
remove 1st array2 element from array2

6ARTIFICIAL INTELLIGENCE
else
concatenate 1st array1 element in end of array3
remove 1st array1 element from array1
end if
end while
while array1 is non-empty:
concatenate 1st array1 element in end of array3
remove 1st array1 element from array1
while array2 is non-empty:
concatenate 1st array2 element in end of array3
remove 1st array2 element from array2
end while
end merge() return array3
Now, merge sort is applied on the same data which is used in search 1. The square of
numbers are
S2 = [1,64,81,100,4,49,256,400,676].
Division steps:
[1,64,81,100,4] [49,256,400,676]
[1,64,81] [100,4] [49,256] [400,676]
[1,64] [81] [100] [4] [49] [256] [400] [676]

7ARTIFICIAL INTELLIGENCE
[1] [64] [81] [100] [4] [49] [256] [400] [676]
Merge steps:
[1,64] [81] [100] [4] [49] [256] [400] [676]
[1,64,81] [4,100] [49,256] [400,676]
[1,4,64,81,100] [49,256,400,676]
[1, 4, 49,64,81,100,256,400,676]
Thus the same sorted list is obtained and by taking the first elements and comparing with
their square roots the five numbers can be obtained as -1,2,7,8 and -9 for minimized sum of
square.
Conclusion:
Hence, in conclusion it can be stated that two sorting algorithms namely bubble sort and
merge sort are appropriately applied as search algorithms to find the five numbers from an
array with minimum sum of square. In worst case scenario the bubble sort algorithm run in
O ( n2 ) time 1,2,3,…n-1 operations are performed in that case for an array of length n as input.
However, worst case time complexity of merge sort is 2∑
i=0
logn
n=2nlog [ n ] =O(nlogn), where n
is the length of array. Thus merge sort performs a bit quicker than the bubble sort algorithm.

8ARTIFICIAL INTELLIGENCE
References:
Marszałek, Z., 2017. Parallelization of modified merge sort algorithm. Symmetry, 9(9), p.176.
Mundra, J. and Pal, M.B., 2015. Minimizing Execution Time of Bubble Sort
Algorithm. IJCSMC-ISSN: 2320–088X, 4(9), pp.173-181.