Algorithm for reordering multiple Items with ranking
Hi i'm really stuck at a problem when I reorder multiple items at the same time, Let me state the problem more clearly using this example :
If originally i have this table :
Supposedly I want to put A and B, to rank 4 and 5, I should expect a result that looks like this :
However, I'm absolutely clueless how i'm going to do this, systematically. Initially I tried reordering them by considering the change one at a time.
My algorithm is:
1) if an item's rank is to be moved lower:
Adjust all other items above the desired rank, increase their rank by 1 until I reach the original item's rank. So suppose I want to move D from rank 4 to 2.
I will move B and C upward until the original rank of D is filled. Then I update the rank of D.
2) If an item's rank is to be moved higher, just do the opposite.
If I use this algorithm for putting A and B to rank 4 and 5 respectively, step by step here's what happens :
This is wrong. Because of the wrong algorithm of course. I move A initially, and A gets to rank 4, but since I only adjust one by one, the A also gets moved when I try to re-rank B.
What's the best algorithm for reordering multiple items at the same time? and maintaining the sequence of rank of the affected items? I'm coding in php btw, so that would be really great if you could provide a sample code, but an algorithm is enough.
I've added 3 examples below to demonstrate the desired movement :
1) #1 case : move C to 2, and B to 4 :
- C and B are of course, moved to their respective ranks. But we do know that A,D and E, has an initial ordering of 1, 4, and 5. But since 4 will be taken, we will have to adjust to lower the rank of D instead of increasing it since rank 4 and 5 are both taken. A remains the same and unchanged as well as E.
- We do know A comes first before D, and D before E, filling the gaps of 1, 3 and 5.
2) #2 case : move E to 1 and A to 4.
- Logically if we move A first, then B should be on #1. But since E is a consideration, instead of going up. adjust rank down.
- Still, we do know that B, C and D also has an order. That B comes first, then C then D, in the same way filling the gaps of the "untaken" spots.
3) #last example, here is to simply move A to 5. - Adjusting all others to go up.
Personally, I'd create a stack as a temporary holder. First push in the lowest ranked value (B), then the next (A) then push in the rest of the items starting from bottom to top. After this push off the stack back into your list starting at the new highest rank first (C, D, E, A, B). If your list of items is enormous, however, this may take some considerable processing power so might not be the best solution.