If memory were not scarce, how would you implement a sort in a language with libraries for representing and sorting sets

If memory were not scarce, how would you implement a sort i开发者_StackOverflow中文版n a language with libraries for representing and sorting sets

A set is unordered, so sorting sets is useless. A "sorted" set is the same as the set itself, even with scarce memory.

To represent a set in non-scarce memory, is just like representing a set in scarce memory. However, if memory is not scarce, we could create a binary predicate for each value or object in memory, stating: "I'm member of set X".

If you want to check whether object Y is member of set X, then just check the binary predicate; which is either true or false.

The iteration of all objects in a set is like an array. It can also be implemented as a double-linked-list or using a hashtable. The difference is all in the details; what objects do you want in the set?

If memory were not scarce, and you've got enough horse-power in your CPU left, then I would store every hash value of an object in memory, instead calculating it on the fly. Then, a hashtable-esque implementation of a set is really fast for listing capabilities. Adding/removing objects from the set is rather slow.

If adding/removing is more needed than listing, any linked-list will do.

Both ways could use the predicate value for each object. It depends on your requirements; for instance, do you allow two objects simultaneously in two sets? (Generally this is a "yes"), then you'll need an array/linked-list storage for each object in the set, to store it's membership information.

There is no "one right" solution, though. Just my two pennies.

It very much depends on the situation. I am going to assume you meant list, and not set. And also, how scarce the memory is.

In either case, read this- http://en.wikipedia.org/wiki/Sorting_algorithm#Summaries_of_popular_sorting_algorithms

In all cases, an in-place merge sort wouldn't be bad. http://en.wikipedia.org/wiki/Merge_sort This sort doesn't use any order of extra memory when sorting

Quicksort is often better if the memory isn't that scarce. http://en.wikipedia.org/wiki/Quicksort

And then Bucket and Radix sort work very well on certain types of data. Ie. if you're numbers are all less than 10,000, these sorts work very well.

They work less well on when number set is too large. (ie, random 32bit ints). http://en.wikipedia.org/wiki/Bucket_sort http://en.wikipedia.org/wiki/Radix_sort

EDIT: Note: I ignored the whole libraries for representing and sorting sets. WTF does that have to do with anything? Maybe that question is.. if I have a library to sort lists that can only have one of each? If thats the case the question is far too weird and sounds like homework.