- Algorithm Instrumentation
- Create Sorting Program
- Instrumenting Insertion Sort
- number compares and number moves for N random data values between 0..N-1
- number compares and number moves for N mostly-sorted data (swaps = N/10)
- number compares and number moves for N sorted data values (swaps = 0)
- Instrumenting Merge Sort and Quick Sort
- Hybrid Sort Algorithm
- Submit Work
- Fill in the information below and hit "Submit Lab".
- This will produce a lab report showing what you have done.
- Show your lab report to your GTA for grading and feedback.
- Backup any files you want to keep and delete unwanted files.
- Logout from your machine.

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 (randomn, mostly-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 "create_random_data", "create_mostly_sorted_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 //------------------------------------------------------------------ void create_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; } //------------------------------------------------------------------ // Initialize data array with mostly sorted values //------------------------------------------------------------------ void create_mostly_sorted_data(int data[], int count, int swaps) { // Put sorted data values into array for (int index = 0; index < count; index++) data[index] = index; // Shuffle data by swapping random pairs of values for (int index = 0; index < swaps; 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; } } //---------------------------------------------------------------- // Partition function used by Quicksort. //---------------------------------------------------------------- void partition(int data[], int low, int high, int &mid) { // Select pivot value int pivot = data[high]; int left = low; int right = high; // Partition array into two parts while (left < right) { // Scan left to right while ((left < right) && (data[left] < pivot)) left++; // Scan right to left while ((left < right) && (data[right] >= pivot)) right--; // Swap data values int temp = data[left]; data[left] = data[right]; data[right] = temp; } // Swap pivot to mid mid = left; data[high] = data[mid]; data[mid] = pivot; } //---------------------------------------------------------------- // Recursive Quicksort algorithm using basic partition function. //---------------------------------------------------------------- void quick_sort(int data[], int low, int high) { // Check terminating condition if (low < high) { // Partition data into two parts int mid = 0; partition(data, low, high, mid); // 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 the compare_counter whenever you compare
one of the data elements to another variable. (Look at the
conditions in if-statements, while-loops, and for-loops).
Now add some code to increment the move_counter whenever
you assign a new value into one of the data elements.

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. This will tell you roughly how much "work" the function does while sorting the data.

Test your revised code with different size data sets N=10, N=100, N=1000 and save the following information:

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. For merge sort, you should count the number of moves into the data array and also the copy array. Run your experiments again with N=10, N=100, and N=1000 using random data, mostly-sorted data, and sorted data. Hopefully you will see a huge difference in behavior. This is because merge sort and quick sort are NlogN algorithms on average and insertion sort is N^2. You should also be able to see that quick sort is N^2 in the worst case.

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 random data, mostly-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:

When you have completed all of the steps to this lab:

Enter your FIRST name: | |

Enter your LAST name: | |

Enter your UAID number: |