Insertion Sort

In this lab we explore the insertion sort algorithm and conclude by writing our own.

Identifying Elements of an Insertion Sort

1. In this exercise, you will examine two sorting programs to determine whether either is insertion sort. Download and save the programs insertion-sort-proc1.c and insertion-sort-proc2.c in your directory for this lab.
   1. Compile and run both programs. Do both sort the given list appropriately?
   2. Look at insertion-sort-proc1.c. Is this an example of insertion sort?
      Hint: What exactly are the nested for loops doing?
   3. Look at insertion-sort-proc2.c. Is this an example of insertion sort?
      Hint: What exactly is the while loop doing?

Error Checking in Insertion Sort

2. Download and save the program insertion-sort-proc3.c in your directory for this lab.
   1. Compile and run the program with the values 1, 7, 3, 5, 4, 2, 9, 8, 2, 6. Does the program produce the correct output
   2. Now run the program with a few of your own values. Does the program still produce correct output?
      Note: try making some elements in the list negative.
   3. Read through the program to locate the source of the error and fix it.
      Hint: the error is caused by just one line in the program.
   4. Explain why this error caused the output you saw.

Picture Pixels as a 1D Array

3. Download the file 2D-1D-array.c and save it in your current directory.
   1. Read over the program and run it. Describe the output obtained.
   2. The program prints the content of the 2D-array in two different way illustrating how to convert from a 1D-array to a 2D-array.
      • When processing data as a 2D-array, the values of i and j represent the indexes of the rows and columns of the 2D-array.
      • When processing the data as a 1D array, we first create a new array that points to the beginning of the original array.
      Review the storage of 1D and 2D array.
      • The program illustrates at least two ways to specify the base address of a 2D array. Describe both, giving the code and an explanation of what the code means.
      • How is the base address of the corresponding 2D array specified?
   3. How are array values organized from this base address?
   4. Explain how the similarities and differences between these 1D and 2D implementations could help manipulate Pixels.

Insertion Sort with Pictures

Although the description of insertion sort in the reading considered the ordering of integers, the algorithm applies to any data type that can be ordered.

4. Apply the insertion sort to the pixels in a picture.
   1. Download insertion-sort-picture.c and save it in your lab directory. Read over the program and be sure you understand it.
   2. Considering a 2D array of pixels as a 1D array, complete the insertion sort function that sorts pixels in a picture.
      • Insert the correct array parameter in main, so that the pixelInsertionSort function will be applied to the 2D array of pixels in the struct for pic.
      • Copy the insertion sort in the reading for integers into pixelInsertionSort as a starting point. Much of the algorithm will run without change.
      • Add a citation to the code acknowledging its source.
      • Adjust the comparison of the size of array values in sorting, so that the sum of R, G, and B values are compared for two pixels.
      • Adjust the type of material being sorted, so that pixels are manipulated rather than integers.
      Compile and run the program to be sure it works.
5. Assuming the previous step was successful, you observed an original picture and a final picture after the pixels had been sorted.
   1. Add a call to rDisplayPicture within the main loop of the insertion sort, so that a picture is displayed every 50th iteration of the for loop. This should allow you to watch sorting progress periodically as the algorithm runs. (Hint: The modulo operator will allow you to find multiples of a given modulus.)
   2. Change the picture display, so that it updates more or less often than every 50 iterations. Do you find one frequency of updates more insightful or more fun to watch than another?
   3. Describe how the picture changes as sorting progresses.

Insertion Sort with Column-Major Order

Recall that the reading discussed how two-dimensional data may be stored linearly in either row-major or column-major order.

6. Write a program that, using insertion sort, sorts a two-dimensional array in row-major order such that the elements in each row go from smaller to larger.
7. Write a program that takes a two-dimensional array and, using insertion sort, sorts it in column-major order, so the values in the top of each column are the smallest in the column, with the largest value in each column in the bottom.

Note that for the latter exercise, you should not perform a normal insertion sort (row-major order) and simply paste the result in the "column-major sorted" array.