• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • paul wheaton
  • Ron McLeod
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Liutauras Vilda
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Carey Brown
  • Piet Souris
Bartenders:

Linked List Sorting Problems

 
Greenhorn
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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!!
 
Ranch Hand
Posts: 230
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 230
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Try something like this...


[ October 01, 2007: Message edited by: Jeff Storey ]
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic