Post
Ask Question

Sorting Sorted Array as Per Absolute Value with Time Complexity O(n) in C#

Few days ago I came across this interesting question, which was asked to my friend in his interview. Though solutions to the problem stated above are many but achieving it with time complexity O(n) became interesting as well challenging.

So here is the solution:

    Input: 50 -25 -12 -3 0 3 5 45 50 60
    Output: 0 -3 3 5 -12 -25 45 -50 50 60

Solution:

  1. public int[] SortByAbsoluteValue() {  
  2.   
  3.     int[] sampleInput = {  
  4.         -50, -25, -12, -3, 0, 3, 5, 45, 50, 60  
  5.     };  
  6.   
  7.     int n = sampleInput.Length;  
  8.   
  9.     int[] output = new int[n];  
  10.   
  11.     string sOutput = string.Empty;  
  12.   
  13.     int start = 0;  
  14.   
  15.     int last = n - 1;  
  16.   
  17.     while (last >= start) {  
  18.   
  19.         n--;  
  20.   
  21.         if (Math.Abs(sampleInput[start]) > Math.Abs(sampleInput[last])) {  
  22.   
  23.             output[n] = sampleInput[start++];  
  24.   
  25.         } else {  
  26.   
  27.             output[n] = sampleInput[last--];  
  28.   
  29.         }  
  30.   
  31.         sOutput = output[n].ToString() + " " + sOutput;  
  32.   
  33.     }  
  34.   
  35.     Console.Write(sOutput);  
  36.   
  37.     return output;  
  38.   
  39. }  
Do mention in comments if we can achieve the same in more optimized manner.