CSCE 2014 - Laboratory Assignment 11

    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.

  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 "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;
       }
    }
    

  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 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:

  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. 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:

  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 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:

  11. Submit Work
  12. When you have completed all of the steps to this lab:

    • 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.
    Enter your FIRST name:
    Enter your LAST name:
    Enter your UAID number: