Tutorialspoint.dev

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<bits/stdc++.h>
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[0]);
    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

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter