N. Kita - 1 year ago 63
C Question

# Sorting an integer circular array swapping elements with 1 in between

Given an integer circular array v, with n > 0 numbers, and only one possible move "m" is to swap one element with the one after 2 ahead.

I have to print a sequence of moves that sort v or say that's impossible (in c language)

Example:

initial: v = [8, 0, 5, 9, -1, 5]

after applying m to v[4]: v = [-1, 0, 5, 9, 8, 5]

after applying m to v[3]: v = [-1, 0, 5, 5, 8, 9]

Which is now sorted from it's 0 position. The output would be "4 3"

What I know up to this point:

- If there are an odd number of elements, you can move any element to any position. (But is it enough to guarantee it can be sorted?)

- For an even number of elements, it's not always possible to sort it, since you can't move elements between odd and even positions (ex: v = [-1, -2, 1, 7], impossible because -2 in is an odd position, but should be at an even position).

I've been thinking about this:

- Use an auxiliar array "aux" to put the numbers with their real neighbours, like:

v = [8, 0, 5, 9, -1, 5, 6] -> aux = [8, 5, -1, 6, 0, 9, 5]

Now in aux I can perform simple swaps with adjacents numbers.

- The final configuration in terms of their position "i" in aux is:

v = [8, 0, 5, 9, -1, 5, 6] -> aux = [8, 5, -1, 6, 0, 9, 5] -> i = [0, 2, 4, 6, 1, 3, 5]

- If n is even, there would be 2 aux, because to sort v, you can't move numbers between odd and even positions, so there's 2 sub problems. Ex:

v = [8, 0, 5, 9, -1, 5]

aux-even = [8, 5, -1] -> i-even = [0, 2, 4]

aux-odd = [0, 9, 5] -> i-even = [1, 3, 5] (thinking in terms of v)

I'm not sure where to go from here or if it's even a good path to run.

Any ideas or help are welcome.

Answer Source

For briefness, let me illustrate the idea by concrete cases, which are easy to generalize.

Even case

Let's say we have 8 elements. Then we sort two sub-array (with odd and even indices) separately, using the bubble sort with step 2, and have

``````a1    a2    a3    a4
b1    b2    b3    b4
``````

If the resulting array `a1 b1 a2 b2 a3 b3 a4 b4` happened to be sorted, we are done. Otherwise there is no solution.

Odd case

Let's say you have 7 elements. Sort them with your favorite method. Let's say after sorting they are

``````a5 a4 a1 a7 a3 a2 a6
``````

Assign key to every element like this:

``````a5 a4 a1 a7 a3 a2 a6
1  5  2  6  3  7  4
``````

Then come back to the original order:

``````a1 a2 a3 a4 a5 a6 a7
2  7  3  5  1  4  6
``````

Then sort the pairs by the new keys (`1` - `7`), using the bubble sort and with jumping over one element every time. As soon as you have the keys sorted, your `a1` ... `a7` values take their destination positions.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download