merge sorting, Data Structure & Algorithms

ESO207: Programming Assignment 1
Due on 6 Sept, 2015. To be submitted online.
Problem In this assignment you are required to implement k-way Merge Sort algorithm. In this version partition the input sequence of integers into k almost equal (may di?er by at most 1) subsequences, recursively sort, and then merge the k sequences. Input: A positive integer n, a sequence of integers (a1,a2,...,an), and a positive integer k = 2. Goal: Design a program KWMS(A,i,j,k) which sorts in decreasing order the integers contained in an array A in the index range i : j (including i and j) using k-way merge. After the completion of sorting the program should print A[i : j] starting from the new line: The sorted list in the range i:j is ........ Details: Please implement the program by strictly following these step. 1. Use three global arrays A,B,C. A contains the input sequence. B is used to form a MaxHeap, and C is used for temporary storage. 2. Let a = d(j -i + 1)/ke,b = b(j -i + 1)/kc,r = (j -i + 1)%k (remainder of (j -i + 1)÷k). Partition the array A[i : j] into A[i : i+a-1],A[i+a : i+2a-1],...,A[i+(r-1)a : i+ra-1],A[i+ra : i + ra + b],A[i + ra + b : i + ra + 2b],.... 3. In order to perform k-way merge implement a MaxHeap on another array B. Let B be a 2D array with the range [0 : 1][1 : k]. To store integer x of subarray j by setting B[0][a] = x and B[1][a] = j. 4. To perform merge operation, ?rst enter the greatest element of each non-empty sub-array into the heap, starting from the leftmost subarray (lower indices to the higher indices). Then each time the greatest element is extracted from the Heap, identify its subarray from B[][1] and insert the next element from that subarray into the heap. If that sub-array becomes empty, then no insertion will occur. MaxHeap
1
must be implemented exactly the way we discussed in the class. Use HeapSize to keep track of the number of elements currently in the heap. 5. The merge must be done into array C and then its content must be transferred back to A. 6. Take the array A and C lengths to be 1000 each. 7. To help us evaluate the correctness of the program, please print from a fresh line Content of the heap is B[0][1],B[0][2],...,B[0][k] after each extraction+insertion (or after extraction, if no insertion happens) in the heap. At the end of the routine KWMS(A,i,j,k) put a print statement which prints from a fresh line The sorted list in the range i : j is A[i],A[i + 1],...,A[j]. Note that this being a recursive program this statement will get printed after each recursive call.
2
Posted Date: 8/30/2015 3:27:35 PM | Location : United States







Related Discussions:- merge sorting, Assignment Help, Ask Question on merge sorting, Get Answer, Expert's Help, merge sorting Discussions

Write discussion on merge sorting
Your posts are moderated
Related Questions
Explain Backtracking The  principal idea is to construct solutions single component  at a time  and evaluate such  partially constructed candidates as follows. If a partiall

Elaborate the symbols of abstract data type length(a)-returns the number of characters in symbol a. capitalize(a)-returns the symbol generated from a by making its first cha

A tree is a non-empty set one component of which is designated the root of the tree while the remaining components are partitioned into non-empty groups each of which is a subtree

what is multilist length file organisation? explain with an example

the above title please send give for the pdf file and word file

Draw a flowchart of a Booth''s multiplication algorithm and explain it.

given the string "Data Structures & , Algorithms", write a program that uses sequential search to return index of ''&''

Determine the Disjoint of division method A polygon is disjoint from the viewport if the x- and y-extents of the polygon do not overlap the viewport anywhere. In this case; reg

Determine YIQ Colour Model Whereas an RGB monitor requires separate signals for the red, green, and blue components of an image, a television monitor uses a single composite si

i want to write code for unification algorithm with for pattern matching between two expression with out representing an expression as alist