User Account

All Pages

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

Depth First Search Through Un-weighted Connected Graph , Q. Write down the ...

Q. Write down the algorithm which does depth first search through an un-weighted connected graph. In an un-weighted graph, would breadth first search or depth first search or neith

Preorder - postorder and inorder, 1) preorder, postorder and inorder 2) ...

1) preorder, postorder and inorder 2) The main feature of a Binary Search Tree is that all of the elements whose values is less than the root reside into the nodes of left subtr

What is assertions and abstract data types, Assertions and Abstract Data Ty...

Assertions and Abstract Data Types Even though we have defined assertions in terms of programs, notion can be extended to abstract data types (which are mathematical entities).

Stack flowchart, example of stack using flowchart

example of stack using flowchart

Breadth first search, While BFS is applied, the vertices of the graph are d...

While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part

Program on radix sort., Write a program that uses the radix sort to sort 10...

Write a program that uses the radix sort to sort 1000 random digits. Print the data before and after the sort. Each sort bucket should be a linked list. At the end of the sort, the

Bubble sort, In this sorting algorithm, multiple swapping occurs in one pas...

In this sorting algorithm, multiple swapping occurs in one pass. Smaller elements move or 'bubble' up to the top of the list, so the name given to the algorithm. In this method,

String manipulation, what is string manipulation?

what is string manipulation?

Basic organization of computer system, what happen''s in my computer when ...

what happen''s in my computer when i input any passage

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

Write Your Message!

Captcha
Order Assignment

Featured Services

Order Now

Popular Subjects

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!

Submit Assignment

Academics

Major Subjects

Majors

Get In Touch

whatsapp: +91-977-207-8620

Phone: +91-977-207-8620

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

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