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

The maximum degree of any vertex in a simple graph with n vertices is (n-1) is the maximum degree of the vertex in a simple graph.

AVL trees and the nodes it contains must meet strict balance requirements to maintain O(log n) search time. These balance restrictions are kept maintained via various rotation func

Overlapping or Intersecting A polygon overlaps or intersects the current background if any of its sides cuts the edges of the viewport as depicted at the top right corner of th

Question 1. How can you find out the end of a String? Write an algorithm to find out the substring of a string. 2. Explain the insertion and deletion operation of linked lis

For AVL trees the deletion algorithm is a little more complicated as there are various extra steps involved in the deletion of node. If the node is not a leaf node, then it contain

Illustrate Trivariate Colour Models Conventional colour models based on the tristimulus theory all contain three variables and so are called trivariate models. Let us now consi

SPARSE MATRICES Matrices along with good number of zero entries are called sparse matrices. Refer the following matrices of Figure (a)

#question. merging 4 sorted files containing 50,10,25,15 records will take time?

The above 3 cases are also considered conversely while the parent of Z is to the right of its own parent. All the different kind of cases can be illustrated through an instance. Le