# Resort set by a farthes step walkthrough

This topic is 1560 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello,

I want to resort a set so that it becomes equal to a walkthrough of the set where every step is position wise as far away as possible from the element already visited. Say for example, I have a sorted set of 5 Elements from A to E:

( A, B, C, D, E )

The first element I want to visit is A. Then I want to visit the element as far away as possible from the first element, that means E. From A and E, the farthest Element is C which I want to visit next. B and D are equally far away from A, C and E so they are both last. So the resorted set would be:

(A, E, C, B, D) or (A, E, C, D, B)

The largest possible set size is probably around 100.

How can this be done?

Regards!

##### Share on other sites

It doesn't sound too complicated, you already have your algorithm there, just need to write it down and add some checks.

There's one step of initialization, the first 2 values you pick are always the same (first and last of the original list) and, assuming you have more elements, you try to find an element in the middels of the other too.

You can have 2 results there, the simples would be to find an element (you have an odd number of elements), so you pick that, and now you have 2 subgroups with the same size, one at the left and one at the right. You now need the element in the middle of each of this groups, so you repeat this steps again and generate more smaller subgroups.

The other case would be that you have an even number off elements, so you can't pick the middle one. In this case you just pick one (say, the left) and you got 2 new subgroups. One group has 1 extra element this time.

Now, the algorithm store a "section" (start and finish index) and keep the list ordered by size and start. After you pick one element, update the list of sections removing the one you checked and add 2 more (add checks to know when you picked the last element). Keep doing this until the list of sections is empty, and always use the first element in the list (the biggest group).

EDIT: An untested idea in JavaScript

function findMiddle(elements,section) {
return Math.floor(section.end - section.start / 2) + section.start;
}

function splitSection(sectionsList,section,cutIndex) {
if (cutIndex - section.start > 1)
sections.push({start: section.start, end: cutIndex})
if (section.end - cutIndex > 1)
sections.push({start: cutIndex, end: section.end);

// sort sections by size (descending) and start index (ascending)
}

elements = [A,B,C...]; //list of elements to "sort"
sortedElements = [];
sections = [];

sortedElements.push(elements[0]);
sortedElements.push(elements[elements.length-1]);

sections.push({start: 0, end: elements.length-1});

while (sections.length > 0) {
index = findMiddle(elements,sections[0]);
sortedElements.push(elements[index]);
splitSection(sections,sections[0],index);
sections.shift(); //removes the first element of the array
}

Edited by DiegoSLTS

##### Share on other sites

If you can do a binary search, you can write the implementation for this pretty easily :-)

##### Share on other sites

I think it would be pretty much equivalent of a conversion from an in-order walk of a corresponding binary search tree converted to a breadth first search but I wonder if there is a fast existing implementation for that.

##### Share on other sites

You don't need to do anything to reorder the container; as long as it is random access, you can mimic the traversal pattern of a binary search and end up with a suitable visitation order based on your described criteria.

##### Share on other sites

Is there a simple mathematical formula that can convert the indexes of a inorder search to a breadth first search?

##### Share on other sites

Why do you need to do a BFS? Or an in-order search for that matter?

Like I've told you: your algorithm essentially describes a variant of a binary search, where each node you visit gets appended to the "result" list as you visit it. Just implement the visitation using the exact logic you described in the first post, and you're done. There's no breadth-first search necessary, no shuffling containers, no reordering anything.

You're making this a hell of a lot more complex than it needs to be :-)

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 13
• 9
• 9
• 15
• 14
• ### Forum Statistics

• Total Topics
634068
• Total Posts
3015327
×