here is my version (unoptimized at all) that works right (at least the way i expect)
fn findClosest list v =
(
local n = 0, d = 1e9
for k=1 to list.count where (i = abs(list[k]-v)) < d do
(
n = k
d = i
)
n
)
fn orderBeBetween list =
(
sort list
order = #()
append order list[1]
append order list[list.count]
final = copy order #nomap
deleteitem list 1
deleteitem list list.count
while list.count > 0 do --and not keyboard.escpressed do
(
k = 1
while k < order.count and list.count > 0 do
(
v = 0.5*(order[k]+order[k+1])
n = findClosest list v
insertitem list[n] order (k+1)
append final list[n]
deleteitem list n
k += 2
)
)
final
)
(
seed 0
-- format "----- 0
%
" (a = (for i=1 to 20 collect (random 1 40)))
format "----- 0
%
" (a = (for i=1 to 40 by (random 1 4) collect i))
-- format "----- 0
%
" (a = (for i=1 to 9 collect i))
format "----- 1
%
" (sortByMiddle (copy a #nomap))
format "----- 2
%
" (orderBeBetween (copy a #nomap))
)
I go to bed and come back with a slew of methods posted. Nice work guys. I’m going to check out these functions and see how they work. Thank you guys.
i can do it using 2 arrays instead of 3 (by shuffling the original list) but who knows … maybe the original list has to stay untouched.
Sorry, my previous function was indeed incorrect.
This one seems to work fine:
fn sortMiddle2 arr =
(
local sorted = #(arr[1])
local pairs = #(#(1, arr.count))
while pairs.count > 0 do
(
local p = pairs[1]
appendIfUnique sorted arr[p[2]]
local mid = (p[1] + p[2]) / 2
if (mid != p[1] and mid != p[2]) do
(
join pairs #(#(p[1], mid), #(mid, p[2]))
)
deleteItem pairs 1
)
sorted
)
It seems that your first function was also good. I just made a minor modification and the results looks good, though there are some differences due to rounding.
fn sortByMiddle arr =
(
local sorted = #()
local stepSize = amax 1 (arr.count - 1)
while (stepSize > 0.5) do
(
for index = 1 to arr.count by stepSize do
(
appendIfUnique sorted arr[index]
)
stepSize /= 2.0
)
sorted
)
Seems you’re right.
The following variation uses a bitarray for index tracking, ignoring the values altogether, and allows duplicates in the source array:
fn sortByMiddle arr =
(
local done = #{}
local sorted = #()
local stepSize = amax 1 (arr.count - 1)
while (stepSize > 0.5) do
(
for index = 1 to arr.count by stepSize where not done[index] do
(
append sorted arr[index]
done[index] = true
)
stepSize /= 2.0
)
sorted
)
Rotem and Denis have some very solid methods. Both create the function I was after. It was clever of you guys to test the sorting based on an array of numbers which skip frames because sometimes i render frame which aren’t always 1,2,3,4,5.
This will be an awesome sorting method to have.
seems to bug out
should be this
appendIfUnique sorted arr[p[2]]
It was a typo, fixed.
it still doesn’t look correct. you have to decide > sort or not sort…
try this array:
seed 0
a = (for i=1 to 20 collect (random 1 40))
i think that the task makes sense just to sorted (or reverse sorted) lists. and technically the list might not be unique. it still makes sense.
unsorted list is OK. but there is a specific rule how to pick two first items. first and last don’t work here. probably it has to be = min and max
As I understand it, the input is by definition a sorted unique list – a range of frames…
I can just call sort() on the list before this function if necessary.
so… can we define the task more exact?
#input: a sorted unique list
#output: “middle sorted” list that uses every, and only one time item from the origin list.
Impressive work guys. Rotem yours is quite condense. Mine would have been a long version haha.
The issue is I called this a sorting function. It’s actually a reorder function. Who says the caller would want the output sorted? It’s about taking one set and transforming it by binary step split, regardless of its values.
but if the list includes negative values?
Good point! Although Ive never needed to render a negative frame it doesnt mean someone else wont need to do so. I just focused on the given example.
Is performance something needed for this function?
i haven’t rendered anything neither positive or negative for about 6 years. but i know for sure that negative frames still exist.