University AI Course: Search Algorithm Analysis and Implementation

This assignment delves into the analysis of search algorithms within the realm of Artificial Intelligence. It explores two primary sorting algorithms: selection sort and insertion sort, demonstrating their application in finding the five elements from an array that minimize the sum of squares. The assignment provides detailed pseudocode for both algorithms, explaining their operational steps and providing examples. The selection sort algorithm's time complexity is analyzed as O(n^2), while the insertion sort's time complexity is examined in both best-case O(n) and worst-case O(n^2) scenarios. The assignment concludes by comparing the efficiency of the two algorithms, highlighting the potential benefits of insertion sort in certain situations. This analysis provides a comprehensive understanding of the practical application and performance characteristics of these fundamental search algorithms.

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

1
ARTIFICIAL INTELLIGENCE
Abstract:
Searching algorithms are very common in artificial intelligence as they are employed based
on their advantage and efficiency on the given problem. The searching algorithms are
basically used to fetch an element stored in a single or multidimensional array where it stored
along with other elements. The type of search operation classifies the searching algorithms in
two categories namely sequential search and Interval search. Sequential search operates
traversing an array sequentially by checking each of the element in the array. Linear search is
an example of sequential search type. The interval search is applied particularly on sorted
arrays and these are generally have less time complexity than the sequential search
algorithms. This is because the in interval search the centre of a array structure is targeted and
based on the centre the search space is divided in two halves of approximately same length.
Binary search algorithm falls under interval search.

2
ARTIFICIAL INTELLIGENCE
Introduction:
Now, in this particular research two search algorithms are applied two find the minimum 5
values from an array which makes the sum of square minimum. Now, sorting the array in
ascending order gives the first five elements of the array which has the minimum sum of
square as square of a number is always positive. Hence, two algorithms are applied to sort the
array in ascending order (Wu and Chiang 2018). The chosen two sorting algorithms are
selection sort and bubble sort as both are very simple to implement and efficiently applied on
any data array.
Search 1:
Now, as mentioned previously the searching algorithms are basically sorting algorithms for
the case as for finding the five elements which gives smallest sum of square from a list of
array of length more than 5, the list is needed to be sorted first and then the first five elements
can easily be chosen. The first sorting algorithm is the selection sort algorithm in which the
minimum of the array is first calculated and placed in the left of the list (Mohammed,
Amrahov and Çelebi 2017). Then the minimum of the rest of the array is calculated and it is
placed in just right of the first minimum. The minimum of a list can be calculated by iterating
through the list pairwise and keeping the updated minimum in the memory.
Pseudo code of search 1:
Input array of length n.
Define sorted_array = selection_sort(array):
sorted_array = [];
for i=n to 1:
min = Min_list(array) to i elements.

3
ARTIFICIAL INTELLIGENCE
sorted_array = [sorted_array, min];
end for
end selection_sort() return sorted_array.
five_elements = sorted_array(1st to 5th elements)
Define min = Min_list(array):
min = 1st element of array
for i=1 to length(array) – 1
if (i+1)th element < min:
min = (i+1)th element
else:
min = min
end if
end for
end Min_list() return min.
The main idea of the selection sort given in pseudo code can be explained by the following
steps.
Let given an array S of selection sort of length n.
1. Find the smallest item in S.
2. Place the minimum at the beginning of sorted array

4
ARTIFICIAL INTELLIGENCE
3. Reduce n by 1 by removing minimum from list and repeat from step 1 until n= 1.
As an example for finding 5 elements from an array to make a array such that
∑
i=1
5
xi
2 is minimum let the given array is x = 29,10,14,13,37,51,62,91.
1st step:
Min(29,10,14,13,37,51,62,91) = 10
Array = [10]
2nd step:
Min(29,14,13,37,51,62,91) = 13
Array = [10,13]
3rd step:
Min(29,14,37,51,62,91) = 14
Array = [10,13,14]
4th step:
Min(29,37,51,62,91) = 29
Array = [10,13,14,29]
Proceeding similarly the sorted list will be
Array = [10,13,14,29,37,51,62,91]
Now, the first five elements are 10,13,14,29,37 for which the sum of square will be
minimum.

5
ARTIFICIAL INTELLIGENCE
This can also be applied for negative numbers in the list and for that case all the numbers in
the list are first squared and the then those square number are sorted and first five of them are
chosen.
Search 2:
Now, another sorting algorithm is insertion sort which is just like sorting cards which playing
a cards game. The cards can be considered as the elements of the array can be arranged
according to their numbers (Qu et al. 2019). The only difference is that the numbers are only
numeric and no colours are there in the numbers like the cards. The idea of the insertion sort
is given below.
1. Start with the first number in the array
2. Pick the next number in the array and compare it with the first and arrange in proper sorted
manner.
3. Pick the next number and repeat 2 until the end of the array.
Pseudo code of insertion sort:
Input array of length n.
Define sorted_array = insertion_sort(array,n):
for i = 2 to n:
next_item = ith item in array
for j = i-1 to 1 and array[j] > next_item:
array[j+1] = array[j]
end for
array[j+1] = next_item

6
ARTIFICIAL INTELLIGENCE
end for
sorted_array = array
end insertion_sort() return sorted_array
Now, the same example of x = 29,10,14,13,37,51,62,91 is sorted by insertion sort as given
below.
Step 1:
Pick = 29
Array = [29]
Step 2:
Pick =10
Arrange [29,10]
Array = [10,29]
Step 3:
Pick = 14
Arrange [10,29,14]
Array = [10,14,29]
Step 4:
Pick = 13
Arrange [10,29,14,13]
Array = [10,13,14,29]

7
ARTIFICIAL INTELLIGENCE
In the similar way finally the arranged array will be
Array = [10,13,14,29,37,51,62,91]
Conclusion:
In conclusion it can be stated that the two algorithms namely the selection sort and insertion-
sort algorithms are successfully applied to find the five numbers from an array which
minimizes the sum of square of 5 elements from a list. The selection sort algorithm operates
in two loops in the outer loop the minimum of the array is calculated in steps and in the inner
loop the calculation of minimum of executed and in worst case both has n operations which is
the length of the array. Hence, the time complexity of the selection sort algorithm is O ( n2 ). In
the insertion sort the outer loop is executed for n-1 times and in the best case scenario
condition array[j] > next_item is false always and no data shifting is required and hence in
best case the time complexity of insertion sort is O(n). However, in the worst case scenario in
the inner loop the array is reversely sorted and thus condition array[j] > next_item is always
true and thus insertion always needed to be performed in the front and thus in worst case the
time complexity of Insertion sort is O ( n2 ) (Wang et al. 2015) . Hence, it can be stated that
insertion sort is some cases beneficial than the selection sort algorithm.

8
ARTIFICIAL INTELLIGENCE
References:
Mohammed, A.S., Amrahov, Ş.E. and Çelebi, F.V., 2017. Bidirectional conditional insertion
sort algorithm; An efficient progress on the classical insertion sort. Future Generation
Computer Systems, 71, pp.102-112.
Wu, C.M. and Chiang, Y.C., 2018, May. Insertion Sort Circuit Design Applied on the
Median Filter. In 2018 IEEE International Conference on Consumer Electronics-Taiwan
(ICCE-TW) (pp. 1-2). IEEE.
Qu, L.P., Lu, Z., Liu, C.J. and He, C.L., 2019, November. A Sort Method of Balancing
Capacitor Voltage of MMC. In 2019 18th International Symposium on Distributed
Computing and Applications for Business Engineering and Science (DCABES) (pp. 241-244).
IEEE.
Wang, R., Cao, D., Zang, Z. and Yu, Y., 2015, January. A Stable Quick Sort Algorithm
(SQSA) for fragment-continuity-sequential data. In Electronics, Information Technology and
Intellectualization: Proceedings of the International Conference EITI 2014, Shenzhen,
China, 16-17 August 2014 (p. 25). CRC Press.