merge sorting, Data Structure & Algorithms

Assignment Help:
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

Related Discussions:- merge sorting

Calculus, basic calculation for algorith.

basic calculation for algorith.

Creation of Heap, Q. Create a heap with the given list of keys: ...

Q. Create a heap with the given list of keys: 8, 20, 9, 4, 15, 10, 7, 22, 3, 12                                                  Ans: Creation

Define wire-frame model, Define Wire-frame Model This skeletal view is ...

Define Wire-frame Model This skeletal view is called a Wire-frame Model. Although not a realistic representation  of the object, it is still very useful in the early stages of

Darw a flowchart for inputs number of hours of sunshine, This algorithm inp...

This algorithm inputs number of hours of sunshine recorded every day for a week (7 days). Output is the highest value for hours of sunshine and average (mean) value for numbers of

Stack, how we will make projects on stack in c?

how we will make projects on stack in c?

Representation of a sparse matrix, Let us assume a sparse matrix from stora...

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroe

Objectives of algorithms, After learning this, you will be able to: u...

After learning this, you will be able to: understand the concept of algorithm; understand mathematical foundation underlying the analysis of algorithm; to understand se

Abstract data type-tree, Definition: A set of data values & related operati...

Definition: A set of data values & related operations that are accurately specified independent of any particular implementation. As the data values and operations are described

What is called the basic operation of an algorithm, What is called the basi...

What is called the basic operation of an algorithm? The most significant operation of the algorithm is the operation contributing the most to the total running time is known as

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd