# Sort rectangles in a grid based on a comparison of the center point of each

If I have a grid of rectangles and I move one of the rectangles, say above and to the left of another rectangle, how would I resort the rectangles?

Note the rectangles are in an array, so each rectangle has an index and a matching tag. All I really need to do is set the proper index based on the rectangles new center point position within the rectangle, as compared with the center point position of the other rectangles in the grid. Here is what I am doing now in pseudo code (works somewhat, but not accurate):

``````-(void)sortViews:myView {
int newIndex;
// myView is the view that was moved.
[viewsArray removeObject:myView];
[viewsArray enumerate:obj*view]{
if (myView.center.x > view.center.x) {
if (myView.center.y > view.center.y) {
newIndex = view.tag -1;
*stop = YES;
} else {
newIndex = view.tag +1;
*stop = YES;
}
} else if (myView.center.x < view.center.x) {
if (myView.center.y > view.center.y) {
newIndex = view.tag -1;
*stop = YES;
} else {
newIndex = view.tag +1;
*stop = YES;
}
}
}];
if (newIndex < 0) {
newIndex = 0;
} else if (newIndex > 5) {
newIndex = 5;
}
[viewsArray insertObject:myView atIndex:newIndex];
[self arrangeGrid];
}
``````
-
To sort objects we need a compare function that tells us when one object is less than or greater than another. In C-style languages this is typically done with a function that returns one of <0 (or -1), 0, >0 (or +1). So how do you define your compare function? – andy256 Sep 17 '13 at 5:48
It can get rather complicated the way you're thinking about it now. @andy256 is right here. The best approach is to modify the position of the rectangle, and then apply a sort to ensure it remains consistent (hint: bubble and insertion sorts are best when you have almost sorted data). – Neil Sep 17 '13 at 13:21

## 1 Answer

Not really an answer, but it won't fit in a comment:

First, what you're doing looks fine to me. I'm not familiar with the language, but arrays are usually very fast.

If you have a large number of rectangles, a Dictionary or Map, using x/y keys would be more elegant. Then you can find your entry more quickly, remove it without moving 1000's of elements around in the array, and insert without moving elements around. (I'd like to they'd be much faster with large lists, but I've been embarrassed by absurdly fast arrays too many times in benchmarks.) (Be sure to remove the rectangle first, then change the key, then re-add it.)

If you stick with an array, you could speed things up with binary searches to find the rectangle and to figure out where to put it. You could also speed things up by moving only the elements between the removal point and the insertion point.

Your language seems to do a lot of work for you: you may want to check out what it is doing and what else it can do for you. (Your "array" may already be a dictionary/map--or something better. You may be able to get it to move an element in one go, rather than removing and adding, thus saving moving a lot of entries.)

-