Question

C++
---------------------------------------------

Do a comparison of a slow sort with Big O(n²) (selection sort, insertion sort, or bubble sort) and one faster sort of Big O(n * log n) (mergesort or quicksort). Count the number of moves (a swap counts as one move). With mergesort, you can count the range of the part of the array you are sorting (i.e. last-first+1). Use the code from the textbook (copy from the lecture notes) and put in an extra reference parameter for the count.

The array needs to be 10,000 items and the number of digits should be 4. Use the srand function to set the seed and rand function to generate the numbers (use the BubbleSort support code from the Examples, chapter 11). For instance:

srand(seed);

for (int x = 0; x < 10000; x++)

    ary[x] = rand() % 10,000;

Would fill the array. Note: do NOT use the "srand(time(NULL)):". You need to recreate the array to be resorted yet again. Note: you can use the sortSupport code on Canvas.

Call the slow sort first, print out the number of moves and the first 10 and last 10 values, fill the array again using the same seed, call the fast sort, and print the number of moves and the first 10 and last 10 values.

The run would look like:

The seed to use is: 39

Bubble sort had 25349145 swaps

The first 10 values: 0 0 0 3 3 6 6 7 7 9

The last 10 values: 9991 9991 9991 9992 9992 9994 9997 9997 9998 9998

Merge sort had 133616 moves

The first 10 values: 0 0 0 3 3 6 6 7 7 9

The last 10 values: 9991 9991 9991 9992 9992 9994 9997 9997 9998 9998
-------------------------------------------------------------------------------------------------------------

#include <cstdlib>
#include <iostream>
#include "sortSupport.h"
#ifndef SORTSUPPORT_CPP
#define SORTSUPPORT_CPP

using namespace std;

// Does seed first
// creates data for the array
template<class ItemType>
void makeArray(ItemType ary[], int max, int seed)
{
        srand(seed);
        for (int index = 0; index < max; index++)
                ary[index] = rand() % MAX_VALUE;
}

// prints the first 10 and last 10 items of an array
template<class ItemType>
void printEnds(ItemType ary[], int max)
{
        cout << "First 10: ";
        for (int index = 0; index < 10; index++)
                cout << ary[index] << " ";
        cout << endl << "Last 10: ";
        for (int index = max - 10; index < max; index++)
                cout << ary[index] << " ";
        cout << endl;
}
#endif
-----------------------------------------------------------------------------

#ifndef SORTSUPPORT_H
#define SORTSUPPORT_H
#include "bubbleSort.h"

const int MAX_VALUE = 10000;
const int MAX_SIZE = 10000;
const int MAX_DIGITS = 4;

template<class ItemType>
void makeArray(ItemType ary[], int max, int seed);

template<class ItemType>
void printEnds(ItemType ary[], int max);

#include "sortSupport.cpp"
#endif
------------------------------------------------------------------------------

#include <iostream>
#include <string>
const int MAX_SIZE = 50;
/** Merges two sorted array segments theArray[first..mid] and 
   theArray[mid+1..last] into one sorted array. 
@pre  first <= mid <= last. The subarrays theArray[first..mid] and    
theArray[mid+1..last] are each sorted in increasing order. 
@post  theArray[first..last] is sorted. 
@param theArray  The given array. 
@param first  The index of the beginning of the first segment in theArray. 
@param mid  The index of the end of the first segment in theArray;   
 mid + 1 marks the beginning of the second segment. 
@param last  The index of the last element in the second segment in theArray. 
@note  This function merges the two subarrays into a temporary    
array and copies the result into the original array theArray. */
template<class ItemType>
void merge(ItemType theArray[], int first, int mid, int last)
{   
ItemType tempArray[MAX_SIZE];  // Temporary array   
// Initialize the local indices to indicate the subarrays  
 int first1 = first;           // Beginning of first subarray   
int last1 = mid;               // End of first subarray  
 int first2 = mid + 1;          // Beginning of second subarray   
int last2 = last;              // End of second subarray   

// While both subarrays are not empty, copy the   
// smaller item into the temporary array  
 int index = first1;            // Next available location in tempArray  
 while ((first1 <= last1) && (first2 <= last2))   
  {      
// At this point, tempArray[first..index-1] is in order      
if (theArray[first1] <= theArray[first2])      
      {         
         tempArray[index] = theArray[first1];         
          first1++;      
       }    
     else     
       {        
        tempArray[index] = theArray[first2];        
         first2++;      
        }  // end if     
  index++;   
   }  // end while   

// Finish off the first subarray, if necessary   
while (first1 <= last1)   
  {      
    // At this point, tempArray[first..index-1] is in order     
  tempArray[index] = theArray[first1];      
  first1++;      
  index++;
   }  // end while  
 // Finish off the second subarray, if necessary   

while (first2 <= last2)   
{      
// At this point, tempArray[first..index-1] is in order      
tempArray[index] = theArray[first2];      
first2++;     
 index++;   
}  // end for   

// Copy the result back into the original array  
 for (index = first; index <= last; index++)      
theArray[index] = tempArray[index];
}  // end merge

/** Sorts the items in an array into ascending order. 
@pre  theArray[first..last] is an array. 
@post  theArray[first..last] is sorted in ascending order. 
@param theArray  The given array. 
@param first  The index of the first element to consider in theArray. 
@param last  The index of the last element to consider in theArray. */

template<class ItemType>
void mergeSort(ItemType theArray[], int first, int last)
{   
if (first < last)   
{      
// Sort each half      
int mid = first + (last - first) / 2; // Index of midpoint      

// Sort left half theArray[first..mid]     
 mergeSort(theArray, first, mid);      

// Sort right half theArray[mid+1..last]      
mergeSort(theArray, mid + 1, last);      

// Merge the two halves     
 merge(theArray, first, mid, last);  
 }  // end if

}  // end mergeSort

int main()
{   
std::string a[6] = {"Z", "X", "R", "K", "F", "B"};  
 mergeSort(a, 0, 5);   
   for (int i = 0; i < 6; i++)      
          std::cout << a[i] << " ";   
  std::cout << std::endl;

}  // end main

/* B F K R X Z  */
 

Answer 1

Comparison of a slow sort with Big O(n²) (selection sort, insertion sort, or bubble sort) and one faster sort of Big O(n * log n) (mergesort or quicksort). Count the number of moves (a swap counts as one move). With mergesort, you can count the range of the part of the array you are sorting (i.e. last-first+1).

Slow Sort Algorithm (Bubble Sort):- Count the number of swaps using code given here:

int bubblesort(int array[], int count) {
    int i, j, temp;
    int swaps = 0; // initialize swap count
    for(i = 0; i < count-1; ++i) {
        for(j=0; j < count-1-i; ++j) {
            if(array[j] > array[j+1]) {
                temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
                swaps++;    // increment swap code after each comparison
            }
        }
    }

    return swaps;
}

Fast Sort Algorithm (Merge Sort): Count the number of moves using code given here:

// C++ program to Count 
// using Merge Sort 
#include <bits/stdc++.h> 
using namespace std; 

int _mergeSort(int arr[], int temp[], int left, int right); 
int merge(int arr[], int temp[], int left, int mid, int right); 

/* This function sorts the input array and returns the number of moves in the array */
int mergeSort(int arr[], int array_size) 
{ 
        int temp[array_size]; 
        return _mergeSort(arr, temp, 0, array_size - 1); 
} 

/* An auxiliary recursive function that sorts the input array and 
returns the number of moves in the array. */
int _mergeSort(int arr[], int temp[], int left, int right) 
{ 
        int mid, moves = 0; 
        if (right > left) { 
                /* Divide the array into two parts and 
                call _mergeSortAndCountInv() 
                for each of the parts */
                mid = (right + left) / 2; 

                /* moves count will be sum of moves in left-part, right-part and number of moves in merging */
                moves += _mergeSort(arr, temp, left, mid); 
                moves += _mergeSort(arr, temp, mid + 1, right); 

                /*Merge the two parts*/
                moves += merge(arr, temp, left, mid + 1, right); 
        } 
        return inv_count; 
} 

/* This funtion merges two sorted arrays and returns moves count in the arrays.*/
int merge(int arr[], int temp[], int left, int mid, int right) 
{ 
        int i, j, k; 
        int moves = 0; 

        i = left; /* i is index for left subarray*/
        j = mid; /* j is index for right subarray*/
        k = left; /* k is index for resultant merged subarray*/
        while ((i <= mid - 1) && (j <= right)) { 
                if (arr[i] <= arr[j]) { 
                        temp[k++] = arr[i++]; 
                } 
                else { 
                        temp[k++] = arr[j++]; 
                        moves = moves + (mid - i); 
                } 
        } 

        /* Copy the remaining elements of left subarray (if there are any) to temp*/
        while (i <= mid - 1) 
                temp[k++] = arr[i++]; 

        /* Copy the remaining elements of right subarray (if there are any) to temp*/
        while (j <= right) 
                temp[k++] = arr[j++]; 

        /*Copy back the merged elements to original array*/
        for (i = left; i <= right; i++) 
                arr[i] = temp[i]; 

        return moves; 
} 

Overall code for the comparison of the sort algorithm is given below:

#include <cstdlib>
#include <iostream>
#include <bits/stdc++.h>  
#include "sortSupport.h"
#ifndef SORTSUPPORT_CPP
#define SORTSUPPORT_CPP 

using namespace std;
int _mergeSort(int arr[], int temp[], int left, int right); 
int merge(int arr[], int temp[], int left, int mid, int right); 

int bubblesort(int array[], int count) {
    int i, j, temp;
    int swaps = 0; // initialize swap count
    for(i = 0; i < count-1; ++i) {
        for(j=0; j < count-1-i; ++j) {
            if(array[j] > array[j+1]) {
                temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
                swaps++;    // increment swap code after each comparison
            }
        }
    }

    return swaps;
}


/* This function sorts the input array and returns the number of moves in the array */
int mergeSort(int arr[], int array_size) 
{ 
        int temp[array_size]; 
        return _mergeSort(arr, temp, 0, array_size - 1); 
} 

/* An auxiliary recursive function that sorts the input array and 
returns the number of moves in the array. */
int _mergeSort(int arr[], int temp[], int left, int right) 
{ 
        int mid, inv_count = 0; 
        if (right > left) { 
                /* Divide the array into two parts and 
                call _mergeSortAndCountInv() 
                for each of the parts */
                mid = (right + left) / 2; 

                /* moves count will be sum of moves in left-part, right-part and number of moves in merging */
                inv_count += _mergeSort(arr, temp, left, mid); 
                inv_count += _mergeSort(arr, temp, mid + 1, right); 

                /*Merge the two parts*/
                inv_count += merge(arr, temp, left, mid + 1, right); 
        } 
        return inv_count; 
} 

/* This funtion merges two sorted arrays and returns moves count in the arrays.*/
int merge(int arr[], int temp[], int left, int mid, int right) 
{ 
        int i, j, k; 
        int inv_count = 0; 

        i = left; /* i is index for left subarray*/
        j = mid; /* j is index for right subarray*/
        k = left; /* k is index for resultant merged subarray*/
        while ((i <= mid - 1) && (j <= right)) { 
                if (arr[i] <= arr[j]) { 
                        temp[k++] = arr[i++]; 
                } 
                else { 
                        temp[k++] = arr[j++]; 
                        inv_count = inv_count + (mid - i); 
                } 
        } 

        /* Copy the remaining elements of left subarray (if there are any) to temp*/
        while (i <= mid - 1) 
                temp[k++] = arr[i++]; 

        /* Copy the remaining elements of right subarray (if there are any) to temp*/
        while (j <= right) 
                temp[k++] = arr[j++]; 

        /*Copy back the merged elements to original array*/
        for (i = left; i <= right; i++) 
                arr[i] = temp[i]; 

        return inv_count; 
} 


// Does seed first
// creates data for the array
template<class ItemType>
void makeArray(ItemType ary[], int max, int seed)
{
        srand(seed);
        for (int index = 0; index < max; index++)
                ary[index] = rand() % MAX_VALUE;
}

// prints the first 10 and last 10 items of an array
template<class ItemType>
void printEnds(ItemType ary[], int max)
{
        cout << "First 10: ";
        for (int index = 0; index < 10; index++)
                cout << ary[index] << " ";
        cout << endl << "Last 10: ";
        for (int index = max - 10; index < max; index++)
                cout << ary[index] << " ";
        cout << endl;
}
#endif

int main(){
      int seed;
      int arr[10000];
      int max=10000;
      cout << "The seed to use is: ";
      cin >> seed;
    
      makeArray(arr,max,seed);

      int bubbleSort_swap = bubblesort(arr,max);

      cout << "Bubble sort had " << bubbleSort_swap << "swaps";
      
      printEnds(arr,max);

      int mergeSort_swap = mergeSort(arr,max);

      cout << "Merge sort had " << bubbleSort_swap << "moves";

      printEnds(arr,max);
}