Home » Data Structure » Array Data Structure

Sort an array according to the absolute difference of the given value

C++ implementation to sort an array according to the absolute difference of the given value.
Submitted by Vikneshwar GK, on January 20, 2022

Consider an array of size n and an integer x. The task at hand is to sort the array according to the absolute difference between array elements and integer x. If two or more elements have the same absolute difference, place them in the same order as in the initial array.

Example:

Input:
test1[] = {8, 4, 2, 5, 6, 1, 10, 9, 7, 12}
x = 5

Output:
test1[] = {5, 4, 6, 7, 8, 2, 1, 9, 10, 12}

Explanation:
abs(8 - 5) = 3
abs(4 - 5) = 1
abs(2 - 5) = 3
abs(5 - 5) = 0
abs(6 - 5) = 1
abs(1 - 5) = 4
abs(10 - 5) = 5
abs(9 - 5) = 4
abs(7 - 5) = 2
abs(12 - 5) = 7
Sort the elements according to this difference.
We will get the desired output.


Input:
test1[] = {4, 7, 1, 6, 8}
x = 3

Output:
test1[] = {4, 1, 6, 7, 8}

Explanation:
abs(4 - 3) = 1
abs(7 - 3) = 4
abs(1 - 3) = 2
abs(6 - 3) = 3
abs(8 - 3) = 5
Sort the elements according to this difference 
and we will get the desired output.

Solution: Using Self-Balancing Binary Search Tree

A self-balancing binary search tree is a height-balanced BST that automatically keeps height as small as possible when insertion or deletion operations are performed on the tree. We can use this concept to sort the array element according to the absolute difference with an element x. It involves the following steps:

• Find the absolute difference of every array element with the given integer.
• Insert the absolute difference as the key and the corresponding array element as the value in the self-balancing BST.
• Perform inorder tree traversal and the elements.

C++ Implementation:

Note: We will be using multimap as we need to store in key-value format and possibly duplicate keys.

#include <bits/stdc++.h>
using namespace std;

// Function to sort the array
// based on absolute difference with x
void absDiffSort(int array[], int length, int x)
{
    // multimap declaration
    multimap<int, int> bst;
    multimap<int, int>::iterator itr;

    // find absolute difference
    // and insert into bst
    for (int i = 0; i < length; i++)
        bst.insert(make_pair(abs(x - array[i]), array[i]));

    // order traversal
    // modify original array
    int i = 0;
    for (itr = bst.begin(); itr != bst.end(); itr++)
        array[i++] = (*itr).second;
}

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
}

// main function
int main()
{
    int array[100], N, x;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    cout << "Enter an Integer value: ";
    cin >> x;

    absDiffSort(array, N, x);
    printArray(array, N);
    
    return 0;
}

Output:

Enter Number of elements: 10
Enter element 1:8
Enter element 2:4
Enter element 3:2
Enter element 4:5
Enter element 5:6
Enter element 6:1
Enter element 7:10
Enter element 8:9
Enter element 9:7
Enter element 10:12
Enter an Integer value: 5
5 4 6 7 8 2 1 9 10 12

Time Complexity: O(nlog(n))