user1950349 - 5 months ago 522
Java Question

# How to know if an array can be sorted by one swap or less?

Given an array with n elements, can we sort this array in ascending order by performing only one swap operation?

For example for below array:

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

We need to swap only 9 with 3 and that's only one swap operation by which my array can be in ascending order. If the array is already sorted in ascending order, then we can return true directly.

I started off below code but I am stuck and I am not sure how should I proceed?

``````public static boolean verifyOrder(int[] data) {
List<Integer> input = new ArrayList<Integer>();
for (int index = 0; index < data.length; 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 efficient way to deal with this problem?

1. You have to iterate over the array exactly once to verify it is already ordered (i.e. check that `data[i]<=data[i+1]` for each `i` from `0` to `data.length-2`).
2. If during this single iteration you find that `data[i]>data[i+1]` for some `i`, you know that `data[i]` is in the wrong place. If it's possible to do a single swap that will make the array ordered, you need to swap `data[i]` with something. In order to find which element to swap `data[i]` with, search for the smallest `data[j]` where `j>i`. After swapping `data[i]` with `data[j]`, you can iterate once more over the array to verify it is ordered.
At most you'll iterate twice over the array, which will give you `O(n)` running time.