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

Ask an Expert

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

Write your message here..

Related Questions

The time and space complexities of an algorihm, Relation between the time a... Relation between the time and space complexities of an algorithm The examining of algorithm focuses on time complexity and space complexity. As compared to time analysis, the a

What is ruby, What is Ruby Ruby has numerous simple types, including nu... What is Ruby Ruby has numerous simple types, including numeric classes such as Integer, Fixnum, Bignum, Float, Big Decimal, Rational, and Complex, textual classes like String,

Siso-4bit register, explain working of siso-register to store 1011 and show... explain working of siso-register to store 1011 and show timing diagram &table

Relationship between shortest path distances of modified, a) Given a digrap... a) Given a digraph G = (V,E), prove that if we add a constant k to the length of every arc coming out from the root node r, the shortest path tree remains the same. Do this by usin

Multidimensional array, Q. The system allocates the memory for any of the m... Q. The system allocates the memory for any of the multidimensional array from a big single dimensional array. Describe two mapping schemes that help us to store the two dimensi

Column major representation, Column Major Representation In memory th... Column Major Representation In memory the second method of representing two-dimensional array is the column major representation. Under this illustration, the first column of

Function performs multiplication of two numbers, You need to write a functi... You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl

How can a lock object be called in the transaction, How can a lock object b... How can a lock object be called in the transaction? By calling Enqueue and Dequeue in the transaction.

What are stored and derived attributes, What are stored and derived attribu... What are stored and derived attributes?  Stored attributes: The attributes kept in a data base are called stored attributes.  Derived attributes: The attributes that are

Complete trees, This is a k-ary position tree wherein all levels are filled... This is a k-ary position tree wherein all levels are filled from left to right. There are a number of specialized trees. They are binary trees, AVL-trees, binary search trees, 2