N. Kita - 3 months ago 15

C Question

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

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.