I have a database in array list and I need to sort them in ascending order based on the frequency of the items, not on lexicographic order.
E.g. Each row is an array with the items
1 2 9
1 2 3 4 5
1 6 7 8
will be arranged into
9 2 1
3 4 5 2 1
6 7 8 1
E.g. in row 1, item 1 is at the last because it has the highest frequency (3), follow by item 2 whose frequency is 2.
Given that I have a large database, is there any way to efficiency sort them? Thanks for your help!
If all your values are low integers less than N (for some value of N), then first make a table of frequencies and have your comparison function look up the frequency on the table.
If your values aren't integers filling the values up to N, use a hash table of freqencies and do the same.
If this sorting operation is common, I'd use a different data structure for your database.
what data structure will you use?
I'd have a table of values by frequencies. The items in the rows in rows would be pointers to these pairs. The table of values with frequencies might be an array; it might be a hash table.
Any insertion, removal functions, etc, would have to update frequencies. The table might have to be carefully designed so that it can grow (with rehashing) without invalidating all the pointers in the rows in rows, if enough unique values are added.
This might be unnecessarily complicated for your task.
