Google Answers Logo
View Question
 
Q: Sort numbers from two lists ( No Answer,   5 Comments )
Question  
Subject: Sort numbers from two lists
Category: Computers > Algorithms
Asked by: outmarcus-ga
List Price: $2.00
Posted: 23 Jun 2006 06:00 PDT
Expires: 23 Jul 2006 06:00 PDT
Question ID: 740474
Hello,

I have two ordered lists LIST1 and LIST2 which elements are composed
of a field named "value" (an integer number) and a field named "prox"
that points on the following element ("nil" when there aren't new
elements).

The elements are disposes in each list in crescent order of value.

What's the optimal Java algorithm to print *in crescent order* the
combination of the elements of both lists?

For example, if the first list is formed by values 8, 12, 13, 28, and
the second by values 10, 11, 35, it must print the list 8, 10, 11, 12,
13, 28, 35.

Thanks in advance to all 

Markus
Answer  
There is no answer at this time.

Comments  
Subject: Re: Sort numbers from two lists
From: randability-ga on 24 Jun 2006 19:05 PDT
 
Hello.

To do this, I would first take the two lists into arrays.

list1[] and list[2]

I would then take the amount of elements in each array, and put them
into variables.

size1 = the size of list1[]
size2 = the size of list2[]

Then, I would create a third array the size of the first and second
combined to store the finished ordered numbers.

final[size1 + size2]

To start with, I would sort both of the lists from least to greatest.

void swap(int x, int y);  // Defining the function I'm using

int swap_var;  // For swapping

void order(){
	int comp;  // Maximum cur swaps needed to get in order
	int cur;  // Current position
	for(comp=0; comp<size1; comp++){
			for(cur=0; cur<size1; cur++){
				if(list1[cur]>list1[cur+1]){
					swap(cur,cur+1);
				}
			}
	}
	return;
}

void swap(int x, int y){
	swap_var = list1[x];
	list1[x] = list1[y];
	list1[y] = list1[swap_var];
	return;
}

Do the same for list2[].  (I'm aware this section is lacking
optimizations.  It's not my focus.)

Now, we'll compare each section to the other.

void print_to(int x, int y);
int x=0;
int y=0;
int max=size1+size2;
int current;

void make_final(){
	for(current=0; current<max; current++){
		(list1[x]<list2[y]) ? print_to(x,1) : print_to(y,2);
	}
}

void print_to(int x, int y){
	switch(y){
		case 1:
			x++;
			final[current]=list1[x];
		case 2:
			y++;
			final[current]=list2[x];
		default:
			end;
	}
}

There may be errors, which will jeopardise my chances of being chosen,
but I'm not in it for the money.  :D
Subject: Re: Sort numbers from two lists
From: outmarcus-ga on 26 Jun 2006 02:35 PDT
 
Very elegant, very clean, very well commented, in other words: GREAT!
Thank you very much, rand!!

The only problem is that I can't convert your comment to answer
(because you need to be an "expert") but you are morally the winner.
Subject: Re: Sort numbers from two lists
From: amitrangra-ga on 26 Jun 2006 21:47 PDT
 
I think the most optimised solution is to use the sorting method
provided by java-api itself.
The following program calculates the execution time also.
(The 2 lists are taken in the form of 2 arrays a1 & a2).
The execution time will come out to be 0. So use bigger arrays
to see the performance.


//*****************************************************************
import java.util.Arrays;

public class OptimalSol {
	
	public void sortedLists(int[] lst1, int[] lst2) {
		int[] result = new int[lst1.length+lst2.length];
		for(int i=0;i<lst1.length;i++) {
			result[i] = lst1[i];
		}
		for(int j=lst1.length;j<result.length;j++) {
			result[j] = lst2[j-lst1.length];
		}
		Arrays.sort(result);
		for(int i=0;i<result.length;i++) {
			System.out.println( result[i] );
		}
	}
	
	/* ======== */
	// Method to convert the time interval measured in milliseconda to proper
	// time format
	public long[] convert(long diff) {
		long[] result = { 0, 0, 0, 0 };
		long q = 0;
		long r = 0;

		q = diff / 1000;
		r = diff % 1000;
		result[3] = r;
		if (q < 60) {
			result[2] = q;
			return result;
		} else {
			r = q % 60;
			q = q / 60;
			result[2] = r;
			if (q < 60) {
				result[1] = q;
				return result;
			} else {
				r = q % 60;
				q = q / 60;
				result[1] = r;
				result[0] = q;
				return result;
			}
		}
	}

	/* ======== */
	
	
	public static void main(String[] args) {
		/* ======== */
		// To display starting time of execution in milliseconds
		long[] mills = { 0, 0 };
		long[] timediff = { 0, 0, 0, 0 };
		mills[0] = System.currentTimeMillis();
		System.out.println("Start time = " + mills[0] + " ms");
		/* ======== */
		
		int[] a1 = {8,12,13,28};//1st array
		int[] a2 = {10,11,35};  //2nd array
		new OptimalSol().sortedLists(a1,a2);
		
		
		/* ======== */
		// To display end time of execution in milliseconds & calculate the
		// difference
		mills[1] = System.currentTimeMillis();
		System.out.println("End time = " + mills[1] + " ms");
		timediff = new OptimalSol().convert(mills[1] - mills[0]);
		System.out.println("Time of execution = " + timediff[0] + ":"
				+ timediff[1] + ":" + timediff[2] + ":" + timediff[3]
				+ " (hh:mm:ss:ms)");
		/* ======== */
	}

}
//*****************************************************************
Subject: Re: Sort numbers from two lists
From: deepeshdeomurari-ga on 18 Jul 2006 09:40 PDT
 
Please clarify that solution should be optimized in what manner Speed,
Size or Memory.
I am giving a mix approach for this.
Step 1: First Select the length, Which list is bigger one. 
Step 2: Now use two pointers first pointer pointing to first member of
the first list(say list having more elements) (initially) and the
second pointer points to first member of the second list. say A(bigger
list), B(Smaller One)
Step 3: Now, Start tracing out the list without swaping (because
swapping do a lot of overhead) in the following manner
Start accepting element from small list  then check the first greater
occurence from the small list . Print each occurence of the A list
each time(except the case when value of A equal to Value of B
reached). upto greater then one was reached. On riching the greater
one. then point to that element in list A and print pointed element in
list B. If end of list reached simply print further elements of B.
Step 4: Continue step 3 for all values of list B. 
Comment on Efficiency:
1. All list will be travelled only one time.
2. You have asked only to print out the sorted list.(Not Storing that
list in memory :-))
3.  No Storage: Memory Optimization.
Note: We can start program without recording length of the list by
starting any one of list as A or B, which may result in quick
performance on average sized list)But its better to keep track at the
entry of that element to check out the length.

I think that according to your stated statement it is simple and
efficient solution).
Please let me know if this is your request answer
Subject: Re: Sort numbers from two lists
From: deepeshdeomurari-ga on 18 Jul 2006 09:48 PDT
 
Continue to previous Comment By me:
Example How the stuff will be done
A = 1,4,8,9,12,13
B = 2,5,9,12,14
p1 =1
p2 =2
print 1 
now p1=4 is greater then p2 so
print p2.. i.e 2
now take 5
again 4 is smaller... print 4 
8 is greater one 
so print 5 ..
Continued...
I am very sorry to inform u that previous one have two mistake.
At Step 3 and Step 4 : Condition: (Let i is the loop variable)
if(i>0 && A[i]==A[i-1])
continue;
similarly, when scanning B.

if(i>0 && B[i]==B[i-1])
continue;
 If greater one list ends i.e. A.
then print all the members remaining in Smaller list i.e.B.
please give me the feedback at deepesh_deomurari@fastmail.fm
__________________________________________________________________



(in both list)

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy