That Randy Brown

Fractional Ranking

Suppose you have a list of items, each saved as an unordered collection, each as an individual entity, that now you need to sort and update the order of in a nondestructive way. Typically, this would be done in one of three ways:

  1. Save the index of the item in the list as its priority
  2. Save the list as a single entity
  3. Creating the list as a linked list

However, All of these have time and space complexity. In the first case, updating a single order will minimally require updating two items, and might require updating all of them (if, for instance, an item is added to the front of the list, shifting all indices). In the second case, there will be a lot of duplication of records in the best case of just two items swapped, or in the case of an item added to the front, because even though the rest of the items in the list are unchanged, their order will be re-preserved. The final list has all the computational complexity of adding an item to the middle of a linked list (at least three nodes will need to be modified for any change), though adding it to the beginning is significantly easier.

To meet the requirements of only modifying the changed item in the order, and to preserve the order, fractional ranking can be leveraged instead, and then the list sorted by the weight. In fractional ranking, the order is determined by sorting items according to an assigned weight, where the weight assigned is determined by taking the two items before and after it in the list, and finding the midpoints of their weights. This is infinitely flexible thanks to floating point values. I usually start with a large power of 2, like 1024, which allows 10 different injected items before collapsing to an odd and then a decimal, which might mess with other weighted math.

As an example, when I have only one item, it has a sort value of 0, arbitrarily. When I add a second value, I add it either to the left, or the right. If it is added to the right, it is given a sort value of 1024, if to the left, a value of -1024. The next item has three spots it can be assigned, but the valuation is easier: 1024 more (or less) than the last value on the outsides, halfway between the two if between them. In this way, I can sort and change order by only modifying the value of the item in question--its weight is always (l + h) / 2 -- a strict mean. If it is on the high or low end, it is plus or minus the base interval (1024 in this case).