N. Kita N. Kita - 1 month ago 6
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

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.

Comments