Java – how do I know if an array can be sorted by one or more swaps?

Given an array containing n elements, can we sort the array in ascending order by performing an exchange operation?

For example, the following array:

int[] data = {1,9,6,3}

We only need to swap with 9. There is only one swap operation. My array can be arranged in ascending order If the array has been sorted in ascending order, we can directly return true

I started the following code, but I got stuck. I don't know what I should do?

public static boolean verifyOrder(int[] data) {
    List<Integer> input = new ArrayList<Integer>();
    for (int index = 0; index < data.length; index++) {
        input.add(data[index]);
    }
    int j = 0;
    while (j < input.size() - 1 && input.get(j) <= input.get(j + 1)) {
        j++;
    }
    if (j == input.size() - 1) {
        // yes we can sort array with only one swap operation
        return true;
    }

    // not sure how should I proceed?
}

What is the effective way to deal with this problem?

Solution

I'll give you some tips:

>You must iterate the array once to verify that it has been sorted (that is, change the data [i] I = I [i] of each I from 0 to data length 2). > If in this single iteration, you will find that data [i] > data [I 1] for some of me, you know that data [i] is in the wrong place If you can do a single exchange to sort the array, you need to exchange data [i] In order to find which element is exchanged with data [i], search for the smallest data [J], where j > I. after exchanging data [i] with data [J], you can repeat it on the array to verify whether it is sorted

You will iterate over the array up to two times, which will give you o (n) runtime