I'm trying to sort a list of integers using bubble sort, insertion sort and selection sort and so far it isn't going so hot. I've created my own LinkedList class (singly linked list) and am a little stuck. Here's everything I have so far...
Ignore the insertionSort method. The bubbleSort methods ALMOST works. For some reason it ignores about half the list and sorts the other half correctly. Any tips/advice on improving my existing code and help on the other sorting methods will be VERY much appreciated. Thanks!!
I think you're on the right track, but a couple of things I see here:
First, as far as general Java practices (and most object-oriented languages), you should start all class names with a capital letter, such as SortingMethods or SortingTest, not how you have it (although you did it correctly with some classes).
Another point is about your LinkedList class. I'm not sure this would be classified as a doubly LinkedList. A doubly LinkedList has pointers to the next and previous nodes (hence a doubly linked list), but your Node only points to the next node, which would make it a singly, or just a regular LinkedList.
To help make your code a little easier to read, look at methods like your LinkedList isEmpty method. Instead of "if(count...)", just do something like "return count == 0;" without the if statements.
Now, as for the bubble sort algorithm. I think the reason it's not working properly is because you don't pass through the whole list on each iteration. You should start with the first element of the list on each pass through the list and stop once you get through the entire list without doing any swaps. Think of this list: 2, 4, 1. The way your algorithm is implemented, it will swap the 4 and the 1 and will leave the list 2,1,4, but since you never go back to the beginning of the list, you'll never swap the 2 and the 1. Does that make sense?
Now some last Java points, and this is probably somewhat beyond where you are now because it looks like you're in a basic Java class. Typically, you would want to have an interface called Sorter (or something like this). The sorter would have a method called sort(LinkedList l). You could then have a couple of different implementations of it, such as BubbleSorter, InsertionSorter, etc. Then you would have a method called sortList(LinkedList l, Sorter s) that would simply call s.sort(l), and this would sort the list based on the sorter you passed in. But, the method wouldn't need to know the type of sorter. I know I've inlined a lot of code here, but hopefully that gives you some ideas.
Hopefully I haven't thrown too much at you, but I hope this helps. Feel free to ask more questions if you'd like.
posted 11 years ago
Yes, I still have questions How can I make sure that it checks each one? I've added a boolean variable to check whether a swap is made or not, so I've got that covered, but I don't know how to restart or continue from the correct place.
posted 11 years ago
Okay! I've changed it a bit more, but for some reason I still have one larger int stuck at the front of the list whenever I print it out.