# Selection Sort using Linked Lists

**807603**Dec 3, 2007 7:37 PM

As the subject says, I'm trying to implement a selection sort method on a linked list structure. I've already created a bubble sort, but I can't seem to get this method to work correctly. The Node and LinkedList classes were written by me, and I know they work correctly (because of the other methods work right).

1

8

13

3

2

29

30

5

Anyone have any idea what is going wrong, or is anymore information needed?

PS: I also need to create a insertion sort method with this, and I've been told I need to reverse the list for the insertion sort to work correctly. Any tips on how to implement this method too? :)

```
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)
System.out.println("List is already sorted.");
else {
Node pointer = list.getFirst();
Node current;
boolean exchangeMade;
while (pointer.getNext().getNext() != null) {
current = pointer;
exchangeMade = false;
iterationsOUTER++;
while (current.getNext() != null && !exchangeMade) {
if(current.getNext().getData() < pointer.getData()) {
int temp = pointer.getData();
pointer.setData(current.getNext().getData());
current.getNext().setData(temp);
exchangeMade = true;
iterationsINNER++;
swaps++;
comparisons++;
}
current = current.getNext();
}
pointer = pointer.getNext();
}
// System.out.println("Comparisons: " + comparisons + " \nSwaps: " + swaps + " \nIterations: " + iterationsINNER+iterationsOUTER);
}
}
```

For instance, if I run this bit of 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();
```

The output is...1

8

13

3

2

29

30

5

Anyone have any idea what is going wrong, or is anymore information needed?

PS: I also need to create a insertion sort method with this, and I've been told I need to reverse the list for the insertion sort to work correctly. Any tips on how to implement this method too? :)

- 1210 Views
- Tags: none (add)