# Sort an array according to absolute difference with given value

Given an array of n distinct elements and a number x, arrange array elements according to the absolute difference with x, i. e., element having minimum difference comes first and so on.
Note : If two or more elements are at equal distance arrange them in same sequence as in the given array.

Examples :

```Input : arr[] : x = 7, arr[] = {10, 5, 3, 9, 2}
Output : arr[] = {5, 9, 10, 3, 2}
Explanation:
7 - 10 = 3(abs)
7 - 5 = 2
7 - 3 = 4
7 - 9 = 2(abs)
7 - 2 = 5
So according to the difference with X,
elements are arranged as 5, 9, 10, 3, 2.

Input : x = 6, arr[] = {1, 2, 3, 4, 5}
Output :  arr[] = {5, 4, 3, 2, 1}

Input : x = 5, arr[] = {2, 6, 8, 3}
Output :  arr[] = {6, 3, 2, 8}
```

The idea is to use a self balancing binary search tree. We traverse input array and for every element, we find its difference with x and store the difference as key and element as value in self balancing binary search tree. Finally we traverse the tree and print its inorder traversal which is required output.

C++ Implementation :
In C++, self-balancing-bianry-search-tree is implemented by set, map and multimap. We can’t use set here as we have key value pairs (not only keys). We also can’t directly use map also as a single key can belong to multiple values and map allows a single value for a key. So we use multimap which stores key value pairs and can have multiple values for a key.

1. Store the values in the multimap with the difference with X as key.
2. In multiimap, the values will be already in sorted order according to key i.e. difference with X because it implements self-balancing-bianry-search-tree internally.
3. Update all the values of array with the values of map so that array has the required output.
 `// C++ program to sort an array according absolute ` `// difference with x. ` `#include ` `using` `namespace` `std; ` ` `  `// Function to sort an array according absolute ` `// difference with x. ` `void` `rearrange(``int` `arr[], ``int` `n, ``int` `x) ` `{ ` `    ``multimap<``int``, ``int``> m; ` `    ``multimap<``int` `,``int` `>:: iterator it; ` `    ``// Store values in a map with the difference ` `    ``// with X as key ` `    ``for` `(``int` `i = 0 ; i < n; i++) ` `        ``m.insert(make_pair(``abs``(x-arr[i]),arr[i])); ` ` `  `    ``// Update the values of array ` `    ``int` `i = 0; ` `    ``for` `(it = m.begin(); it != m.end(); it++) ` `        ``arr[i++] = (*it).second ; ` `} ` ` `  `// Function to print the array ` `void` `printArray(``int` `arr[] , ``int` `n) ` `{ ` `    ``for` `(``int` `i = 0 ; i < n; i++) ` `        ``cout << arr[i] << ``" "``; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `arr[] = {10, 5, 3, 9 ,2}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``int` `x = 7; ` `    ``rearrange(arr, n, x); ` `    ``printArray(arr, n); ` `    ``return` `0; ` `} `

Output:

```5 9 10 3 2
```

Time Complexity : O(n Log n)
Auxiliary Space : O(n)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

code

load comments