Jump to content
  • Advertisement
Sign in to follow this  
jwezorek

sorting multicolumn data

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Say you have tabular data that can be sorted ascending or descending by any column. How can you represent the current sort state such that the sorts can be replayed to get the same order?

 

In other words, if you have a "name" field and a "value" field and a "color" field none of which is guaranteed to be unique, sorting by name and then by color gives different results than sorting by color and then by name. So you would need to maintain the sort history in queue of sort operations, but at what point can you stop maintaining this history -- shouldn't it loop around to the same order at some point?

Edited by jwezorek

Share this post


Link to post
Share on other sites
Advertisement

Assuming your sort is stable (without which this will blow up in interesting ways anyhow), you can drop off history entries as soon as each column appears exactly once.

 

(Or more than once, I should say.)

Edited by ApochPiQ

Share this post


Link to post
Share on other sites

Wait a second ...(I'm sorry this seems like it should be simple but I'm getting confused)

Say I have 3 records:

 

1 B 10

2 A 20

1 A 10

 

Sort by column #1 then by #2 then by #3 yields

1 B 10      1 A 10      1 A 10

1 A 10  ->  2 A 20  ->  1 B 10 

2 A 20      1 B 10      2 A 20

 

Now I've sorted by all columns but if I sort by column 1 again I get the following: (which doesn't change the order but whatever)

1 A 10

1 B 10

2 A 20

 

which is different than what I got when I sorted the original data by column 1, so I would have to maintain the history of the four sorts to get this state back, but prior to the last sort (that didn't change the order) each column appeared as a sort exactly once.

Edited by jwezorek

Share this post


Link to post
Share on other sites
Right, you just need to go a step further. Say we sort once more by column 2:
 
1 A 10
2 A 20
1 B 10
The history at this point is 1, 2, 3, 1, 2. You can drop the initial 1, leaving the history of 2, 3, 1, 2:
 
Start      By 2      By 3      By 1      By 2
1 B 10    2 A 20    1 A 10    1 A 10    1 A 10
2 A 20 -> 1 A 10 -> 1 B 10 -> 1 B 10 -> 2 A 20
1 A 10    1 B 10    2 A 20    2 A 20    1 B 10
Which matches our final state.


At least, I think that's right :-)


If that doesn't do it, you just need to search for the longest prefix of the list that appears somewhere else in the list, and truncate based on that. Note that I repeated 1,2,3,1,2 in the example above and see if that helps work out a more generalized strategy.


Or maybe it's even simpler: N columns = truncate after N+1 sorts, ignoring cases where you sort on the same column more than once in a row. Edited by ApochPiQ

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!