CSCE 2014 - Laboratory Assignment 10

    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.

  1. Algorithm Instrumentation
  2. 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.

  3. Create Sorting Program
  4. 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;
       }
    }
    

  5. Instrumenting Insertion Sort
  6. 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:

  7. Instrumenting Merge Sort and Quick Sort
  8. 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:

  9. Hybrid Sort Algorithm
  10. 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:

  11. Submit Work
  12. 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 UAID number:
    Your website PASSWORD: