# IC210 Class 39: Inserting, sorting

Review Section 13.1 of Problem Solving with C++.

Lecture

## Insert in order

One of the nice things about a linked list is that it's pretty easy to insert new nodes anywhere you'd like. If there's a new value you've read in, you might not necessarily want to add it to the front of the list or to the back. You might, for example, want to insert it in a list in a way that maintains sorted order. Let's consider a function `insert_in_order(val,L)` that will insert a new value `val` into `L` so that sorted order is maintained. Here's what we need to do in pictures:

 Start: We want to add `val` to the list `L`. Move `p` to point to the node after which `val` should be added. Create the new node we want, with the proper `data` and `next` values. `Node *T = new Node;``T->data = val;``T->next = p->next;` Splice our new node in after the node `p` points to. `p->next = T;`` `` ` Done!

Now, how do we make that work in C++ code? First we need to "Move `p` to point to the node after which we want to insert our new node".  Here is some code to start with.

 Attempt 1: `  Node *p = L;``  while(p->next->data < val)``    p = p->next;``  add2front(val,p->next);`` ` Commentary: What makes `p` special is that it's the first node in your list whose next node has a bigger data value than `val`. That's what we're looking for here. The only problem is that this'll crash if `val` is bigger than everything currently in the list. To deal with this, we should also stop moving `p` if it's the last node in the list - i.e. if `p->next` is 0. Attempt 2: `  Node *p = L;``  while(p->next != 0 &&             ``        p->next->data < val)``    p = p->next;``  add2front(val,p->next);`` ` Commentary: This works like a champ, but it contains the hidden assumption that `val` will never need to come before the first node. Attempt 3: `if (L->data < val)``{``  Node *p = L;``  while(p->next != 0 && ``        p->next->data < val)``    p = p->next;``  add2front(val,p->next);``}``else``  add2front(val,L);`` ` Commentary: This is fine, except that it crashes if `L` is the empty list, because the test `L->data` implicitly assumes that `L` is really pointing to something! Success! `if (L != 0 && L->data < val)``{``  Node *p = L;``  while(p->next != 0 && ``        p->next->data < val)``    p = p->next;``  add2front(val,p->next);``}``else``  add2front(val,L);`` ` Commentary: This does exactly what we want, in all cases!

Now, let's compare the iterative versus the recursive version of the `insert_in_order` function:

 `void insertInOrder(double val, Node* &L)``{`` if (L!=0 && L->data < val)``   insertInOrder(val,L->next);`` else``   add2front(val,L);``}` `void insertInOrder(double val, Node* &L)``{``  if (L != 0 && L->data < val)``  {``    Node *p = L;``    while(p->next != 0 && ``          p->next->data < val)``      p = p->next;``    add2front(val,p->next);``  }``  else``    add2front(val,L);``}`

You can do this stuff quite elegantly with recursion!

## Sorting

With our `insertInOrder` we can sort stuff pretty easily with linked lists. For example, if you want to read in a bunch of values and put them in sorted order, you can simply put them in a list as you read them using `insertInOrder`, and when you're done, you'll have a sorted list of values. Not bad, eh? Of course, as we know from selection sort there are many, many different "orders" you can put things into when you sort. If you recall, we used the `before(a,b)` function to determine whether element `a` must come before element `b` in sorted order. We really ought to write `insertInOrder` so it relies on a "before" function as well. This program uses linked lists and `insertInOrder` with a "before" function to read in words from the user and write them back sorted by increasing length, with ties broken by alphabetical order. Here's an example of the program in action:

`Enter words, terminated with a semi-colon:`
`the quick brown fox jumped over the lazy dog ;`
`dog fox the the lazy over brown quick jumped `

## Sorting existing lists

Suppose that you already have a list and it's not in sorted order. You could easily create a sorted copy of the list by moving through you list a node at a time and calling `insertInOrder` for that node's data.

`Node* sortedCopy(Node* L)`
`{`
`  Node* S = 0;`
`  for(Node* p = L; p != 0; p = p->next)`
`    insertInOrder(p->data,S);`
`  return S;`
`}`

This function returns a copy of the original list in sorted order.

Problems

1.      Write a program that reads in commands from the user, which are quit, add x, and print. Each time the add x command is given the actual number (as opposed to x) is stored. Each time the print command is given, all the numbers added thus far are printed out in sorted order. I'll leave it to you to guess what the quit command does!

2.      Use the "merge" function from the previous homework to sort.

Assoc Prof Christopher Brown