- Algorithm Instrumentation
- Create Sorting Program
- Instrumenting Insertion Sort
- Instrumenting Merge Sort and Quick Sort
- Hybrid Sort Algorithm
- Submit Work

In this lab we will continue our analysis of sorting algorithms by comparing the performance of insertion sort, merge sort, and quick sort. This time, we will "instrument" the sorting functions to measure how much work they are doing. Our experiments will use different types of input data (unsorted, semi-sorted, and sorted) to estimate the best case, worst case, and average case performance.

As you saw in the previous lab, measuring cpu times gives us a way to compare the overall performance of different algorithms. One downside to this approach is that it does not give accurate information if the data sets are too small, because the cpu times are essentially zero. Furthermore, this approach does not separate out the cost of comparing data and the cost of moving data.

To get more detailed information about how a sorting algorithm
performs, we can "instrument" the code by counting the number of
times specific operations are executed. For example, we can
increment a **compare_counter** whenever we compare two data
values, and we can increment a **move_counter** whenever we move
data from one position in the array to another location.

Create a new project in NetBeans cut and paste the functions "random_data", "shuffle_data", "insertion_sort", "merge_sort" and "quick_sort" from below into your program. Now create a main program that creates an array of 1000 integers, and calls one of the data initialization functions and one of the sorting functions to make sure everything is compiling and running.

//------------------------------------------------------------------ // Initialize data array with random values between 0 and range-1 //------------------------------------------------------------------ void random_data(int data[], int count, int range) { // Put specified count of random numbers into data array for (int index = 0; index < count; index++) data[index] = rand() % range; } //------------------------------------------------------------------ // Shuffle data values inside data array //------------------------------------------------------------------ void shuffle_data(int data[], int count, int shuffles) { // Shuffle data by swapping random pairs of values for (int index = 0; index < shuffles; index++) { int pos1 = rand() % count; int pos2 = rand() % count; int temp = data[pos1]; data[pos1] = data[pos2]; data[pos2] = temp; } } //---------------------------------------------------------------- // Insertion sort algorithm //---------------------------------------------------------------- void insertion_sort(int data[], int low, int high) { // Insert each element of unsorted list into sorted list for (int unsorted = low+1; unsorted <= high; unsorted++) { // Select unsorted value to be inserted int value = data[unsorted]; int posn = unsorted; // Make room for new data value while ((posn > 0) && (data[posn - 1] > value)) { data[posn] = data[posn - 1]; posn--; } // Put new value into array data[posn] = value; } } //---------------------------------------------------------------- // Quicksort adapted from Sedgewick's partition algorithm //---------------------------------------------------------------- void quick_sort(int data[], int low, int high) { // Check terminating condition int range = high - low + 1; if (range > 1) { int pivot = data[high]; int left = low - 1; int right = high; int temp; // Partition array into two unsorted sections do { // Scan left to right while ((left < right) && (data[++left] < pivot)); // Scan right to left while ((left < right) && (data[--right] > pivot)); // Swap data values temp = data[left]; data[left] = data[right]; data[right] = temp; } while (left < right); // Correct for last swap data[right] = data[left]; data[left] = data[high]; data[high] = temp; int mid = left; // Recursive calls to sort array quick_sort(data, low, mid - 1); quick_sort(data, mid + 1, high); } } //---------------------------------------------------------------- // Mergesort using secondary storage for data merging. //---------------------------------------------------------------- void merge_sort(int data[], int low, int high) { // Check terminating condition int range = high - low + 1; if (range > 1) { // Divide the array and sort both halves int mid = (low + high) / 2; merge_sort(data, low, mid); merge_sort(data, mid + 1, high); // Create temporary array for merged data int *copy = new int[range]; // Initialize array indices int index1 = low; int index2 = mid + 1; int index = 0; // Merge smallest data elements into copy array while (index1 <= mid && index2 <= high) { if (data[index1] < data[index2]) copy[index++] = data[index1++]; else copy[index++] = data[index2++]; } // Copy any remaining entries from the first half while (index1 <= mid) copy[index++] = data[index1++]; // Copy any remaining entries from the second half while (index2 <= high) copy[index++] = data[index2++]; // Copy data back from the temporary array for (index = 0; index < range; index++) data[low + index] = copy[index]; delete []copy; } }

Create two global variables called **compare_counter**
and **move_counter** at the top of your program.
Then go into the "insertion_sort" function and add some
code to increment these counters whenever you compare
data values or move data values.

Now modify the main program to initialize these counters, call the "insertion_sort" function, and print out the final values of these counters after the sort has completed.

Test your instrumentation with different size data sets N=10, N=100, N=1000 using unsorted data, semi-sorted data, and sorted data. To test with sorted data, you can start with unsorted data, and sort it using one of the other sort functions.

Cut and paste your modified "insertion_sort" function below:

Cut and paste the output of your experiments below:

Repeat the instrumentation process on the "merge_sort" and "quick_sort" functions to count the number of comparisons and moves. Run your experiments again with N=10, N=100, and N=1000 using unsorted data, semi-sorted data, and sorted data. Hopefully you will see a huge difference in worst case behavior. This is because merge sort and quick sort are NlogN algorithms and insertion sort is N^2.

Cut and paste your modified "merge_sort" and "quick_sort" functions below:

Cut and paste the output of your experiments below:

It is possible to improve overall sorting performance by creating a hybrid sort algorithm that combines two or more classic sorting algorithms. One common idea is to use one algorithm when the amount of data is small, and another algorithm when there is a lot of data.

Go into the "quick_sort" function or "merge_sort" function and modify the code to call the "insertion_sort" function whenever the amount of input data is small. It is up to you to decide what "small" means, and where to call "insertion_sort".

Since you used the same variables to instrument both functions, you can run your experiments again with N=10, N=100, and N=1000 data values using unsorted data, semi-sorted data, and sorted data and this will produce combined instrumentation results. Hopefully, you will do better with your hybrid sorting algorithm than you did with your original "merge_sort" or "quick_sort" functions.

Cut and paste your modified "merge_sort" or "quick_sort" function below:

Cut and paste the output of your experiments below:

This lab assignment will be submitted electronically to the TAs once you fill in the fields below and click on the "submit" button. You do NOT need to print a copy of this document to hand in.

Your full name: | |

Your uaid number: |