Skip to main content

Sorting a linked list in Java


I have written a bubble sort algorithm to sort a linked list. I am a Java beginner and trying to learn data structures. I am confused why my second element is not sorted properly.



EDIT




class SListNode {
Object item;
SListNode next;


SListNode(Object obj) {
item = obj;
next = null;
}


SListNode(Object obj, SListNode next) {
item = obj;
this.next = next;
}

}
public class SList {

private SListNode head;
private SListNode temp;

public void sortList() {
SListNode node = head,i,j;
head = node;
i = node;
j = node.next;
while(i.next != null) {
while(j.next != null) {
if((Integer)i.item < (Integer)j.item) {
temp = i.next;
i.next = j.next;
j.next = temp;
}
j = j.next;
}
i = i.next;
}
}
}



This is the output I am getting




List after construction: [ 3 6 9 4 12 15 ]
After sorting: [ 3 4 9 12 6 15 ]



Besides I know the worst case scenario of a bubble sort is O(n 2 ). Can I use mergesort on a linked list to have a better time complexity?



Thanks!


Source: Tips4allCCNA FINAL EXAM

Comments

  1. There are many sorting algorithms that work on linked lists and mergesort works excellently in this case. I wrote an earlier answer to a question about sorting linked lists that explores many classic sorting algorithms on linked lists, along with their time and space complexities. You can use insertion sort, selection sort, mergesort, and quicksort on linked lists. With a bit of fudging, you can also get heapsort working. My older answer has details on how to do this.

    With regards to your code, notice that in your inner loop you advance j forward until the next pointer becomes null. At this point, you never reset j to be anything else, so on each future iteration of the outer loop the inner loop never executes. You should probably set j = i.next at the start of each iteration. Moreover, you probably don't want to have the loop stop when j.next is null, but rather when j is null, since otherwise you skip the last element of the array.

    Additionally, the sorting algorithm you've written here is selection sort rather than bubble sort, because you're making many passes over the linked list looking for the smallest element that you haven't positioned yet. I don't know if this is a problem or not, but I wasn't sure if you were aware of this. That said, I think that's probably a good thing, since bubble sort is less efficient than selection sort in most cases (unless the list is already close to being sorted).

    Hope this helps!

    ReplyDelete
  2. Without directly answering, the way to investigate would be to System.out.println() your list after every swap and after each outer loop to see what is happening.

    ReplyDelete

Post a Comment

Popular posts from this blog

Why is this Javascript much *slower* than its jQuery equivalent?

I have a HTML list of about 500 items and a "filter" box above it. I started by using jQuery to filter the list when I typed a letter (timing code added later): $('#filter').keyup( function() { var jqStart = (new Date).getTime(); var search = $(this).val().toLowerCase(); var $list = $('ul.ablist > li'); $list.each( function() { if ( $(this).text().toLowerCase().indexOf(search) === -1 ) $(this).hide(); else $(this).show(); } ); console.log('Time: ' + ((new Date).getTime() - jqStart)); } ); However, there was a couple of seconds delay after typing each letter (particularly the first letter). So I thought it may be slightly quicker if I used plain Javascript (I read recently that jQuery's each function is particularly slow). Here's my JS equivalent: document.getElementById('filter').addEventListener( 'keyup', function () { var jsStart = (new Date).getTime()...

Is it possible to have IF statement in an Echo statement in PHP

Thanks in advance. I did look at the other questions/answers that were similar and didn't find exactly what I was looking for. I'm trying to do this, am I on the right path? echo " <div id='tabs-".$match."'> <textarea id='".$match."' name='".$match."'>". if ($COLUMN_NAME === $match) { echo $FIELD_WITH_COLUMN_NAME; } else { } ."</textarea> <script type='text/javascript'> CKEDITOR.replace( '".$match."' ); </script> </div>"; I am getting the following error message in the browser: Parse error: syntax error, unexpected T_IF Please let me know if this is the right way to go about nesting an IF statement inside an echo. Thank you.