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

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

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.

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)");
		/* ======== */
	}

}
//*****************************************************************

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

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)