Sorting LinkedList

Question

I cannot figure out where is something I'm missing in the code. Why it only sorts once and puts 50 at last and rest of element are as it was before. Here is my Code.

//TO SORT THE LINKED LIST
  static Node sorted(Node head){
      
      Node temp1 = head;
      Node temp2 = head;
      while(temp1 != null){
          while(temp2 != null){
              if(temp2.data > temp2.next.data){
                  int temp = temp2.data;
                  temp2.data = temp2.next.data;
                  temp2.next.data = temp;
              }
              temp2 = temp2.next;
          }
          temp1 = temp1.next;
      }
      return head;
  }

You should use more descriptive variable-names than just `temp1` and `temp2`. — Dai, Dec 11 '21 at 06:23
Hi sorry, It's Java. So I'm trying to sort my linked list 50,40,30,20,10 in ascending order using two loops. — nick.hil69, Dec 11 '21 at 06:28
Have you used your step-through debugger? If not, **why not**? — Dai, Dec 11 '21 at 06:30
In-place sorting of a linked-list [can be... tricky](https://stackoverflow.com/questions/1525117/whats-the-fastest-algorithm-for-sorting-a-linked-list). There's always the option to create a _view_ of the linked-list as a traditional array and sort that in `O( n log n )` (using quicksort) and then re-build the linked-list (with `O( 2n + n log n )` total time and `O(n)` additional space). — Dai, Dec 11 '21 at 06:32
Your `sorted` function (which should be renamed to `sort`, methods are verbs, not adjectives) appears to partially implement Bubble Sort, which is an inappropriate sorting algorithm (it only sorts elements forward, rather inefficiently). You need to understand how to implement more appropriate algorithms that work on linked-lists _specifically_ (as linked-lists are not randomly-seekable unless you allocated a lookup buffer, which adds `O(n)` space, so you can't use quicksort, for example). — Dai, Dec 11 '21 at 06:36
1) Surely you need to set `temp2` to the `head` of the list before *each* iteration of the inner loop. 2) What happens if you move the first element of the list to later in the list. Shouldn't `head` be updated? Nowhere in your code are you updating `head`. — Stephen C, Dec 11 '21 at 09:04
(No - I'm NOT going to provide you with fixes ... so don't bother asking. Instead you need to understand the problems yourself and work out the fixes for yourself. That way you **learn** ... which is the whole point of your doing homework. And, yes, learning how to use a debugger would be a good thing too.) — Stephen C, Dec 11 '21 at 09:06
Are you sure it is acceptable that you swap the *data* of the nodes, instead of the nodes themselves? Is that specified in the assignment? — trincot, Dec 11 '21 at 09:11

trincot · Answer 1 · 2021-12-11T21:00:21.657

There are two issues in your code:

temp2 should restart from the beginning of the list in every iteration of the outer loop.
temp2.next will eventually be null when temp2.next.data is evaluated. You need to exit the inner loop when you arrive at the last node, not when you are past the last node. So the while condition should be temp2.next != null

With those corrections it will work:

    static Node sorted(Node head){
        Node temp1 = head;
        while (temp1 != null) {
            Node temp2 = head;
            while (temp2.next != null) {
                if (temp2.data > temp2.next.data){
                    int temp = temp2.data;
                    temp2.data = temp2.next.data;
                    temp2.next.data = temp;
                }
                temp2 = temp2.next;
            }
            temp1 = temp1.next;
        }
        return head;
    }

Now, there are still several remarks to make:

You should check whether it is acceptable to swap the data of the nodes, instead of swapping (and rewiring) the nodes themselves. If the caller of the method has references to individual nodes in the list, they may not expect that these nodes will have different values after the list has been sorted. This may come as an unpleasant surprise. Many code challenges will require that you do not modify the data member of nodes, but only their next properties.
You chose bubble sort as your sorting algorithm. This is not a very efficient sorting algorithm, and even this implementation of it could be improved by stopping the inner loop sooner -- knowing that the tail of the list gets sorted gradually, and the outer loop could also exit sooner when it is found that no more swaps were performed. But you'll have a more efficient algorithm when you go for merge sort or quick sort.
The name of the function should be sort, since it modifies the given list. The name sorted would suggest that it doesn't modify the given list, but produces a new list that is the sorted version of it.
temp1 and temp2 are not descriptive variable names. Think of more descriptive names.
You wrote "Why it only sorts once and puts 50 at last and rest of element are as it was before.", but the given code does not have that behaviour: it runs into an exception.

Sorting LinkedList

1 Answers1