using insertion sort with a linked list

Discussion in 'C++' started by Julia, Aug 6, 2006.

  1. Julia

    Julia Guest

    I am trying to sort a linked list using insertion sort. I have seen a
    lot of ways to get around this problem but no time-efficient and
    space-efficient solution. This is what I have so far:

    struct node
    {
    int x;
    struct node *next;
    };

    void sort(struct node *root, struct node *conductor)
    {
    while(0 != conductor->next)
    {
    while(conductor->x < conductor->next->x)
    {
    conductor = conductor->next;
    }
    node *temp, *temp2;
    temp = new node;
    temp2 = new node;
    temp = root;
    temp2 = root;
    while(conductor->next->x > temp->x)
    {
    temp2 = temp;
    temp = temp->next;
    }
    temp2->next = temp->next;
    temp->next = temp2->next->next;
    temp2->next->next = temp;
    }
    return;
    }
     
    Julia, Aug 6, 2006
    #1
    1. Advertising

  2. Julia

    Kai-Uwe Bux Guest

    Julia wrote:

    > I am trying to sort a linked list using insertion sort.


    Consider using std::list. It has a sort method. Also consider using other
    standard containers. There is no need to roll your own list code.

    > I have seen a
    > lot of ways to get around this problem but no time-efficient and
    > space-efficient solution.


    If I recall correctly, insertion sort has quadratic complexity anyway. So
    what do you mean by efficient?

    > This is what I have so far:
    >
    > struct node
    > {
    > int x;
    > struct node *next;
    > };
    >
    > void sort(struct node *root, struct node *conductor)
    > {
    > while(0 != conductor->next)
    > {
    > while(conductor->x < conductor->next->x)
    > {
    > conductor = conductor->next;
    > }


    It appears this loop might run past the end of your list.

    > node *temp, *temp2;
    > temp = new node;
    > temp2 = new node;
    > temp = root;
    > temp2 = root;
    > while(conductor->next->x > temp->x)
    > {
    > temp2 = temp;
    > temp = temp->next;
    > }


    Same here. In order to asses correctness, however, one would need to know
    the preconditions of the contract for sort.

    > temp2->next = temp->next;
    > temp->next = temp2->next->next;
    > temp2->next->next = temp;
    > }
    > return;
    > }


    I am with you so far. Now, what is your question?


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Aug 6, 2006
    #2
    1. Advertising

  3. Julia

    Julia Guest

    Kai-Uwe Bux wrote:
    > Julia wrote:
    >
    > > I am trying to sort a linked list using insertion sort.

    >
    > Consider using std::list. It has a sort method. Also consider using other
    > standard containers. There is no need to roll your own list code.
    >


    I know there is no need to write my own code. I am doing it to
    challenge for myself as opposed to actually using it for something.

    > > I have seen a
    > > lot of ways to get around this problem but no time-efficient and
    > > space-efficient solution.

    >
    > If I recall correctly, insertion sort has quadratic complexity anyway. So
    > what do you mean by efficient?
    >


    Obviously using an insertion sort on a linked list is a waste of time,
    energy and space. However, some of the other solutions I have seen to
    this puzzel have consisted of transferring the data from the linked
    list to an array, sorting the array and transferring the data back to a
    linked list. I would like to do this without using that many extra
    memory locations.

    > > This is what I have so far:
    > >
    > > struct node
    > > {
    > > int x;
    > > struct node *next;
    > > };
    > >
    > > void sort(struct node *root, struct node *conductor)
    > > {
    > > while(0 != conductor->next)
    > > {
    > > while(conductor->x < conductor->next->x)
    > > {
    > > conductor = conductor->next;
    > > }

    >
    > It appears this loop might run past the end of your list.

    Hmmm... should the while statement be
    (conductor->x < conductor->next->x) && (0 != conductor->next)
    >
    > > node *temp, *temp2;
    > > temp = new node;
    > > temp2 = new node;
    > > temp = root;
    > > temp2 = root;
    > > while(conductor->next->x > temp->x)
    > > {
    > > temp2 = temp;
    > > temp = temp->next;
    > > }

    >
    > Same here. In order to asses correctness, however, one would need to know
    > the preconditions of the contract for sort.

    Should I add the same thing here? The preconditions are that there is a
    root that points to the first item in a linked list. The last item in
    the list points to a null value. each item in the list contains an
    integer value and a pointer to the next item in the list.
    >
    > > temp2->next = temp->next;
    > > temp->next = temp2->next->next;
    > > temp2->next->next = temp;
    > > }
    > > return;
    > > }

    >
    > I am with you so far. Now, what is your question?

    Right now the program has an infinite loop (i think) for some sets of
    data. It works perfectly for other sets of data though.
    >
    >
    > Best
    >
    > Kai-Uwe Bux
     
    Julia, Aug 6, 2006
    #3
  4. Julia

    Kai-Uwe Bux Guest

    Julia wrote:

    >
    > Kai-Uwe Bux wrote:
    >> Julia wrote:
    >>
    >> > I am trying to sort a linked list using insertion sort.

    >>
    >> Consider using std::list. It has a sort method. Also consider using other
    >> standard containers. There is no need to roll your own list code.
    >>

    >
    > I know there is no need to write my own code. I am doing it to
    > challenge for myself as opposed to actually using it for something.
    >
    >> > I have seen a
    >> > lot of ways to get around this problem but no time-efficient and
    >> > space-efficient solution.

    >>
    >> If I recall correctly, insertion sort has quadratic complexity anyway. So
    >> what do you mean by efficient?
    >>

    >
    > Obviously using an insertion sort on a linked list is a waste of time,
    > energy and space. However, some of the other solutions I have seen to
    > this puzzel have consisted of transferring the data from the linked
    > list to an array, sorting the array and transferring the data back to a
    > linked list. I would like to do this without using that many extra
    > memory locations.
    >
    >> > This is what I have so far:
    >> >
    >> > struct node
    >> > {
    >> > int x;
    >> > struct node *next;
    >> > };
    >> >
    >> > void sort(struct node *root, struct node *conductor)
    >> > {
    >> > while(0 != conductor->next)
    >> > {
    >> > while(conductor->x < conductor->next->x)
    >> > {
    >> > conductor = conductor->next;
    >> > }

    >>
    >> It appears this loop might run past the end of your list.

    > Hmmm... should the while statement be
    > (conductor->x < conductor->next->x) && (0 != conductor->next)


    Other way:

    ( conductor->next != 0 ) && ( conductor->x < conductor->next->x )

    This makes sure that conductor->next->x is only evaluated if it is
    meaningful.

    >>
    >> > node *temp, *temp2;
    >> > temp = new node;
    >> > temp2 = new node;
    >> > temp = root;
    >> > temp2 = root;
    >> > while(conductor->next->x > temp->x)
    >> > {
    >> > temp2 = temp;
    >> > temp = temp->next;
    >> > }

    >>
    >> Same here. In order to asses correctness, however, one would need to know
    >> the preconditions of the contract for sort.

    > Should I add the same thing here? The preconditions are that there is a
    > root that points to the first item in a linked list. The last item in
    > the list points to a null value. each item in the list contains an
    > integer value and a pointer to the next item in the list.


    Yeah, you should have a test

    conductor->next != 0

    before the loop and you should have a test

    temp != 0

    within the loop.

    >>
    >> > temp2->next = temp->next;
    >> > temp->next = temp2->next->next;
    >> > temp2->next->next = temp;
    >> > }
    >> > return;
    >> > }

    >>
    >> I am with you so far. Now, what is your question?

    > Right now the program has an infinite loop (i think) for some sets of
    > data. It works perfectly for other sets of data though.


    The first of the two loops runs off the end for conductor pointing to a list
    that is sorted in increasing order. Is that among the kind of data for
    which the program fails?



    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Aug 6, 2006
    #4
  5. Julia

    Markus Moll Guest

    Hi

    Julia wrote:

    > Obviously using an insertion sort on a linked list is a waste of time,
    > energy and space. However, some of the other solutions I have seen to
    > this puzzel have consisted of transferring the data from the linked
    > list to an array, sorting the array and transferring the data back to a
    > linked list. I would like to do this without using that many extra
    > memory locations.


    Why don't you use in-place merge-sort or quick-sort?
    In-place merge-sort should be easy to implement.

    > Hmmm... should the while statement be
    > (conductor->x < conductor->next->x) && (0 != conductor->next)


    Actually it would be better to test for conductor->next != 0 _first_, before
    trying to dereference conductor->next:

    (0 != conductor->next) && (conductor->x < conductor->next->x)

    Also, you would have to return after the loop in case 0 == conductor->next,
    because then your list is completely sorted.

    >> > node *temp, *temp2;
    >> > temp = new node;
    >> > temp2 = new node;
    >> > temp = root;
    >> > temp2 = root;
    >> > while(conductor->next->x > temp->x)
    >> > {
    >> > temp2 = temp;
    >> > temp = temp->next;
    >> > }


    Some more remarks:

    1. You have a memory leak here. You allocate two nodes and immediately
    discard all pointer pointing to them.

    2. Looks like you're trying to find the two nodes temp2 and temp between
    which conductor should be inserted. You should use the
    invariant "temp2->next == temp", so you had better initialize temp with
    root->next (more intelligible). At the same time, you might think about
    renaming these variables ("temp" is rarely a good name).

    > Should I add the same thing here?


    In fact you needn't, as you know that eventually temp->x >=
    conductor->next->x (hint: temp == conductor)

    You should also consider using a wrapper class (mylist?) around your nodes
    so that you cannot pass around internal nodes but only complete lists.
    Secondly, I don't see the point in passing conductor as an argument instead
    of declaring it as a local variable...

    Markus
     
    Markus Moll, Aug 6, 2006
    #5
  6. Kai-Uwe Bux wrote:

    > Julia wrote:
    >
    >> I am trying to sort a linked list using insertion sort.

    >
    > Consider using std::list. It has a sort method. Also consider using other
    > standard containers. There is no need to roll your own list code.
    >
    >> I have seen a
    >> lot of ways to get around this problem but no time-efficient and
    >> space-efficient solution.

    >
    > If I recall correctly, insertion sort has quadratic complexity anyway. So
    > what do you mean by efficient?
    >
    >> This is what I have so far:
    >>
    >> struct node
    >> {
    >> int x;
    >> struct node *next;
    >> };
    >>
    >> void sort(struct node *root, struct node *conductor)
    >> {
    >> while(0 != conductor->next)
    >> {
    >> while(conductor->x < conductor->next->x)
    >> {
    >> conductor = conductor->next;
    >> }

    >
    > It appears this loop might run past the end of your list.
    >
    >> node *temp, *temp2;
    >> temp = new node;
    >> temp2 = new node;
    >> temp = root;
    >> temp2 = root;
    >> while(conductor->next->x > temp->x)
    >> {
    >> temp2 = temp;
    >> temp = temp->next;
    >> }

    >
    > Same here. In order to asses correctness, however, one would need to know
    > the preconditions of the contract for sort.
    >
    >> temp2->next = temp->next;
    >> temp->next = temp2->next->next;
    >> temp2->next->next = temp;
    >> }
    >> return;
    >> }

    >
    > I am with you so far. Now, what is your question?
    >
    >
    > Best
    >
    > Kai-Uwe Bux
     
    Dmitri Sologoubenko, Aug 11, 2006
    #6
  7. Markus Moll wrote:

    > Hi
    >
    > Julia wrote:
    >
    >> Obviously using an insertion sort on a linked list is a waste of time,
    >> energy and space. However, some of the other solutions I have seen to
    >> this puzzel have consisted of transferring the data from the linked
    >> list to an array, sorting the array and transferring the data back to a
    >> linked list. I would like to do this without using that many extra
    >> memory locations.

    >
    > Why don't you use in-place merge-sort or quick-sort?
    > In-place merge-sort should be easy to implement.
    >
    >> Hmmm... should the while statement be
    >> (conductor->x < conductor->next->x) && (0 != conductor->next)

    >
    > Actually it would be better to test for conductor->next != 0 _first_,
    > before trying to dereference conductor->next:
    >
    > (0 != conductor->next) && (conductor->x < conductor->next->x)
    >
    > Also, you would have to return after the loop in case 0 ==
    > conductor->next, because then your list is completely sorted.
    >
    >>> > node *temp, *temp2;
    >>> > temp = new node;
    >>> > temp2 = new node;
    >>> > temp = root;
    >>> > temp2 = root;
    >>> > while(conductor->next->x > temp->x)
    >>> > {
    >>> > temp2 = temp;
    >>> > temp = temp->next;
    >>> > }

    >
    > Some more remarks:
    >
    > 1. You have a memory leak here. You allocate two nodes and immediately
    > discard all pointer pointing to them.
    >
    > 2. Looks like you're trying to find the two nodes temp2 and temp between
    > which conductor should be inserted. You should use the
    > invariant "temp2->next == temp", so you had better initialize temp with
    > root->next (more intelligible). At the same time, you might think about
    > renaming these variables ("temp" is rarely a good name).
    >
    >> Should I add the same thing here?

    >
    > In fact you needn't, as you know that eventually temp->x >=
    > conductor->next->x (hint: temp == conductor)
    >
    > You should also consider using a wrapper class (mylist?) around your nodes
    > so that you cannot pass around internal nodes but only complete lists.
    > Secondly, I don't see the point in passing conductor as an argument
    > instead of declaring it as a local variable...
    >
    > Markus


    PROVA
     
    Dmitri Sologoubenko, Aug 11, 2006
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jochus
    Replies:
    3
    Views:
    534
    Jochus
    Apr 21, 2005
  2. John N.
    Replies:
    5
    Views:
    572
    John N.
    Dec 31, 2003
  3. Java Newbie

    Insertion Sort on a linked list

    Java Newbie, Feb 4, 2007, in forum: Java
    Replies:
    2
    Views:
    3,449
    Mark Space
    Feb 9, 2007
  4. fool
    Replies:
    14
    Views:
    548
    Barry Schwarz
    Jul 3, 2006
  5. joshd
    Replies:
    12
    Views:
    705
    John Carson
    Oct 2, 2006
Loading...

Share This Page