• Post Reply Bookmark Topic Watch Topic
  • New Topic

Java Set - Selection Sort  RSS feed

 
B Travis
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi All,

When using selection sort to sort a Java set do I remove the duplicate elements before the sort or when it's done?

Thanks
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
you should be able to sort any collection regardless of whether they have duplicates or not. The selection sort algorithm itself has no restriction on duplicates nor does any other sorting algorithm that I know of.

If your goal is to remove duplicate elements, you can save yourself some effort by adding all your elements to a set first before sorting. By definition, a set contains no duplicates. Of course, your elements should implement equals() so the Set can properly tell whether or not two things are the same.
 
Henry Wong
author
Sheriff
Posts: 23295
125
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:If your goal is to remove duplicate elements, you can save yourself some effort by adding all your elements to a set first before sorting. By definition, a set contains no duplicates. Of course, your elements should implement equals() so the Set can properly tell whether or not two things are the same.


The problem with the Set interface, IMHO, is that the interface isn't really good for (external) sorting. There aren't positional set() and get() methods that enable getting at a particular index. I would recommend going to a List interface instead -- and I believe that there is an implementation with an addIfAbsent() method (CopyOnWriteArrayList), which can be used to not add duplicates.

Henry
 
Junilu Lacar
Sheriff
Posts: 11494
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As with skinning a cat, there are multiple options for doing this.  A List has a copy constructor that takes a Collection, so you could add elements to a Set and then create a List from it. Or you could just use streams and distinct(). Of course if OP has to remove duplicates manually so to speak, then all these options are moot.

But there's not much to go on when all OP has given is "When using selection sort to sort a Java set do I remove the duplicate elements before the sort or when it's done?"

@OP: what exactly are you required to do? Eliminate duplicates or sort using the selection sort algorithm? Both? Do you have to program this out yourself or can you use standard library classes?
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
If you already have a Set, then the duplicates shou‍ld already have been removed because adding to a Set shoul‍d not allow duplicates. Go through the Java™ Tutorials and it will tell you what you can do with sets. The mathematical model of sets doesn't usually recognise sorting, but you will find specialised Set interfaces and classes which will do the sorting for you automatically. Follow the links in that tutorial and you shou‍ld eventually find everything you want.
 
B Travis
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi. Thanks so much for your replies. I should have explained myself a little better. I've been given an assignment that asks me to sort a set containing duplicates (1 4 6 6 8 1 8 3 2 9 7 ). I need to explain how I'd sort them using selection sort. I understand how to do this, but my question is when do I remove the duplicates? At the beginning or after I've sorted them i.e. at the end of the explanation? Any advice appreciated. I've trawled the net and can't find anything on when to delete the duplicates.
 
Liutauras Vilda
Sheriff
Posts: 4930
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Junilu Lacar wrote:your elements should implement equals()
@OP and hashCode() as Joshua Bloch suggests in his Effective Java book.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
B Travis wrote:. . . a set containing duplicates (1 4 6 6 8 1 8 3 2 9 7 ). . . .
There is no such thing as a set with duplicates; that isn't a set but a sequence (=list). You can convert that List to a Set retaining insertion order. I don't think of that as a set myself, but I think of it as a hybrid collection, partially set and partially list. If you go through the Java™ Tutorials link I gave you yesterday, you can find how to use that sort of set to convert your sequence to a set with a record of insertion order. You might have to copy that into a List implementation or similar so as to have something you can sort.
Is this supposed to be an exercise in writing your own sorting algorithm? You would appear to have found the algorithm somewhere.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Alternatively, consider sorting that sequence and then later remove the duplicates. Sorting with selection sort runs in n² time, as would seeking duplicates, but removing duplicates from a ready‑sorted list can probably be done in linear complexity.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!