This is more of an self defined programming exercise than a real problem. I have an array of java.lang.Comparable items. I need to maintain two pointers (an index into the array i.e., int values) i,j . i starts at the beginning of array and moves right until it encounters an element which is less than or equal to the previous element. When it does it stops moving right and ends up pointing to the element which is out of order(element which is not greater than the previous). Similarly j starts at the end of the array and moves left until it finds an element which is not less than the previous.
Also, I need to make sure that the indices don't run out of the array i.e., i cannot go below 0 and j cannot go above arraylength-1
lets say we have an array of 5 elements.
i = 0;
j = 4;(which is the arraylength-1 )
if C,D,E,F,G is the array ,the final values of i and j will be
i = 4 and j = 0
if array is J,D,E,F,G ,the final values of i, j will be
i = 0 , j = 0
if array is B,C,A,D,G , final values of i,j will be
i = 2 , j = 1
I tried to code the logic for moving i to the right, using a while loop as below. I was able to get it working for the i pointer in two cases.
public class PointerMovement{
public static void ptrsPointToOutOfOrderElements(Comparable[] a){
int lo = 0;
int hi = a.length-1;
int i = lo;
int t=i+1;
int j = hi;
//only for moving i to the right .
while(less(a[i],a[t])){
if(t == hi){
i=t;
break;
}
i++;
t++;
}
i=t;
for(Comparable x:a){
System.out.print(x+",");
}
System.out.println();
System.out.println("bad element or end of array at i="+i+"==>"+a[i]);
}
private static boolean less(Comparable x,Comparable y){
return x.compareTo(y) < 0;
}
public static void main(String[] args) {
String[] a = new String[]{"C","D","E","F","G"};//works
//String[] a = new String[]{"B","C","A","D","G"};//works
//String[] a = new String[]{"J","D","E","F","G"};//fails!
ptrsPointToOutOfOrderElements(a);
}
}
My line of reasoning given below
I maintain i=0; and another variable t=i+1
when the while loop fails, less(a[i],a[t]) is false .We need to return a pointer to a[t] which is out of order. so i=t and return i.
if we reach right end of array, the test if(t == hi) passes and we assign i=t and now i points to end of array.
However, the code fails when the out of order element is in the 0th position in the array.
J,D,E,F,G
Instead of i (=0) we get i=1 because i=t is assgined.i ends up pointing to D instead of J.
Can someone point me in the right direction?
update:
this seems to work
public static void ptrsPointToOutOfOrderElements(Comparable[] a){
int lo = 0;
int hi = a.length-1;
int i = lo;
while(less(a[i],a[i+1])){
if(i+1 == hi){
break;
}
i++;
}
i++;
int j = hi;
while(less(a[j-1],a[j])){
if(j-1 == lo){
break;
}
j--;
}
j--;
for(Comparable x:a){
System.out.print(x+",");
}
System.out.println();
if(i>=j){
System.out.println("pointers crossed");
}
System.out.println("bad element or end of array at i="+i+"==>"+a[i]);
System.out.println("bad element or end of array at j="+j+"==>"+a[j]);
}
I do not think you have a problem: String[] a = new String[]{"C","D","E","F","G"};//works, index should be 4 (but should it be so? It would indicate that G is out of order while it is not. I think you should return 5, indicating that none is out of order. String[] a = new String[]{"B","C","A","D","G"};//works, index should be 2 as A is out of order String[] a = new String[]{"J","D","E","F","G"};//works since the first out of order element is indeed D, with index 1