aspose file tools*
The moose likes Java in General and the fly likes Linked List Sorting Problems Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Java 8 in Action this week in the Java 8 forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Linked List Sorting Problems" Watch "Linked List Sorting Problems" New topic
Author

Linked List Sorting Problems

Joel Cochran
Greenhorn

Joined: Sep 28, 2007
Posts: 6
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!!
Jeff Storey
Ranch Hand

Joined: Apr 07, 2007
Posts: 230
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.

Jeff
Joel Cochran
Greenhorn

Joined: Sep 28, 2007
Posts: 6
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.
Joel Cochran
Greenhorn

Joined: Sep 28, 2007
Posts: 6
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.



The output looks like this:
8409
0
0
12
63
97
636
682
773
847
905
933
1258
1338
1826
1992
2543
2868
3026
3221
3287
3671
3796
3800
3829
3945
4420
4607
4782
4950
5242
5337
5898
6091
6154
6160
6216
6598
7089
7154
7203
7515
7542
7654
8147
8149
8511
8687
8907
8984
8997
9976
Jeff Storey
Ranch Hand

Joined: Apr 07, 2007
Posts: 230
Try something like this...


[ October 01, 2007: Message edited by: Jeff Storey ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Linked List Sorting Problems
 
Similar Threads
null pointerException handling
Linked List Sorting Problem
compiler will not accept setprev or getprev to make doubly linked listin
Sorting Methods with Linked Lists
Generics: cannot make a static reference to the non-static type