# Sorting position array by shortest distance

hi,
i would like to ask how to make sorting faster.
lets say that the posArr is collection of random positions and I need to sort them by distances so that>
posArr[n + 1] asi clossest point to posArr[n]
and
posArr[n + 2] asi clossest point to posArr[n + 1]
and so on....

```-- random positions 1000
posArr = for i = 1 to 1000 collect random [-100,-100,0] [100,100,200]

fn sortByMin v1 v2 mN:[-100,-100,0] = ---- sorting by minimum
(
local d1 = distance v1 mN
local d2 = distance v2 mN
case of
(
(d1 < d2) : -1
(d1 > d2) : 1
default: 0
)
)

fn compareDistance v1 v2 pA:#() pass:1 = --- sorting by distance to pos
(
if pass > 1 then
(
local p0 = pA[pass-1]
)
else local p0 = pA[pass]
local d1 = (distance v1 p0)
local d2 = (distance v2 p0)
case of
(
(d1 < d2) : -1
(d1 > d2) : 1
default: 0
)
)

fn compareNeighbArr pA = ( --- for loop for search at next array index
qsort pA sortByMin
for i in 1 to pA.count-1 do
(
qsort pA compareDistance pA:Pa pass:i start:i
)
)

clearlistener()

st = timestamp()
compareNeighbArr posArr
t= timestamp() - st

format "sorted in % s " (t / 1000.0)
format "%" (distance posArr[1] posArr[2]) -- test 1 2
format "%" (distance posArr[1] posArr[3]) -- test 1 3```

----
right now it takes 11 seconds for 1000 member array
but 45 seconds for 2000 array

And I need to make it much much faster

## Comment viewing options

### `

Hi,

If you still need it, I tried some sorting methods and I got to 2s for 1000 array and 10s for 2000 array,

but trying to sort :
posArr[n + 1] asi clossest point to posArr[n]
and
posArr[n + 2] asi clossest point to posArr[n + 1]
and so on....

In some point the closest pos to previous is totaly on other side of space/line...

When I quickly tried your method it sorted only in growing order starting closest to 0... (without finding smallest distance between 2 points)

For eg this random Z axis 0 to 200:
`posArr = for i = 1 to 1000 collect random [100,100,0] [100,100,200]`
It sorted only z positions like this: 0.1,0.5,1,1.25,5,10,15,16,22,28,39...

After some tests I got something like this:

```(
clearlistener()
t = timestamp()

posArr = for i = 1 to 2000 collect random [100,100,0] [100,100,200]
distArr = #()
sortedPosArr = #()

------------------------------------------------------------------- find smallest distance --   collect array with distance and 2 points  ---------------------------------------
posArr2 = for o in posArr collect o
for i = 1 to posArr2.count where posArr2[i] != undefined do (
local shortestdist = 99999999
local sub = #()
for j = 1 to posArr2.count where i != j and posArr2[j] != undefined and (d = distance posArr[i] posArr[j]) < shortestdist do (
shortestdist = d
sub = (if i < j then #(shortestdist, i, j) else #(shortestdist, j, i))
)
if sub[1] != undefined then appendifUnique distArr sub
posArr2[i] = undefined
)
posArr2 = for o in posArr collect o
------------------------------------------------------------------- finds next closest point --------------------------------------------------------------------------------------------
fn findShortestDa a shortestdist:99999999 c: = (
for j = 1 to posArr2.count where posArr2[j] !=undefined and (d = distance a posArr2[j]) < shortestdist do (shortestdist = d; c = j)
#(shortestdist, c)
)
------------------------------------------------------------------ sort by distance -------- array with distance and 2 points ----------------------------------------------------------
fn compareDist v1 v2 =
case of (
(v1[1] > v2[1]): 1
(v1[1] < v2[1]): -1
default: 0
)
qsort distArr compareDist
----------------------------------------------------------------- collect 2 points of smallest distance
a = posArr2[(distArr[1][2])]
b = posArr2[(distArr[1][3])]
----------------------------------------------------------------- remove them from pos array
posArr2[(distArr[1][2])] = undefined
posArr2[(distArr[1][3])] = undefined
----------------------------------------------------------------- find if a or b has closest point
c = (findShortestDa a)
d = (findShortestDa b)
----------------------------------------------------------------- append 3 points to array
if c[1] > d[1] then (
append sortedPosArr a
append sortedPosArr b
append sortedPosArr posArr2[d[2]]
posArr2[d[2]] = undefined
)
else (
append sortedPosArr b
append sortedPosArr a
append sortedPosArr posArr2[c[2]]
posArr2[c[2]] = undefined
)
------------------------------------------------------------------- collect and find next closest point   ------ delate used points from array

for i = sortedPosArr.count+1 to posArr.count do (
a = ((findShortestDa sortedPosArr[(sortedPosArr.count)])[2])
append sortedPosArr posArr2[a]
posArr2[a] = undefined
)

totalTime = ((timestamp() - t)/1000)

print sortedPosArr
print sortedPosArr.count
print totalTime
)```

Hope it helps a bit,
Best,

### `

ah, maybe this is better
it sorts 2000 array in 9s

But it still find smallest distance on beggining and then look for next points.

```(
clearlistener()
t = timestamp()

posArr = for i = 1 to 2000 collect random [100,100,0] [100,100,200]
distArr = #()
sortedPosArr = #()

------------------------------------------------------------------- find smallest distance --   collect array with distance and 2 points  ---------------------------------------
posArr2 = for o in posArr collect o
for i = 1 to posArr2.count where posArr2[i] != undefined do (
local shortestdist = 99999999
local sub = #()
for j = 1 to posArr2.count where i != j and posArr2[j] != undefined and (d = distance posArr[i] posArr[j]) < shortestdist do (
shortestdist = d
sub = (if i < j then #(shortestdist, i, j) else #(shortestdist, j, i))
)
if sub[1] != undefined then appendifUnique distArr sub
posArr2[i] = undefined
)
posArr2 = for o in posArr collect o
------------------------------------------------------------------- finds next closest point --------------------------------------------------------------------------------------------
fn findShortestDa a shortestdist:99999999 c: = (
for j = 1 to posArr2.count where (d = distance a posArr2[j]) < shortestdist do (shortestdist = d; c = j)
#(shortestdist, c)
)
------------------------------------------------------------------ sort by distance -------- array with distance and 2 points ----------------------------------------------------------
fn compareDist v1 v2 =
case of (
(v1[1] > v2[1]): 1
(v1[1] < v2[1]): -1
default: 0
)
qsort distArr compareDist
----------------------------------------------------------------- collect 2 points of smallest distance
a = posArr2[(distArr[1][2])]
b = posArr2[(distArr[1][3])]
----------------------------------------------------------------- remove them from pos array
deleteItem posArr2 distArr[1][2]
deleteItem posArr2 distArr[1][2]
----------------------------------------------------------------- find if a or b has closest point
c = (findShortestDa a)
d = (findShortestDa b)
----------------------------------------------------------------- append 3 points to array
if c[1] > d[1] then (
append sortedPosArr a
append sortedPosArr b
append sortedPosArr posArr2[d[2]]
deleteItem posArr2 d[2]
)
else (
append sortedPosArr b
append sortedPosArr a
append sortedPosArr posArr2[c[2]]
deleteItem posArr2 c[2]
)
------------------------------------------------------------------- collect and find next closest point   ------ delete used points from array

for i = sortedPosArr.count+1 to posArr.count do (
a = ((findShortestDa sortedPosArr[(sortedPosArr.count)])[2])
append sortedPosArr posArr2[a]
deleteItem posArr2 a
if posArr2.count == 0 do exit
)

totalTime = ((timestamp() - t)/1000)

print sortedPosArr
print sortedPosArr.count
print totalTime
)```

if you to declare 0 position [100,100,0]
then it can be 3s for 2000 array:

```(
clearlistener()
t = timestamp()

posArr = for i = 1 to 2000 collect random [100,100,0] [100,100,200]
distArr = #()
sortedPosArr = #()
pos0 = [-100,-100,0]

posArr2 = for o in posArr collect o
sortedPosArr = #(pos0)

fn findShortestDa a shortestdist:99999999 c: = (
for j = 1 to posArr2.count where (d = distance a posArr2[j]) < shortestdist do (shortestdist = d; c = j)
#(shortestdist, c)
)

for i = 1 to posArr.count do (
a = ((findShortestDa sortedPosArr[(sortedPosArr.count)])[2])
append sortedPosArr posArr2[a]
deleteItem posArr2 a
if posArr2.count == 0 do exit
)

deleteItem sortedPosArr 1

totalTime = ((timestamp() - t)/1000)

print sortedPosArr
print sortedPosArr.count
print totalTime
)```

Hope it helps,
Pixamoon

### ...

```fn compareFN v1 v2 =
(
local d = v1.dist - v2.dist
case of
(
(d < 0.): -1
(d > 0.):  1
default:   0
)
)

_min = [-100,-100,0]
_max = [100,100,200]
data = #()
num = (data.count = 10000)
data = for i = 1 to num collect dataPair pos:(number = random _min _max) dist:(distance number _min)

gc() ; t1 = timestamp() ; m1 = heapfree
qsort data compareFN
format "time:% memory:%\n" ((timestamp()- t1 as float)/1000) (m1-heapfree)```

barigazy

### `

I think he ask for faster sorting by distance between points in array, not to one _min point.
but maybe not
But I've just learned dataPair from your comment! good to know, Thanks