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