Sort an simple linked list

Question

I try to sort an linked list, but my code didn't work and idk why.

My input: 85, 92, 78, 27, 13, 68, 11, 92, 73

My output before using sort method: 85, 78, 92, 27, 13, 68, 11, 92, 73.

  Node prev = first;
  Node aux = first.next;
  Node next = aux.next;
  while (next != null) {
                if (Utility.greaterT(aux.data, next.data)) {
                    aux.next = next.next;
                    prev.next = next;
                    next.next = aux;
                    
                    prev = next;
                    next = aux.next;
                    aux = aux.next;
                } else {
                    prev = aux;
                    aux = next.next;
                    next = next.next;
                } // If
            } // While;

the method greaterT just verifiy if the first value is bigger than the second value.

Just sorting the second and the third value.

Answer 1

The answer is your algorithm cannot be fixed. Please take Sephen's advise to learn about a possible solution: e.g. Bubble sort (the article exists in different languages if that helps)

I'll try to explain and hope you will see better then.

You are trying to sort a singly linked list and you are using 3 references (prev, aux and next). You cannot sort an arbitrary singly linked list with this approach. To see this try to think about the following:

At any given moment you can compare at most 4 values: prev, aux, next and next.next - that is what you can do at the moment (if you think of using var.next.next..., that won't work in general).

Let's presume that is what you will do and you start with the first 4 items. Assume you can sort them correctly in order, e.g. 4 5 6 7 ...

You move on with the 3 references and you see something like: 5 6 7 3 - what is going to be done with the first item 4 ? It is obviously greater than 3 - you will end up with 4 3 5 6 7 ...

Answer 2

Try to fix your chunk of code with this

  Node prev = first;
  Node aux = first.next;
  Node next = aux.next;
  while (next != null) {
                if (Utility.greaterT(aux.data, next.data)) {
                    aux.next = next.next;
                    prev.next = next;
                    next.next = aux;
                    
                    prev = next;
                    next = aux.next;
                    // I eliminated this line
                } else {
                    prev = aux;
                    aux = next;
                    next = next.next;
                } // If
            } // While;