Java Custom Sort Order Round Robin-ish sorting

2520 views java
1

I am Java developer, but I'm blanking on a good algorithm for a specific type of sort I need to do.

Basically, I am going to get some data returned from a query (up to a few thousand rows). I only care about sorting based on a single column. Ironically, that column will likely already be sorted, but not in the way I need it to be.

It's simply this:

I am getting a list of user IDs, and I need to sort them in such a way that it runs through the whole list and starts over. An simple example is easier than the explanation:

Let's say the data is like this:

A A A A B B C D D

A valid sort order for my purpose would be this:

A B C D A B D A A

Basically, I need each user to "get a turn" before getting back to them. There will likely be an uneven number of users, so any extra can just stack at the end.

Again, I'm do this in Java, but am not locked into an specific data structure at this point, etc.

[Additional info: If it helps, specifically what I'm doing is generating data for a load test and want to minimize the same user login into the app multiple times, so I want my test to loop through all available application users before going back to the start of the list. The data is real data, though, and I cannot guarantee each user will have the same number of activities.]

Thanks! Tom

answered question

What about counting the occurrences of each ID (A:4, B:2, C:1, D:2) and then writing the new order by cyclic looping through unique occurrences? step 1: A B C D (A:3, B:1, C:0, D:1), step 2: A B C D A B D (A: 2, B: 0, C: 0 , D 0), step 3: A B C D A B D A A. Even seems like linear complexity, but is not in-place

Is the solution required to sort in place?

1 Answer

2

What kind of query? Are SQL window functions available? Sorry, couldn't comment... too little reputation.

posted this

Have an answer?

JD

Please login first before posting an answer.

Ads

Categories