Using bubble sort with a linked list

Question

I'm trying to write a method that will sort objects of a linked list based on an integer variable (named priority) of each object. I've used bubble sort before with arraylists and had no trouble, but for some reason when I try it with a linked list, it gives me a NullPointerException and I can't figure out what I'm doing wrong. Any advice?

public void sortList() {
    boolean flag = true;
    Item temp = null;
    Item position = head;
    Item positionLink = position.link;
    while(flag) {
        flag = false;
        while (position != null) {
            if(position.getPriority() > positionLink.getPriority()) {
                temp.setItem(position);
                position.setItem(positionLink);
                positionLink.link.setItem(temp);
                flag = true;
                position = position.getItem();
        }
        }
    }
}

@Algorithmist is it so complex? :) just a good style of asking questions, of course. — Vitaly
– Vitaly, Commented Apr 16, 2013 at 2:53
Vitaly, if you feel like it's an easy question just answer it rather than leaving useless comments. — sashkello
– sashkello, Commented Apr 16, 2013 at 2:54
@user2180462 always check exception stackTrace to reach to the core of the problem.If you would have checked your stackTrace then within seconds you would have resolved temp=null issue. — Algorithmist
– Algorithmist, Commented Apr 16, 2013 at 2:59

Vitaly · Accepted Answer · 2013-04-16 02:55:09Z

3

You did not initialise temp

 temp.setItem(position);

answered Apr 16, 2013 at 2:55

Vitaly

2,8002 gold badges21 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Vitaly · Accepted Answer · 2013-04-16 03:36:44Z

Btw, your algorithm looks wrong.. There is a mess with item.link and item.setItem().. and so on..

Should be something like this:

public void sortList() {

    boolean flag = true;
    while (flag) {
        flag = false;

        Item position = head;
        Item positionNext = position.link;
        Item positionPrev = null;

        while (positionNext != null) {
            if(position.getPriority() > positionNext.getPriority()) {

                Item temp = position;
                Item tempNextNext = positionNext.link;
                position = positionNext;
                position.link = temp;
                positionNext = temp;
                positionNext.link = tempNextNext;

                if (positionPrev == null) { // position is head
                    head = position;
                } else {
                    positionPrev.link = position;
                }

                flag = true;
            }
            positionPrev = position;
            position = position.link;
            positionNext = position.link;
        }
    }
}

JavaDeveloper · Accepted Answer · 2013-09-05 02:27:35Z

 public void bubbleSort() {
        boolean swapped;

        do {
        Node curr = first;
        Node prev = null;
        swapped = false;
        while (curr.next != null) {
            Node fwd = curr.next;

            if (curr.item > curr.next.item) {
                /**
                 * 3 pointers involved: prev, temp and temp.next. simply
                 * follow the order
                 * 
                 * prev.next = temp.next; 
                 * temp.next = temp.next.next;
                 * temp.next.next = temp;
                 */

                /**
                 * egde case: prev: can be null temp & temp.next cannot be
                 * null.
                 */

                if (prev != null) {
                    prev.next = fwd;
                } else {
                    first = fwd;
                }
                // advance prev.
                prev = fwd;

                curr.next = fwd.next;
                fwd.next = curr;
                swapped = true;
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
    } while (swapped);
}

Collectives™ on Stack Overflow

Using bubble sort with a linked list

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related