List Insertion Sort

download source

A note on passing Arrays to functions

Given an array of Node pointers…..each element is a pointer to a Node object.

1) We get a random int

2) Create a Node object
3) assign the random into to the Node object

4) then point the array element to the Node object

So now, we have a full array of Node pointers, pointing to Node objects with random integers.

What we’re trying to do is to pass this array into a class SortedLinkedList so that it can process this list.
It processes this list by taking each Node and inserting it into its own data structure. The insert will sort it. Then it will pop the element back onto an array, and thus, we sort it this way.

However, the passing of a whole array into a parameter is done by passing the pointer of pointer of the 1st element in the array. It is designated simply by the array name linkArray.

We know that each array element has an address. The first element’s address has its own address. That address of the address of the 1st element is designated simply by the variable itself, or linkArray.

Let’s display the address of our 1st element’s address in 2 different ways. One through star, and the other through bracket access. Both of which are the same, just different ways of accessing elements in C++. Notice that linkArray, has the same address as them:

linkArray: 0x7fff5fbff6d0

&linkArray[0]: 0x7fff5fbff6d0
&(*linkArray): 0x7fff5fbff6d0

Therefore, that’s how we pass whole arrays into a function.

Create unsorted Array

Create the sort list and pass the unsorted array in

When we pass in the unsorted array, the linked list’s insertion will sort it

Then, because the list was already sorted via insertion, we simply pop the elements from the list and assign it onto the array.
This ensures that what we pop is in sorted order.