Sorting is generally used to solve problems where distance between elements matters. A sorted list/array has the convenient property that the smaller the difference between the indices of any two elements, the smaller the difference between the values of the elements.*
When working with lists of coordinates or similar values with more than one dimension, is there an arrangement of the list that has similar properties (for Euclidean distance) to those of a sort in one dimension?
Edited (twice) to add more details:
To be clear, a sorted list
[X, Y, Z] has the property that the distance between
Z cannot be less than that between
Z and that between
X, otherwise the list wouldn't qualify as sorted.
For example, let's say I have the following unsorted list of
(name, X, Y) coordinates, with the names just in there for convenience:
[("A", 58, 45), ("B", 7, 4), ("C", 44, 88), ("D", 60, 100), ("E", 76, 44)]
A simple Python script tells me the Euclidean distances between every pair of elements:
import itertools import math coords = [("A", 58, 45), ("B", 7, 4), ("C", 44, 88), ("D", 60, 100), ("E", 76, 44) ] def dist(coord1, coord2) -> int: name1, x1, y1 = coord1 name2, x2, y2 = coord2 return round(math.sqrt((x1 - y1)**2 + (x2 - y2)**2), 2) for (i, j) in itertools.combinations(coords, 2): print("Distance between", i, "and", j, "is", dist(i, j))
With the results:
Distance between A and B is 13.34 // Closest two elements Distance between A and C is 45.88 Distance between A and D is 42.06 Distance between A and E is 34.54 // Third closest elements Distance between B and C is 44.1 Distance between B and D is 40.11 Distance between B and E is 32.14 // Second closest elements Distance between C and D is 59.46 Distance between C and E is 54.41 Distance between D and E is 51.22
I've been trying to work out on paper how to arrange these elements such that the rank-distance property of sorting is preserved. So far I've worked out that because
B are the two elements with the least Euclidean distance between them, they need to be adjacent post-sort. The pair of elements with the second smallest Euclidean distance is
E should be adjacent. The only possible arrangements of
E with both these adjacencies are
[A, B, E], and
[E, B, A]. Beyond trial and error however, I can't justify whether this property is always satisfiable.
* Technically, the smaller the difference between the indices of any two elements, the smaller the rank of the difference between the values of the elements. For example, in the list
[1, 5, 6, 8],
5 has an index closer to that of
1 than to that of
8, but 5 as a number is closer to 8 than it is to 1.
O(N)after doing the multidimensional sort) figuring out who should go for which chair in music chairs. Actually lots and lots of mapping problems. Figuring out which servers in a data center should talk to which others for splitting work across nodes. Basically this is just a more general notion of sorting. Off the top of my head, this would be especially useful in navigation, self-driving cars, simulated worlds, graphics and so on.