CODEWITHSUNDEEP
javaalgorithmsortingpredicate
tacos_tacos_tacos
tacos_tacos_tacos

Reputation: 10585

Algorithm for sorting Java objects into buckets, then sorting within buckets

I have the need to take an ArrayList<Conference> conferences, where Conference contains a public Date beginDate parameter, and sort as follows: first, separate conferences into buckets which represent unique months for beginDate, and then sort on beginDate itself within the buckets. I'm sure this is a common need so I was hoping someone here would have some tips.

My idea for this follows. Please tell me why it is sub-optimal :)

  1. Create a HashMap<Date, ArrayList<Conference>>.
  2. Iterate over conferences and use a special static function to find the first day of the month of their beginDate, check if there is an ArrayList<Conference> for that Date. then add them to the ArrayList for that Date (which should all be the same because first_day_of_month(any_day_in_month) is the same.
  3. Iterate over each ArrayList member of the HashMap and use a standard sorting procedure to sort the ArrayList by date.

This seems more complicated than necessary, but please let me know why it's bad and what can be done to fix it.

Edit: Also, if it matters, I will eventually need to add all of those ArrayList back into an ArrayAdapter which will go in commonsware's MergeAdapter... :(

Upvotes: 0

Views: 885

Answers (1)

Boris Strandjev
Boris Strandjev

Reputation: 46953

If you sort by the date from the very beginning the month's entries will be subsequent either way. After the initial sorting you can iterate over all entries and make artificial "split" if an entry is the first one of new month. I am not even sure you will need to do such differentiation (maybe becasue the question is a bit vague on this).

The total complexity of the proposed algorithm is O(nlog n), where n is the number of elements, and of course there is no better solution.

NOTE Btw this algorithm is better than the one proposed by you in operations complexity.

Upvotes: 3

Related Questions