user1950349 - 4 months ago 287x

Java Question

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++) {

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 efficient way to deal with this problem?

Answer

I'll give you some hints :

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`

).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.

Source (Stackoverflow)

Comments