This week's book giveaway is in the Cloud/Virtualizaton forum.
We're giving away four copies of Mesos in Action and have Roger Ignazio on-line!
See this thread for details.
Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Bubble Sort LinkedList

 
tom davies
Ranch Hand
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 5575
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 5575
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to JavaRanch Tom
 
tom davies
Ranch Hand
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Rancher
Posts: 2756
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 48954
60
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 168
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 10417
63
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic