Insertion Sort with linked list?

how to preform a insertion sort with a linked list?

Page 1 of 1

5 Replies - 5730 Views - Last Post: 10 February 2010 - 01:52 PM Rate Topic: -----

#1 Guest_Franz*


Reputation:

Insertion Sort with linked list?

Posted 07 February 2010 - 08:31 PM

ok i have been sitting here for some days now and i still can't figure out how to do this.
it is for school so i don't want any other methods, i simply want to relink all the nodes with an insertion sort

here's the code i have so far.
public void sort()
    {
        Link out;
        Link in = null;
        for (out = first.getNext(); out != null; out = out.getNext())
        {
            Link temp = new Link(out.getData());
            in = out;
            while (in.getPrev() != null && in.getPrev().getData() >= temp.getData())
            {
                in = in.getPrev();
            }
            Link right = null;
            Link left = null;
            temp.setNext(in);
            if (in.getPrev() == null)
            {
                temp.setPrev(null);
                first = temp;
                right = out.getNext();
            } else if (in.getNext() == null)
            {
                in.getPrev().setNext(temp);
                temp.setNext(null);
                left = out.getPrev();
                last = temp;
                temp.setPrev(in.getPrev());
            } else
            {
                right = out.getNext();
                left = out.getPrev();
                in.getPrev().setNext(temp);
                temp.setPrev(in.getPrev());

            }
            in.setPrev(temp);
            if (right != null && left != null)
            {
                right.setPrev(out.getPrev());
                left.setNext(out.getNext());
            } else if (left != null)
            {
                left.setNext(out.getNext());
            } else if (right != null)
            {
                right.setPrev(out.getPrev());
            }
        }
    }


Is This A Good Question/Topic? 0

Replies To: Insertion Sort with linked list?

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 9025
  • View blog
  • Posts: 33,466
  • Joined: 27-December 08

Re: Insertion Sort with linked list?

Posted 07 February 2010 - 09:04 PM

This looks a little to complicated to be an Insertion Sort. I think you're doing too much with all your checks for null nodes, as the only null references you should find are the tailNode.nextNode and the headNode.previousNode (if you're implementing a doubly-linked list).

Basically, you want to remove each element from the list starting at the first, going to the end. Then, for each removal, start at the beginning through the position you pull and find where the element fits (meaning the next elem is less than the removed elem) from the beginning up to the element before its position at removal, and add it in there.

So for example, given [4, 2, 3, 1, 5], you start with 2. The elem before 2 is 4, so from the beginning to that elem, two is less than 4 so your revised list is [2, 4, 3, 1, 5]. Now grab 3, and iterate from the beginning to the position before 3. You need to insert it between 2 and 4 so [2, 3, 4, 1, 5]. We will continue this process until the list becomes [1, 2, 3, 4, 5]. The difference with LinkedLists are that you just add a Node at the desired index rather than resizing an array. So if you've implemented add(index, elem) and remove(index) methods for your list, I would take advantage of them.

Go ahead and give your implementation another try considering these suggestions. Feel free to post if you run into more problems or have more questions. Good luck! :)
Was This Post Helpful? 0
  • +
  • -

#3 Guest_franz*


Reputation:

Re: Insertion Sort with linked list?

Posted 08 February 2010 - 07:16 AM

well i've considered moving to another list which would be the easiest choise but i realy just want to move the links. but if i do that then the loop will go on forever cause the in will link to the out and the out will link to the in and it will just crash. so i made the temp variable as a new variable, to put it where the old one should be. but it seems like i will go for doing what you say. just add it to a new list in a sorted way
Was This Post Helpful? 0

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 9025
  • View blog
  • Posts: 33,466
  • Joined: 27-December 08

Re: Insertion Sort with linked list?

Posted 08 February 2010 - 08:50 AM

Do you have some counter variable to keep track of the number of elements in the list? Really, you just need to iterate from the second to the last element in the outer for loop, and the beginning to the ith element in the nested for loop. So if you have a counter field or a size() method, you'll find them very helpful.
Was This Post Helpful? 0
  • +
  • -

#5 Guest_Franz*


Reputation:

Re: Insertion Sort with linked list?

Posted 08 February 2010 - 10:22 AM

i did it the "simple" way. I prolly will get the other one to work somehow but it's good to have a backup for delivery, here is the working code

the loop that goes through all the items in the list.
class something
{

    private Link first;
    private Link last;
    private Link newFirst;
    private Link newLast;

public void sort()
    {
        Link out;
        Link in = first;
        int tell = 0;
        for (out = first; out != null; out = out.getNext())
        {
            insertSort2(out.getData());
            tell = tell + 1;
        }
        System.out.println("antall " + tell);
        first = newFirst;
        last = newLast;
        newFirst = null;
        newLast = null;
    }

the insert method
public void insertSort2(long data)
    {
        Link current = newFirst, previous = null;
        Link newLink = new Link(data);
        while (current != null && data >= current.getData())
        {
            previous = current;
            current = current.getNext();
        }
        if (previous == null)
        {
            if (current != null)
                newFirst.setPrev(newLink);
            newFirst = newLink;
        } else
        {
            previous.setNext(newLink);
            if (current != null)
                current.setPrev(newLink);
        }
        if (current == null)
        {
            if(previous != null)
                newLast.setNext(newLink);
            newLast = newLink;
        }
        newLink.setNext(current);
        newLink.setPrev(previous);

    }

Was This Post Helpful? 0

#6 Guest_Franz*


Reputation:

Re: Insertion Sort with linked list?

Posted 10 February 2010 - 01:52 PM

k guys i got the original insertion sort to work without making new nodes, here's the code hope it will help some of you :)
public void sorting()
    {
        Link out;
        Link in = null;
        //går gjennom alle nodene i lista
        for (out = first.getNext(); out != null; out = out.getNext())
        {
            Link temp = out;
            in = out;
            //går fra out bakover til man når null og så lenge den forige linken er større enn
            // dataen i temp
            while (in.getPrev() != null && in.getPrev().getData() > temp.getData())
            {
                //beveg ett hakk bakover i lista
                in = in.getPrev();
            }
            // hvis in ikke er lik out, grunnen til at denne er her er hvis out noen gang er lik in
            // så linker man in til out og når de er de samme linker man til seg selv og ender opp
            // med en evig loop
            if (in != out)
            {
                //Setter forige temp og neste temp sammen
                if (temp.getPrev() != null)
                {
                    temp.getPrev().setNext(temp.getNext());
                }
                if (temp.getNext() != null)
                {
                    temp.getNext().setPrev(temp.getPrev());
                }
                if (in.getPrev() == null)//hvis først
                {
                    first.setPrev(temp);//førstes forrige = temp
                    temp.setNext(first);//setter temps neste til first
                    first = temp;//Setter first til temp
                    first.setPrev(null);// forige = null
                }

                else
                {
                    //linker temp til in og in til temp
                    temp.setPrev(in.getPrev());
                    in.getPrev().setNext(temp);
                    in.setPrev(temp);
                    temp.setNext(in);
                }
            }
            //sjekker etter siste
            if (out.getNext() == null)
            {
                last = out; // setter siste
            }
        }
    }


sorry about the norwegian comments, didn't have time to remove them for this post
Was This Post Helpful? 0
Page 1 of 1