Efficiently Sorting an Array of N Points by Distance from the Origin

Given an array arr[] of N points. The task is to sort these points according to it’s distance from the origin.

Examples:

Input: arr[] = { {5,0}, {4,0}, {3,0}, {2,0}, {1,0} } 
Output: (1,0) (2,0) (3,0) (4,0) (5,0) 
distance bw (0,0) and (1,0) = 1 
distance bw (0,0) and (2,0) = 2 
distance bw (0,0) and (3,0) = 3 
distance bw (0,0) and (4,0) = 4 
distance bw (0,0) and (5,0) = 4 

Input: arr = { {5,5}, {6,6}, {1, 0}, {2,0}, {3,1}, {1,-2} } 
Output:(1,0) (2,0) (1,-2) (3,1) (5,5) (6,6)

Approach:
The idea is to store each element with its distance from the origin in a vector pair and then sort all the elements of the vector according to the distance stored. Finally, print the elements in order.

Below is the implementation of the above approach:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

// Function to sort the array according to
// their distance from origin
void sortArr(vector<pair<int, int>> arr, int n)
{
    // Vector to store the distance
    // with respective elements
    vector<pair<double, pair<double, double>>> vp;

    // Inserting distance with elements
    // in the vector pair
    for (int i = 0; i < n; i++) {
        double dist = sqrt(arr[i].first*arr[i].first + arr[i].second*arr[i].second );
        vp.push_back(make_pair(dist, make_pair(arr[i].first,arr[i].second)));
    }

    // Sort the vector, this will sort the pair
    // according to the distance form origin
    sort(vp.begin(), vp.end());

    // Print the sorted vector content
    for (int i = 0; i < vp.size(); i++)
       {
        cout << "(" << vp[i].second.first << "," << vp[i].second.second << ") ";
       }
}

// Driver code
int main()
{
    vector<pair<int, int>> arr = { {5,5}, {6,6}, {1, 0}, {2,0}, {3,1}, {1,-2} };
    int n = 6;
    sortArr(arr, n);

    return 0;
}

Output:

(1,0) (2,0) (1,-2) (3,1) (5,5) (6,6)

Time Complexity: O(nlogn)
Space Complexity: O(n)

Similar Reads