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
GIVE TRACE OF BINARY SEARCH ALGORITHM BY USING A SUITABLE EXAMPLE.

Explain th term input and output-  Pseudocode Input and output indicated by the use of terms input number, print total, output total, print "result is" x and so on.

Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

You have to sort a list L having of a sorted list followed by a few "random" elements. Which sorting methods would be especially suitable for this type of task?   Insertion sort

Define the terms     i) Key attribute     ii) Value set  Key attribute:  An entity  type  usually  has  an attribute  whose  values  are  distinct  fr


You will write functions for both addition and subtraction of two numbers encoded in your data structure. These functions should not be hard to write. Remember how you add and subt

A circular queue can be implemented through arrays or linked lists. Program 6 gives the array implementation of any circular queue. Program 6: Array implementation of any Circu

An adjacency matrix representation of a graph cannot having information of : Parallel edges

What is quick sort? Quick sort is a sorting algorithm that uses the idea if split and conquer. This algorithm chooses an element called as pivot element; search its position in