1

I have an array of n = 32 items with positive and negative values. First n/2 elements are positive and sorted by value and second n/2 elements are negative and sorted by value as well. I would like to sort the whole array by value, starting from the smallest negative value to biggest positive value which means if there are 32 elements the first 16 (n/2) sorted elements should contain the values of second 16 elements of the original array and the second 16 elements of the sorted array should contain the first 16 values of the original array.

Hypothetical example:

double[] original = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, -16, -15, ..., -1};

double[] sorted = {-16, -15, ...., -1, 1, 2, ..., 16};

Does anyone know what is the best way to shift the elements to generate the sorted array from original?

This array is by the way tied to another array which doesn't have the elements sorted by size the same way and has to be shifted the same way as original so the array shouldn't be sorted by size, it has to be shifted.

Improve this question
3
  • Why do they have to be shifted and not sorted? Commented Apr 19, 2009 at 18:44
  • because i have to shift another array which is not sorted by size the same way i do it for this one. the hyppothetical example rapresents an x-axis and it is sorted by size but another array contains values which shouldn't be sorted by size (y-axis). Commented Apr 19, 2009 at 18:54
  • Do you want to sort one array based on the values contained in another array? In other words: do you want to sort one array and then apply the same sequence of steps to another array? Commented Apr 19, 2009 at 19:06

7 Answers 7

Reset to default
9

So you want a second array, with the contents of the original but at locations shifted? Either do it explicitly:

double[] result = new double[32];
for (int i=0; i < 32; i++)
{
    result[(i+16)%32] = original[i];
}

or using Array.Copy twice:

double[] result = new double[32];
Array.Copy(original, 0, result, 16, 16);
Array.Copy(original, 16, result, 0, 16);
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

Given the rigid nature of the problem, Array.Copy:

        int half = original.Length / 2;
        Array.Copy(original, 0, sorted, half, half);
        Array.Copy(original, half, sorted, 0, half);
Improve this answer

Comments

2

How about in Linq:

int half = original.Length/2;
var sorted = original.Skip(half).Concat(original.Take(half)).ToArray();
Improve this answer

1 Comment

I think you mean Concat rather than Union - Union will remove any repeated elements.
0

Have you tried: 

Array.Sort(original);
Improve this answer

4 Comments

it has to be shifted not sorted!
In the example you gave, the desired result will be obtained with Array.Sort.
Bearing in mind that both halves are already sorted (according to your description) shifting element 0 with 16, 1 and 17, 2 and 19, etc... will have the same result as sorting the array by size.
@Darin Dimitrov - He cannot sort as he needs to do the same shift on another array. It's explained in a questions's comment.
0

Just do a swap on element 0 and element 16, 1 and 17, 2 and 18.. etc.

Improve this answer

Comments

0

Do you want to sort one array based on the values contained in another array of the same size? If so, use the following:

Array.Sort(keys, values);

Here's the documentation Array.Sort(Array keys, Array items)

Improve this answer

Comments

0

Jon Skeet's and Marc Gravell♦'s answers provide the correct solution, but if you don't want to allocate an extra array you can:

a) solve you specific problem (shifting the 2nd half to be before the 1st half) in place:

private void Rotate1(double[] toRotate ) {
        int startOf2nd = toRotate.Length / 2;
        for (int i=0; i < toRotate.Length/2; i++) {
            double temp = toRotate [i];
            toRotate [i] = toRotate [i + startOf2nd];
            toRotate [i + startOf2nd] = temp;
        }
    }

Note that this code cannot deal with an array with odd number of items.

b) you can apply the vector shifting algorithm I know from Jon Bentley's 'Programming Pearls':

 private void Rotate2(double[] toRotate, int index ) {
        Array.Reverse(toRotate, 0, index);
        Array.Reverse(toRotate, index, toRotate.Length-index);
        Array.Reverse(toRotate, 0, toRotate.Length);
    }

In your example the index would be 16. This code handles odd numbers of items and index not being in the middle. Using an example similar to the one used in the book for toRotate={0,1,2,3,4,5,6,7} and index = 3 Rotate2 would produce {3,4,5,6,7,0,1,2}.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.