SORTING ALGORITHMS2 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 ALGORITHMS3 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 ALGORITHMS6 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 implementationof 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 billsis 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 ALGORITHMS7 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. In2016 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];
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
SORTING ALGORITHMS13 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
Secure Best Marks with AI Grader
Need help grading? Try our AI Grader for instant feedback on your assignments.
SORTING ALGORITHMS14 ‘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 ALGORITHMS15 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 ALGORITHMS16 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
Paraphrase This Document
Need a fresh take? Get an instant paraphrase of this document with our AI Paraphraser
SORTING ALGORITHMS17 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. InEuropean 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.