9 Replies Latest reply on Nov 7, 2007 4:18 AM by 807603

# Selection Sort Algorithm

I'm trying to implement a selection sort method with linked lists, but I just can't seem to get it to work correctly.
`````` public void selectionSort(LinkedList list) {
int iterationsINNER = 1, iterationsOUTER = 1, swaps = 0, comparisons = 1;
if(list.isEmpty())
System.out.println("List is currently empty.");
else if (list.size() == 1)
else {
Node pointer = list.getFirst();
Node current;
while (pointer.getNext() != null) {
current = pointer;
iterationsOUTER++;
while (current.getNext() != null && !exchangeMade) {
if(current.getNext().getData() < current.getData()) {
int temp = current.getData();
pointer.setData(current.getNext().getData());
current.getNext().setData(temp);
iterationsINNER++;
swaps++;
comparisons++;
}
current = current.getNext();
}
pointer = pointer.getNext();
}
//  System.out.println("Comparisons: " + comparisons + " \nSwaps: " + swaps + " \nIterations: " + iterationsINNER+iterationsOUTER);
}
}``````
If I test it with this code...
``````        LinkedList list = new LinkedList();
list.insert(5);
list.insert(29);
list.insert(2);
list.insert(1);
list.insert(13);
list.insert(8);
list.insert(30);
list.insert(3);
sort.selectionSort(list);
list.print();``````
I get this as my output...
8
13
1
2
29
5
30
30
• ###### 1. Re: Selection Sort Algorithm
That would be a bubble sort not a selection sort.
• ###### 2. Re: Selection Sort Algorithm
Please clarify one thing for me:

Is the Node class, something you made, or is it in the Java class library (there's quite a few named Node in there)? let me know....

also, the LinkedList class has a generic type attached to it. Meaning you can store any data type in the LinkedList, but you have to specify what you want.

example:
``LinkedList<String> strings = new LinkedList<String>();``
since the list is a parameter you don't have to initialize it, however you still need to specify what data type you're dealing with. I'd use "LinkedList<Object>" if you're not sure what type a user of this method may select, but it looks like you're gonna want to use "LinkedList<Node>".
• ###### 3. Re: Selection Sort Algorithm
after I re-read your question, and saw you got some output; i guess you don't have to specify a parameterized type, but it's probably a good practice to do so.

Edited by: art on Nov 7, 2007 3:00 AM
• ###### 4. Re: Selection Sort Algorithm
Sorry...the LinkedList and Node classes were custom classes. Node takes an int as a parameter.

Ah...I knew that didn't look correct. I've already written a BubbleSort method, and I thought I had read the algorithm for the SelectionSort right...but apparently not.
• ###### 5. Re: Selection Sort Algorithm
selection sort is an n^2 algorithm so that's how many iterations you should have.

(i think)

and btw:
that looks like a selection sort algorithm to me, but you don't need the boolean variable in there.

Edited by: art on Nov 7, 2007 3:48 AM

Edited by: art on Nov 7, 2007 3:52 AM
• ###### 6. Re: Selection Sort Algorithm
that looks like a selection sort algorithm to me
OP is comparing next node with current node and if next node is less than current node, swap them. Sounds like a bubble sort to me!
• ###### 7. Re: Selection Sort Algorithm
Maybe I'm not positive on how a selection sort is supposed to work. Does it pick the smallest element in the list, puts it in the first slot, finds the seconds smallest element in the list and puts it in the second slot...and so on? I thought I was doing this by finding placing it into "position" and looping through the list with "current" to find the smallest element in the linked list.
• ###### 8. Re: Selection Sort Algorithm
Yes that is how selection sort should work but you are only comparing 2 nodes at a time and swapping them. That is a bubble sort. Read this:

http://en.wikipedia.org/wiki/Selection_sort
• ###### 9. Re: Selection Sort Algorithm
yes, you're both correct. (i didn't read it correctly, flounder...it's been a long day)

hehe...yeah, i checked out the wiki to see if i was thinking of the right thing.

so, is this for a school project or just personal stuff?

cause you may want to look into the merge sort for sorting LinkedLists. (or just use Collections.sort(list)...check out the API).

-----
for the implementation you have above, you'll need to have a temp list that keeps getting shorter with each "outer" iteration...

Edited by: art on Nov 7, 2007 4:07 AM

Edited by: art on Nov 7, 2007 4:16 AM