Analysis of Selection Sort, Merge Sort, and Queue Algorithms Report

This report provides a comprehensive overview of sorting algorithms, specifically focusing on selection sort, merge sort, and queue data structures. It begins with an introduction to sorting, emphasizing its importance in arranging data for efficient retrieval. Part 1 delves into selection sort, explaining its in-place comparison method and providing code examples. The report then analyzes its running time, memory requirements, and stability. Part 2 explores merge sort, highlighting its divide-and-conquer approach and presenting code implementations. It discusses the algorithm's key steps, time complexity, and space complexity. Part 3 shifts the focus to de-queues, queues, and priority queues, defining their functionalities and illustrating their applications with code. The report concludes by summarizing the discussed algorithms and their real-world implications, with a note on the NetBeans platform used for code implementation. The assignment also includes references to relevant research papers.

Running head: SORTING ALGORITHMS 1
Assignment
Student
Course
Instructor
Date

SORTING ALGORITHMS 2
Contents
Introduction....................................................................................................................................3
Part 1...............................................................................................................................................3
Selection Sort...............................................................................................................................3
Part 2...............................................................................................................................................7
Merge Sort...................................................................................................................................7
Part 3.............................................................................................................................................14
De-queues, Queues, and Priority Queues..................................................................................14
Conclusion....................................................................................................................................17

SORTING ALGORITHMS 3
Introduction
Sorting is basically an arrangement of data in ascending or descending order. Sorting
helps in finding the required items quickly. In real life there are many which we required to
search for particular items such as roll numbers in a given list. It arranges data in a proper
sequence, hence sorting algorithms were introduced.
Part 1
Selection Sort
Selection sort in an algorithm used for sorting with a sort of in-place comparison. In
selection sort algorithm the array is sorted by repeating the finding of minimum element from the
array which is not sorted (Shin & Miyazaki, 2016). And the beginning element is kept at the
beginning of the array. The following code to be implemented:
System.out.print("Enter the Elements to be sorted: ");
for(m=0; m<size; m++)
{
arr[m] = sc.nextInt();
}
for(m=0; m<size; m++)
{
for(n=m+1; n<size; n++)
{
if(arr[m] > arr[n])

SORTING ALGORITHMS 4
{
temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
}
}
}
System.out.print("The sorted array is:\n");
for(m=0; m<size; m++)
{
System.out.print(arr[m]+ " ");
}

SORTING ALGORITHMS 5

SORTING ALGORITHMS 6
Output:
There are different criteria used for selection sorting algorithm:
 Running time: A basic sorting algorithm needs O (N2) steps for sorting N random
arranged items. O (N log N) is the time complexity during the implementation of
a complex program.
 Memory Requirements: Sorting algorithm requires extra memory. No additional
memory is required for in place sorting algorithms (Sangwongwanich et al.,
2016). Extra N memory words for list of pointers is required for linked list.
 Stability: Sorting algorithm’s ability for preserving respective order for equal keys
within a file.
Consider a pile of electricity bills is there for last 12 months and the bills are to be
arranged in order from January to October. The bill of January is to be found from the pile and
then search the remaining pile to find bill of February and put it behind January. Proceed in this
way until all the bills are placed in ascending sequence. This is done with selection sort.
Within quadratic sorting algorithms, generally selection sort’s performance is better than
other sorting algorithms. Insertion sort and selection sort are almost identical. However, selection

SORTING ALGORITHMS 7
sort is preferred over insertion sort for its time complexity. Though merge sort outperforms
selection sort on larger items.
References
Sangwongwanich, A., Mathe, L., Teodorescu, R., Lascu, C., & Harnefors, L. (2016, September).
Two-dimension sorting and selection algorithm featuring thermal balancing control for
modular multilevel converters. In 2016 18th European Conference on Power Electronics
and Applications (EPE'16 ECCE Europe) (pp. 1-10). IEEE.
Shin, K., & Miyazaki, S. (2016). A fast and accurate feature selection algorithm based on binary
consistency measure. Computational Intelligence, 32(4), 646-667.
Part 2
Merge Sort
Merge Sort is a general-purpose algorithm, which is based on comparison. It constructs a stable
sort by keeping the elements in the order. Dividing of the entire array and the merging of sub-
array takes place through bottom-up implementation (Friedman, 2018). Merge sort can be
implemented with the following code:
{
int l = mid - beg + 1;
int r = end - mid;
int LeftIndex[] = new int [l];
int RightIndex[] = new int [r];

SORTING ALGORITHMS 8
for (int m=0; m<l; ++m)
LeftIndex[m] = arr[beg + m];
for (int n=0; n<r; ++n)
RightIndex[n] = arr[mid + 1+ n];
int m = 0, n = 0;
int j= beg;
while (m<l&&n<r)
{
if (LeftIndex[m] <= RightIndex[n])
{
arr[j] = LeftIndex[m];
m++;
}
else
{
arr[j] = RightIndex[n];
n++;

SORTING ALGORITHMS 9
}
j++;
}
while (m<l)
{
arr[j] = LeftIndex[m];
m++;
j++;
}
while (j<r)
{
arr[j] = RightIndex[n];
n++;
j++;
}
}
void sort(int arr[], int beg, int end)
{

SORTING ALGORITHMS 10
if (beg<end)
{
int mid = (beg+end)/2;
sort(arr, beg, mid);
sort(arr , mid+1, end);
merge(arr, beg, mid, end);
}
}
public static void main(String args[])
{
int arr[] = {90,23,101,45,65,23,10,89,3,23};
mergesort ob = new mergesort();
ob.sort(arr, 0, arr.length-1);
System.out.println("\nSorted array");
for(int i =0; i<arr.length;i++)
{
System.out.println(arr[i]+"");
}

SORTING ALGORITHMS 11

SORTING ALGORITHMS 12

SORTING ALGORITHMS 13
Output:
Using Merge sort is advantageous as it can read the input during the building step of the
program is sequential (Marszałek, 2017). It uses less comparison during implementation, which
maintains the original position of the elements with respect to each other.
Key steps followed in Merge sort:
1. In Merge sort “divide and conquer” algorithm is applied which means mainly two steps
are involved, Divide and Conquer.
2. The entire input array is divided into two halves and the middle element is considered as
pivot element.
3. In the step of Divide, recursive method is carried out until there are no more arrays left
to divide into half.
4. In Conquer step, sorting and merging of the arrays are carried out through bottom-up
approach.
Suppose a queue of runners is there with numbers glued on their T-shirt and they
have to stand sequentially according to the order. Consider the queue as an entire array of count

SORTING ALGORITHMS 14
‘16=n’ hence, the whole array would be divided into sub-arrays. Firstly, the queue is divided into
two sections containing ‘8=n/2’ runners in each. Then similarly, each 8 runners are divided into
‘4=n/4’ after that into two, which is equal to n/8. Now, the first two runners will swap their
places with each other so that the one with smaller number will stand in front of the greater one.
Then the any four runners would compare and swap themselves with other four, since the
merging part carries the recursive method that’s why the sequence is n/8, n/4, n /2.
For merge sort time complexity is O (n log n) during worst case and its space
complexity is O (n). Whereas Quick sort’s time complexity in average case is O (n log n) and in
case of space complexity it’s O (n2).
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).
Marszałek, Z. (2017). Parallelization of modified merge sort algorithm. Symmetry, 9(9), 176.
Part 3
De-queues, Queues, and Priority Queues
A queue is a catalogue where an element is inserted from one end and removed from
another end. De-queue is a catalogue where insertion can be done from both ends (Braginsky,
Cohen & Petrank, 2016). De-queue can be used as a stack and as a list at same time. There are no
ends in priority queue. Elements are inserted in any order in priority queue and elements are
removed in sorted order.
A queue follows a particular order of First-In-First-Out (FIFO) for the performance of
operations. A de-queue allows insertion and deletion from both ends (Dudin et al.,2016). In

SORTING ALGORITHMS 15
priority queue, items can be added at any point of time, however only the item with the highest
priority can be removed.
The following code can be implemented in the queue program:
{
Queue<Integer> l = new LinkedList<>();
for (int m=0; m<20; m++)
l.add(m);
System.out.println("Elements of queue is:"+l);
int delete = l.remove();
System.out.println("removed element is:" + delete);
System.out.println(l);
int head = l.peek();
System.out.println("head of the queue is:" + head);
int size = l.size();
System.out.println("Size of the queue is:" + size);
}

SORTING ALGORITHMS 16
Output:
Consider a scenario where a retail website serves items to many users. All requests can be
serviced at the same time, only a few orders can be handled at once. It would be a fair policy to

SORTING ALGORITHMS 17
implement queue ADT logic, that is, first-come-first-serve technique. A queue would be most
appropriate for the situation.
Priority queue is more important than queue as it uses heap with O (log N) time
complexity for insertion and deletion and O (N) for building initially, whereas time complexity is
O (1) for insertion and O (N) for deletion for one operation.
References
Braginsky, A., Cohen, N., & Petrank, E. (2016, August). CBPQ: high performance lock-free
priority queue. In European Conference on Parallel Processing (pp. 460-474). Springer,
Cham.
Dudin, A. N., Lee, M. H., Dudina, O., & Lee, S. K. (2016). Analysis of priority retrial queue
with many types of customers and servers reservation as a model of cognitive radio
system. IEEE Transactions on Communications, 65(1), 186-199.
Conclusion
The programs or codes that are involved in the assignment has been implemented in Net-
Beans platform. Merge sort and Selection sort are the sorting algorithm which have real life
implications. And the queue is an essential data structure, which is similar to real life queue
before cinema hall, ticket queue, etc. These codes are basically to sort the data which are initially
unarranged.