Generate a single sorted list of all n elements, Data Structure & Algorithms

Q. Assume that we have separated n elements in to m sorted lists. Explain how to generate a single sorted list of all n elements in time O (n log m )?                                                   

Ans.

The list can be developed using Merge sort. Following is the method for it. Assume A is a sorted list with r elements and B is a sorted list with s elements. The operation that combines the elements of A and B into the single sorted list C with n = r +s elements is known as merging.

Procedure 1

MERGING(A, R, B, S, C)

Let A and B be the sorted arrays with R and S elements respectively. The

algorithm merges A and B into an array C with N= R + S elements.

1. [Initialize.] Set NA := 1, NB := 1 and PTR := 1.

2. [Compare.] Repeat while NA <=  R and NB <=  S : If A[NA] < B[NB], then ;

(a)  [Assign element from A to C.] Set C[PTR] := A[NA].

(b)  [Update pointers.] Set PTR := PTR + 1 and

NA := NA + 1. Else:

(a)   [Assign element from B to C.] Set C[PTR]

:= B[NB].

(b)   [Update pointers.] Set PTR := PTR + 1 and

NB := NB + 1.

[End of If structure.] [End of loop.]

3. [Assign remaining elements to C.] If NA > R, then:

Repeat for K = 0, 1, 2,...,S-NB:

Set C[PTR + K] := B[NB + K]. [End of loop.]

Else:

Repeat for K = 0, 1, 2, ..., R - NA:

Set C[PTR + K] := A[NA + K]. [End of loop.]

[End of If structure.]

4. Exit.

Procedure 2:

MERGE(A, R, LBA, S, LBB, C, LBC)

This procedure merges the sorted arrays A

and B into the array C.

1. Set NA := LBA, NB := LBB, PTR := LBC, UBA:= LBA + R - 1, UBB :=     LBB + S - 1.

2. call merging (A,UBA,B,UBB,C)

3. Return.

Procedure 3:

MERGEPASS(A, N, L, B)

The N-element array A consists of sorted subarrays where each subarray has L elements apart from possibly the last subarray, which can have fewer than L elements. The procedure merges the pairs of subarrays of A and assigns them to the array B.

1.   Set Q := INT(N/(2*L)), S:= 2*L*Q and R := N - S.

2.  [Use procedure2 to merge the Q pairs of subarrays.] Repeat for J = 1, 2, . . ., Q:

(a) Set LB := 1 + (2*J - 2) * L. [Finds lower bound of first array.]

(b) Call MERGE(A, L, LB, A, L, LB + L, B, LB). [End of loop.]

3.  [Only one subarray left ?] If R ?  L, then: Repeat for J = 1, 2, . . ., R: Set B(S + J) := A(S+J).

[End of loop.]

Else :

CALL MERGE(A, L, S + 1, A, R, L + S + 1, B, S + 1).

[End of If structure.]

4.   Return.

Procedure 4 MERGESORT( A, N)

This particular algorithm sorts the Nth element array A using an auxiliary array B.

1.   Set L:=1 . [ Initiliazes the number of elements in the subarrays.]

2.   Repeat Steps 3 to 6 while L

3.            Call MERGEPASS(A,N,L,B)

4.            Call MERGEPASS(B,N,2*L,A).

5.             Set L:= 4*L.

[End of Step 2 loop].

6.   Exit.

Posted Date: 7/13/2012 2:58:57 AM | Location : United States







Related Discussions:- Generate a single sorted list of all n elements, Assignment Help, Ask Question on Generate a single sorted list of all n elements, Get Answer, Expert's Help, Generate a single sorted list of all n elements Discussions

Write discussion on Generate a single sorted list of all n elements
Your posts are moderated
Related Questions
Any Binary search tree has to contain following properties to be called as a red- black tree. 1. Each node of a tree must be either red or black. 2. The root node is always b

In order to get the contents of a Binary search tree in ascending order, one has to traverse it in In-order

CIRCULARLY LINKED LISTS IMPLEMENTATION A linked list wherein the last element points to the first element is called as CIRCULAR linked list. The chains do not specified first o

Write an algorithm in form of a flowchart that takes temperatures input over a 100 day period (once per day) and outputs the number of days when temperature was below 20C and numbe

multilist representation of graph

need an expert to help me with the assignment

The space-complexity of the algorithm is a constant. It just needs space of three integers m, n and t. Thus, the space complexity is O(1). The time complexity based on the loop

It is a useful tool for indicating the logical properties of data type. It is a collection of values & a set of operations on those values. Methodically, "a TYPE is a set, & elemen

Define Binary Tree  A binary tree T is explained as a finite set of nodes that is either empty or having of root and two disjoint binary trees TL, and TR known as, respectively

There are three typical ways of recursively traversing a binary tree. In each of these, the left sub-trees & right sub-trees are visited recursively and the distinguishing feature