Summer 2019 PROG20799 Project: Algorithm Performance Analysis

This C programming project undertakes a comparative study of sorting and searching algorithms, fulfilling the requirements of the PROG20799 course. The project examines the theoretical performance and practical demonstration of various algorithms, including at least three sorting algorithms (with at least one having O(n*log n) or better efficiency) and at least two search algorithms (with at least one having O(log n) or better efficiency). The solution explores Selection Sort and Insertion Sort, along with Linear Search and Binary Search. The project analyzes time complexity and algorithm efficiency. It also includes an introduction explaining human-computer interaction, the core of the project, and a conclusion which summarizes the findings. The project is well-structured, providing an in-depth analysis of the algorithms, and includes references to support its claims.

TEMAOS [Company address]
C PROGRAMMING

1
Table of Contents
Introduction..........................................................................................................................................2
Sorting algorithms...............................................................................................................................3
Search algorithms................................................................................................................................5
Conclusion............................................................................................................................................8
References.............................................................................................................................................9
pg. 1

2
Introduction
The project is based on human-computer interaction which is used to determine
how competent humans are when interacting with a computer screen. For the
sorting algorithms, an array or a list of elements is provided as come parameter.
A comparison factor is then used as part of the elements. The comparison factor
is then used to determine the order of the new elements using a data structure of
choice. The structure is defined which is used to store the information about the
array elements. The sorting and search algorithms use a different order to
arrange the items. Such that the items can be arranged in ascending or
descending order depending on the order of choice and the number of elements
that are found in the array.
pg. 2

3
Sorting algorithms
1. Selection Sort
This algorithm is used to sort the elements that are found in the array by using a
loop to find the minimum element using the unsorted array and putting the
minimum element at the beginning of the array. The array is first divided into
two subarrays with each array containing a reference of the main array. The
subarrays are maintained by the algorithm for the given array until sorting all of
the elements in the array is done (Friedman, 2018). The sorting of the elements
in the array is done by using a repetitive method which loops over the elements,
each time determining the smallest element in the array and putting the element
in the lowest index of the array. Once all the elements of the main array are
sorted, then the subarrays are joined to form the sorted array.
During the procedure, there are two types of arrays which include the sorted
arrays contained in the sub-arrays and the remaining unsorted arrays.
The time complexity for the selection sort algorithm used O(n2) since in the main
loop there contains other two nested loops which are used to move through the
elements determining the smallest element among the given array (Mahdavi,
Fesanghary & Damangir, 2017).
During each of the iterative steps involved, the minimum element from the array
I picked and the array is moved to the sorted subarray which contains other
elements from the main array.
Successive sort of the elements in the array involves selecting all the elements
from the main array and moving them into the sorted subarray which contains
other elements from the unsorted array.
An example showing the operations that are performed:
arr[] = 64 25 12 22 11
pg. 3

4
// minimum element in the array with 5 elements from [0-5]
// place each of the minimum element in the first index of the array.
11 25 12 22 64
// minimum element in the array with 5 elements from [1-5]
// place the element at the beginning of elements [1-5]
11 12 25 22 64
// minimum element in the array with 5 elements from [2-5]
// place the element at the beginning of elements [2-5]
11 12 22 25 64
// minimum element in the array with 5 elements from [3-5]
// place the element at the beginning of elements [3-5]
11 12 22 25 64
pg. 4

5
Figure 1: Implementation of the algorithm
2. Insertion Sort
This algorithm involves picking an element from an index in the array and
placing the element in the previous index of the sorted sequence. For instance,
an element in the position is picked and moved into i-1 position in the array. If
the elements in the array are already sorted in reverse order, the algorithm takes
a minimum time of Order of n if the elements are already sorted. If the number
of elements found in the array is small, them a binary search insertion sort is
used to increase the speed of the comparisons and the number of iterations.
The use of a binary search is used to reduce the number of comparisons
performed during a normal insertion sort. Implementation of the binary sort
algorithm uses a binary search to enable find the index to insert the selected
element. A normal insertion sort starts with an empty sorted list. A loop is used
to loop through the elements and the nodes while inserting the current node into
the sorted list.
pg. 5

6
Search algorithms
Search algorithms are meant to retrieve items or elements from a structure
where they are contained. The algorithm can be classified as Iterative and
sequential depending on the type of search operation. For instance, Linear
Search uses a sequential algorithm which involves traversing through each of
the elements in the array until all the items in the array have been checked
(Rahim, Nurarif, Ramadhan, Aisyah & Purba, 2017).
An iterative loop is used to move through all the elements which are contained in
the array.
The binary search algorithm uses an interval search which is designed to check
through the sorted items stored in a structure. This type of algorithm is more
efficient than the linear search it targets the center of the items repetitively, the
search found is usually divided into a half to increase the speed of checking the
items in the structure.
A binary search is more efficient and faster than a linear search since it uses a
repetitive search for the items at the center of the array.
pg. 6

7
pg. 7

8
Conclusion
The choice of the algorithm for use, determine the complexity and the amount of
time that is used to sort the elements in the array. Each time an iterative loop is
used, each of the items is mapped sequentially into a position (Setiawan, 2016).
For instance, while using insertion sort and time complexity of O(N) while using
an already sorted array, the number of swaps performed for all the elements in
the array are reduced more than using bubble sort.
This makes insertion sort faster while using the time complexity of O(N) as
compared to the use of bubble sort. The total number of steps for performing the
iterative steps are also reduced. A simple insertion sort based algorithm inserts
every element from the array into the position during each of the iterations.
pg. 8

9
pg. 9

10
References
Friedman, J., 2018. An algorithm for finding best matches in logarithmic
expected time (No. SLAC-
PUB-1549). SLAC National Accelerator Lab., Menlo Park, CA (United
States).
Mahdavi, M., Fesanghary, M. and Damangir, E., 2017. An improved harmony
search algorithm for
solving optimization problems. Applied mathematics and computation,
188(2), pp.1567-1579.
Rahim, R., Nurarif, S., Ramadhan, M., Aisyah, S. and Purba, W., 2017, December.
Comparison
Searching Process of Linear, Binary and Interpolation Algorithm. In J. Phys.
Conf. Ser (Vol.
930, No. 1, p. 012007).
Setiawan, R., 2016, November. Comparing sorting algorithm complexity based on
control flow
structure. In 2016 International Conference on Information Management
and Technology
(ICIMTech) (pp. 224-228). IEEE.
pg. 10