CODEWITHSUNDEEP
pythonarraysalgorithmsorting
user9790132
user9790132

Reputation:

How can I check if sorted and rotated array is in ascending or descending order?

I need to check if a sorted and rotated array is in ascending or descending order. I need to know it in order to find a rotation count via modified binary search.

For example:

[5, 6, 1, 2, 3, 4]

is in ascending order, but

[2, 1, 6, 5, 4, 3]

in in descending order

Python implementation would be awesome. Thanks for help!

Upvotes: 0

Views: 669

Answers (2)

Julez Julio
Julez Julio

Reputation: 13

am providing codes using Java may be you can check out if it would be helpful

public class IsSorted {

public static void main(String[] args){
    int[] list ={4,3,2,1};
    System.out.println(isSorted(list));

}

public static int isSorted(int[] a){

    if(a.length==0){
        return 1;
    }
    if(a.length==1){
        return 1;
    }

    int[] holdingArray=new int[a.length];

    for (int i =0; i<a.length; i++){
        holdingArray[i]=a[i];
    }


    int[] virtualIncreasedArray= new int[holdingArray.length];
    int[] virtualDecreasedArray= new int[holdingArray.length];
    sortIncrease(holdingArray);

    for(int i=0; i<holdingArray.length;i++){
        virtualIncreasedArray[i]=holdingArray[i];
    }
    sortDecrease(holdingArray);

    for(int i=0; i<holdingArray.length;i++){
        virtualDecreasedArray[i]=holdingArray[i];
    }

    //check if array is decreasing
    for(int i=0; i<virtualDecreasedArray.length;i++){
        if(virtualDecreasedArray[i]!=a[i]&&virtualIncreasedArray[i]!=a[i]){
            return 0;
        }

    }
    //check if array is increasing


    return 1;
}


static void sortIncrease(int[] a){
    for(int unsorted=a.length-1; unsorted>0; unsorted--){
        for(int i=0; i<unsorted;i++){
            if(a[i]>a[i+1]){
                swap(a,i,i+1);
            }
        }
    }
}


static void sortDecrease(int[] a){
    for(int unsorted=a.length-1; unsorted>0; unsorted--){
        for(int i=0; i<unsorted; i++){
            if(a[i]<a[i+1]){
                swap(a,i,i+1);
            }
        }
    }
}

static void swap(int[] a, int i, int j){
    if(i==j){
        return;
    }
    int temp = a[i];
    a[i]=a[j];
    a[j]=temp;
}

}

Upvotes: 0

Dave
Dave

Reputation: 9085

Simple constant time way is to check any 3 adjacent pairs. At most one contains the boundary, so the majority has the same order as the array.

These can be overlapping. eg, if a,b,c,d are adjacent in the array, the pairs ab, bc, cd are fine.

Wraparound is fine. eg for the array abc, check ab, bc, ca

Upvotes: 1

Related Questions