Analysis of Sorting Algorithms: A Comprehensive Report

Desklib provides solved assignments and past papers to help students succeed.

Data Structures and Algorithms

Table of Contents
Introduction......................................................................................................................................3
LO1:.................................................................................................................................................4
P1.................................................................................................................................................4
P2.................................................................................................................................................4
M1................................................................................................................................................5
M2................................................................................................................................................7
D1..............................................................................................................................................12
LO2................................................................................................................................................15
P3...............................................................................................................................................15
M3..............................................................................................................................................17
D2..............................................................................................................................................17
LO3................................................................................................................................................19
P5...............................................................................................................................................19
LO4................................................................................................................................................20
P6...............................................................................................................................................20
P7...............................................................................................................................................21
M5..............................................................................................................................................22
D4..............................................................................................................................................22
Conclusion.....................................................................................................................................23
References......................................................................................................................................24

Introduction
In this report, we will learn about data structures and their respective algorithms. We will analyse
various sorting algorithms. In addition, we will also find out what are asymptotic notations and
determine the worst, best and average case complexity of the various algorithm.

LO1:
P1
Define abstract data types and cover basic outline as well as its importance of lists, Stack,
Queue, Graph data structure, etc.
Abstract Data Type or ADT is a class for many objects which have their value predefined using
some collection of values or set of some operations. The ADT’s just only determines what
operations need to be performed but their method of performing is not described. For any
program, the programmer is only informed about what data type is going to be used but not the
part about how will it be used. We can also analyse ADT as the confidential structure which
hides the inner structure and data type’s design.
In this section, we will discuss 3 types of ADT which are,
1. List ADT
2. Stack ADT
3. Queue ADT
P2
What is stack, importance and explain the concept with a diagram and list and explain all
the functions?
Stacks data structure falls under the category of linear data structures, and its main property is
that it only follows a single order which is also the way of how operations are performed. The
order can be LIFO which means Last In First Out or FILO which means First In Last Out.

Figure 1: Stack representation
There are numerous numbers of examples of the stack, we can imagine on a table glass plated are
placed one over the another. The first place to be removed is the top one which means that the
bottom plate will be out from the stack at the longest period of time. This example is the LIFO
category.
There is a various number of functions in the stack and they are as follows with their
functionality:
 Push(): This is used to insert an element in the stack
 Pop(): This function is used in order to remove any element from the stack
 Peek(): This function will return the selected element at the top without removing it if the
stack is not empty.
 Size(): This function will return the number of elements present in the stack
 isEmpty(): This function will return true if the stack is empty, otherwise return false
 isFull(): This function will return true if the stack is full, otherwise return false
M1
What is Queue, importance and explain the concept with a diagram and list and explain all
the functions?
A Queue is also a member of the linear data structure, which also performs operations in a
certain order. The order of operation in Queue is FIFO which means First In First Out. A good

example of a Queue or FIFO is in a restaurant, where the first customer that comes into the
restaurant will get served first (Al-Bastami, et al., 2017).
Figure 2: Queue Representation

Output:
There are various functions used in the Queue data structure, which are as follows:
 enqueue(): This function is used to insert an element in the queue.
 dequeue(): This function is used to remove any element from the queue if the queue is not
empty.

 peek(): This function will return the element from the queue, is the size of the list is not
less than zero.
 Size(): This function will return the size of the queue.
 isEmpty(): This function will return true if there are no elements in the queue.
 isFull(): This function will return true of the queue is full, otherwise false.
M2
Show and demonstrate Mergesort
Merge sort algorithm falls under the same functionality as a divide and conquer algorithm. This
algorithm divides the input into two halves then after sorting those two halves it merges those
two halves by using the merge function. The merge function is merge (arr, l, m, r) which is the
main process for sorting two halves of the array then merging the said two halves. Below is
shown the details of the implementation of merge sort (Deitel, et al., 2016).
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for the first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for the second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)

Implementation of Merge Sort using C sharp
Figure 3: Code for Merge Sort

Figure 4: Output for Merger sort
Show and demonstrate Insertion sort
The way we use insertion sort is the same way we sort our playing card. First, we compare the
first to the element if the first number is larger than the second number then we switch them
using a sorting algorithm.
Algorithm
Sorting array arr[]
insertionSort(arr, n)
loop from( i=0; i<n-1;i++)
pick any element at position n.