In this homework, we have to write code to perform a radix sort with the data which are social security numbers in the form xxx xxx xxx. Our professor gave us pseudo code to follow but I'm a little lost on how to write this program. I have added some pictures of the pseudo-code.

// *********************8 psuedo code follows: **********************

// for (pass = 0, 1, 2) // this is the outer loop // { // for(j) 0 -> < 1000, set bucket[] to all zeroes (NULL) for each pass// note we are not deleting the old nodes, this is not good programming because we create a memory leak // if you want to delete the old nodes, go ahead, but it is not necessary for your grade in this lab. The leaked memory goes away once the program ends.

// for(i 0, < n) // inner loop - walk through the out array (which contains the data to be sorted // { // int index; // where in the bucket do we want to store this data // switch(pass) // refer to the Powerpoint to see how to parse the digits // {// refer to the Powerpoint to see how to parse the digits // case 0: // set index to the last 3 digits // break; // case 1; // set index to the middle 3 digits // break; // case 2: // set index to the first 3 digits // break; // };

// if(bucket[index] == NULL) // { // nothing is stored here so // bucket[index] = new node(out[i], NULL); // create a new head node and store this data // } // else // { // something is already here so make a new node, store the out[i] in the new node // walk the linked list from the head (bucket[index] to find the last node (tail). // make tail point to the new node you just created. // } // } // end of the inner (i) loop

// int idx = 0; // you need this to load the out array // for(i) 0 -> < 1000 // walk through the bucket // { // if(bucket[i] == NULL)continue; nothing was stored here so skip to the next item // something is stored here, so put it into the out array starting at the beginning (idx) //out[idx++] = bucket[i]->data[i]; // now see if there are more nodes in the linked list that starts at bucket[i]. If there are, put their data into out[idx++] // } // at this point, idx must equal n (use this as a check)

// }// end of the outer loop pass). The output (out) from this pass becomes the input for the next pass

return count;