CSCE 2014 - Laboratory Assignment 10

    The purpose of this lab is to evaluate the performance of two well known sorting algorithms: bubble sort and selection sort. We will do this by calculating the cpu times to sort different types of input data (random, mostly-sorted, and sorted) using these two sorting algorithms. As we will see there can be some dramatic differences in performance.

  1. Introduction to Sorting
  2. The purpose of sorting is to put a sequence of data records in ascending or descending order based on a sorting key. For example, to sort student records based on last name, or sort baseball player records based on batting average. The problem of sorting data has been around a long, long time. See the Wikipedia entries for "Hollerith card" and "tabulating machine" for more information.

    There have been dozens of different sorting algorithms invented over the years, each with different advantages and disadvantages. In the next two labs, we will be studying six classic sorting techniques: bubble sort, insertion sort, selection sort, quick sort, merge sort, and bucket sort. These are described in more detail in your text book, and also on the "sorting" Wikipedia page.

  3. Generating Unsorted Data
  4. There are two ways to generate unsorted data for sorting experiments. The first way is to use a random number generator and create N values within a range [L..H]. This is like rolling dice over and over again. The data values in this case will be in random order.

    The second method starts with sorted data and randomly swaps pairs of values in the array. If we do lots of swaps, the array will eventually look like it is in random order. If we only do a small number of swaps, we will have data that is mostly in sorted order.

    These two approaches are used in the code below to initialize an array of integers.

    //------------------------------------------------------------------
    // 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;
       }
    }
    
    //------------------------------------------------------------------
    // Write data array to output file
    //------------------------------------------------------------------
    void write_data(string name, int data[], int count)
    {
       // Open output file
       ofstream dout;
       dout.open(name.c_str());
       if (dout.fail())
          cout << "Error: could not open output file\n";
    
       // Write the data
       dout << count;
       for (int i = 0; i < count; i++)
       {
          if (i % 20 == 0)
    	 dout << endl;
          dout << data[i] << " ";
       }
    
       // Close the file 
       dout.close();
    }
    

    Create a new program in NetBeans and cut and paste the functions "create_random_data", "create_mostly_sorted_data" and "write_data" above into your program. Now create a main program that declares an array of 100 integers, and calls "create_random_data" and "write_data" to create a data file "random.txt" with random values between 0 and 99. If you look at this file, it should look almost as unsorted as possible.

    Now extend your main program to call the "create_mostly_sorted_data" function on an array of 100 integers to create the file "mostly_sorted.txt". Try a few different values of the "swaps" parameter to see what happens and choose a value that creates data that looks mostly sorted (some sequences of values are in the correct order, but others are out of order).

    Cut and paste your main program below:

    Cut and paste one of your mostly sorted results below:

  5. Comparing Bubble Sort and Selection Sort
  6. Cut and paste the functions "bubble_sort" and "selection_sort" below into your program.

    //-----------------------------------------------------------------
    // Bubble sort algorithm
    //-----------------------------------------------------------------
    void bubble_sort(int data[], int count)
    {
       int pass = 1;
       int exchange = 1;
    
       // Bubble largest value to the right N times
       while ((pass < count) && (exchange > 0))
       {
          // Scan unsorted part of data array
          exchange = 0;
          for (int index = 0; index < count - pass; index++)
          {
    	 // Swap two data values if out of order
    	 if (data[index] > data[index + 1])
    	 {
    	    int temp = data[index];
    	    data[index] = data[index + 1];
    	    data[index + 1] = temp;
    	    exchange++;
    	 }
          }
          pass++;
       }
    }
    
    //---------------------------------------------------------------
    // Selection sort algorithm
    //---------------------------------------------------------------
    void selection_sort(int data[], int low, int high)
    {
       // Put largest unsorted value at end of sorted list
       for (int last = high; last > low; last--)
       {
          // Find index of largest value in unsorted array
          int largest = low;
          for (int index = low + 1; index <= last; index++)
    	 if (data[index] > data[largest])
    	    largest = index;
    
          // Swap with last element in unsorted array
          int temp = data[last];
          data[last] = data[largest];
          data[largest] = temp;
       }
    }
    

    Now we are ready to do some experiments to compare the speed of these two sorting algorithms. Your next task is to modify your main program to calculate the CPU times for the following tasks:

    Use the code below to measure the CPU time. Calculate the run times for N=1000. If the CPU times are too small to measure, increase N as needed until you can get a CPU time greater than a few seconds. Stop your program if it uses more than a minute of CPU time and decrease N accordingly.

       // Get start time
       clock_t time1=clock();
    
       // Some chunk of code
    
       // Get end time
       clock_t time2=clock();
       double run_time = (time2-time1)/(double)CLOCKS_PER_SEC;
       cout << "Run time: " << run_time << " seconds\n";
    

    Cut and paste your modified main program below:

    Enter the results of your six timing experiments below:

  7. Submit Work
  8. When you have completed all of the steps to this lab:

    Enter your FIRST name:
    Enter your LAST name:
    Enter your UAID number: