• Post Reply Bookmark Topic Watch Topic
  • New Topic

Counting Sort with Objects  RSS feed

 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello,

https://www.youtube.com/watch?v=qNMQ4ly43p4&list=PLD4CAE0D1D2EEF760

In the link above, the professor teaches counting sort on integers in the first few minutes, and then at time 4:15, he says that the sort can't work with objects and then goes on to show how it can be made to work. I am not able to understand how the first version he taught won't work on objects and can't see how the 2nd version will fix that either.

Please help.

Thanks,
Prasanna
 
Tony Docherty
Bartender
Posts: 3271
82
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In the link above, the professor teaches counting sort on integers in the first few minutes, and then at time 4:15, he says that the sort can't work with objects and then goes on to show how it can be made to work. I am not able to understand how the first version he taught won't work on objects and can't see how the 2nd version will fix that either.

That's not what he said. What he said was the first version worked where the items are the keys as opposed to the items having associated values one of which is the key. Therefore, you could use the first version it to sort Integer objects.
The reason you can't use the first version to sort objects which have associated values is because the first version doesn't return the actual items in the input array. It counts the frequency of each item value and then for each of these frequency values it creates and returns that number of items with that value. This won't work for Objects which hold more than one piece of data because in this case you need to return the original object, you can't just create a new object because you don't know what other values the object may hold. The second, admittedly more complex, version fixes this by making sure the original objects are returned.

For example imagine you have a class which holds a persons name and their age and you have an array of objects for each of your friends. Now work through the first version and try to use it to sort the array of objects on your friends ages and see what you get out the other end. Now try to sort the array with the second example.
 
Prasanna Raman
Ranch Hand
Posts: 410
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!