Tag Archives: sorted

Detecting whether a given integer array is sorted

Today I will discuss how to test or find whether a given integer array is sorted or not. The array will be considered to be sorted if all the elements of the array are in ascending order or descending order.

An array is considered to be in ascending order if each element of an array is smaller than the next element. If any two successive elements of an array are such that the first is larger than the second then the array cannot be in ascending order. Similarly, An array is considered to be in descending order if each element of an array is larger than the next element. If any two successive elements of an array are such that the first is smaller than the second then the array cannot be in descending order.

The programming implementing the above logic is as follows:

class Sorting{
    public static boolean isSorted1(int a[]){
        boolean isAscending=true;
        for(int i=0; i < a.length-1; i++){
            if(a[i]>a[i+1]){
                isAscending=false;
                break;
            }
        }
        if(isAscending) return true;
        boolean isDescending=true;
        for(int i=0; i < a.length-1; i++){
            if(a[i] < a[i+1]){
                isDescending=false;
                break;
            }
        }
        return isDescending;
    }
    public static void main(String[] args){
	int[] a={-20, -10, 10, 20};
	int[] b={20, 10, -10, -20};
	int[] c={10, 20, 10 , 20};
	System.out.println(isSorted1(a));
	System.out.println(isSorted1(b));
	System.out.println(isSorted1(c));
    }
}

In the above Java program we are first testing the array elements for ascending order, if the array is found to be in ascending order we will returning true. If the array is not in ascending order then it implies that either the array is sorted in descending order or it is not sorted at all. We will then proceed to test the array for descending order, if the array is found to be in descending order, we will return true else we will return false. That is, if the array is not in ascending order then the status of the test for descending order decides whether the array is sorted or not.
The above code will give correct answer and can be easily understood, but if we look carefully we can easily see that the body of the two loops are quite similar. It’s possible to do everything in one loop with slight modifications as follows:

class Sorting{
    public static boolean isSorted1(int a[]){
        boolean isAscending=true;
        for(int i=0; i < a.length-1; i++){
            if(a[i] > a[i+1]){
                isAscending=false;
                break;
            }
        }
        if(isAscending) return true;
        boolean isDescending=true;
        for(int i=0; i < a.length-1; i++){
            if(a[i] < a[i+1]){
                isDescending=false;
                break;
            }
        }
        return isDescending;
    }

    public static boolean isSorted2(int a[]){
        boolean isAscending=true, isDescending=true;
        for(int i=0; i < a.length-1; i++){
            if(a[i] > a[i+1]) isAscending=false;
            if(a[i] < a[i+1]) isDescending=false;
            if(!isAscending && !isDescending) break;
        }
        return isAscending || isDescending;
    }

    public static void main(String[] args){
        int[] a={-20, -10, 10, 20};
        int[] b={20, 10, -10, -20};
        int[] c={10, 20, 10 , 20};

        System.out.println(isSorted1(a));
        System.out.println(isSorted1(b));
        System.out.println(isSorted1(c));

        System.out.println(isSorted2(a));
        System.out.println(isSorted2(b));
        System.out.println(isSorted2(c));
    }
}

In the above Java program isSorted2() function implements the improvised logic. Other than putting both the if statements inside the body of the loop we have added one more if statement to abort further testing as soon as it’s known that the array is neither sorted in ascending order nor sorted in descending order.