Sorting an integer array in strictly O (n) time

Question

I was recently asked this question in an interview.

Given a sorted integer array containing negative and positive numbers, how to resort to an array based on the absolute values ​​of the elements?

This had to be done strictly in O (n) time.

input

{- 9, -7, -3,1,6,8,14}

Exit

{1, -3.6, -7.8, -9.14}

What are the possible solutions besides O (n) time?

Answer 1

Basically, we will have 2 heads, one looks at the end of the array, one at the beginning.

vv {-9, -7, -3, 1, 6, 8, 14} 

We compare the absolute value of the two records that our heads point to and insert them into our new sorted array. So, it will be 14.

 New array: {14} 

Then we move the head of the element that we selected closer to the center. So, we move our head, pointing to 14-8.

  vv {-9, -7, -3, 1, 6, 8, 14} 

Then we repeat the process, inserting the larger of 2 absolute values ​​at the beginning of our new, sorted array. Here it will be -9, as | -9 | > | 8 |

 New array: {-9, 14} 

And after we move our head again:

  vv {-9, -7, -3, 1, 6, 8, 14} 

Repeat until both heads meet in the center.

Answer 2

Take your example:

 {-9,-7,-3,1,6,8,14} 

You can rewrite this in two parts:

 {-9,-7,-3} and {1,6,8,14} 

Two obvious observations:

• The left part is sorted in descending order.
• The right part is sorted ascending

Now you basically just concatenate these two sorted subarrays, which are possibly in linear time. Look at the algorithm here. How to combine two sorted arrays into a sorted array? .

Since you do not separate these arrays, you find a point in the array that flips negative to positive. From this split point, you can go index by index to the boundaries of the array and restore the sorted array again.

Answer 3

As mentioned in the comments, you mostly look at merge sort. The source data is already sorted, so all you have to do is get the values ​​in order from each negative and positive sets of numbers, combining them according to their absolute values.

The code looks something like this:

 int[] input = { -9, -7, -3, 1, 6, 8, 14 }; int[] output = new int[input.Length]; int negativeIndex, positiveIndex = 0, outputIndex = 0; while (input[positiveIndex] < 0) { positiveIndex++; } negativeIndex = positiveIndex - 1; while (outputIndex < output.Length) { if (negativeIndex < 0) { output[outputIndex++] = input[positiveIndex++]; } else if (positiveIndex >= input.Length) { output[outputIndex++] = input[negativeIndex--]; } else { output[outputIndex++] = -input[negativeIndex] < input[positiveIndex] ? input[negativeIndex--] : input[positiveIndex++]; } } 

Above, this IMHO is somewhat easier to understand, but as another answer indicates, you can do this without even scanning a 0-point data, by sorting from the other end. The code for this will look something like this:

 int[] output = new int[input.Length]; int negativeIndex = 0, positiveIndex = input.Length -1, outputIndex = input.Length - 1; while (outputIndex >= 0) { if (input[negativeIndex] >= 0) { output[outputIndex--] = input[positiveIndex--]; } else if (input[positiveIndex] < 0) { output[outputIndex--] = input[negativeIndex++]; } else { output[outputIndex--] = -input[negativeIndex] < input[positiveIndex] ? input[positiveIndex--] : input[negativeIndex++]; } }