wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes Bubble Sort LinkedList Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Bubble Sort LinkedList" Watch "Bubble Sort LinkedList" New topic
Author

Bubble Sort LinkedList

tom davies
Ranch Hand

Joined: Apr 27, 2012
Posts: 168
I have a linkedList of assignments, they all have a string holding the date the assignment was set.
I want to be able to sort these assignments by the date in which they were set.
I can convert the strings into dates and compare them using the .before() method to see which comes first.
My problem is how to swap the assignments around if one is before the other.

I thought about getting the index of the assignments using indexof() and then swapping it with another. . .
not sure if that will work or if theres a better way to do it.

Thanks
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

do you know how bubble sort works? and you know how to compare one another and now try it yourself ! DoYourOwnHomework
Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

Welcome to JavaRanch Tom
tom davies
Ranch Hand

Joined: Apr 27, 2012
Posts: 168
Hi, i wasn't trying to get it written for me below is what i have at the moment, im just trying to get some pointers and to see if im going in the right direction.

Jayesh A Lalwani
Bartender

Joined: Jan 17, 2008
Posts: 2273
    
  28

Few things that I notice

a) iterator.next will move the iterator. So, if you call iterator.next twice inside your loop, it will move 2 steps. Call iterator.next only once if you expect to move it only once
b) This doesn;t look like bubble sort. you are always comparing the date of the first element with the date of the current element. In bubble sort, you compare the date of consecutive elements and swap them.
tom davies
Ranch Hand

Joined: Apr 27, 2012
Posts: 168
Ive made a few changes to it now, im comparing to the previous element instead of the first and also not calling next() twice. Can you give me some guidance on the section after if(dateCheck.before(date)) where im trying to swap the index so i can then set the assignments at a different index afterwards. Its telling me that the assigned value is never used at line 39 and 41 on here.

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38006
    
  22
Warning. You ought not to try to sort a linked list. If you look at the Collections class‘ method, you see it copies the list into an array, sorts the array and the re-creates the list, and gives you an explanation why. Also notice it uses the Comparable interface (compareTo method) or a Comparator. If you are trying to sort Dates, etc., they will most probably already implement Comparable, so you have that method ready to use.
tom davies
Ranch Hand

Joined: Apr 27, 2012
Posts: 168
Thanks campbell ritchie, i understand why it puts it into an array as it makes the sorting process more efficient. Its going to take me a while to get my head around how to do this. Any hints and tips you could give me for where to start, ive already read the link and searched for a few examples.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 7545
    
  18

tom na wrote:Thanks campbell ritchie, i understand why it puts it into an array as it makes the sorting process more efficient. Its going to take me a while to get my head around how to do this. Any hints and tips you could give me for where to start, ive already read the link and searched for a few examples.

Well, Wikipedia has several good pages on various sort algorithms, including bubble sort; however, swapping entries in a LinkedList is somewhat tricky because the class's API doesn't give you access to them (I kind of wish it did). Your idea of using an Iterator is a good one, but I suspect you'll need two of them to perform the swap optimally (ie, without using direct-access methods like add(int, E) and remove(int), which are very slow for LinkedList's).

Another possibility is to look at the source code for Collections.sort(). It doesn't actually use bubble sort, and it's geared for Lists that implement the RandomAccess interface (which LinkedList doesn't), but it might give you some pointers.

Finally, you could write a LinkedList class of your own which does provide access to entries, and then add a
swap(Entry e1, Entry e2)
method. Then a bubble sort should be a doddle.

HIH

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Bubble Sort LinkedList
 
Similar Threads
Loose coupling : Avoid using implementation types like 'LinkedList'; use the interface instead
Sorting of vector
XML for Assignment Log
Sorting based on the value object in the collection
LinkedList