completing the worksheet only

//--------------------------------------------------------------------

//

// Laboratory C, In-lab Exercise 2 sort.cpp

//

// Implementation of a set of sorting routines

//

//--------------------------------------------------------------------

template

void selectionSort ( DT keyList [], int numKeys )

// Selection sort routine. Sorts the first numKeys keys in keyList

// into ascending order.

{

DT temp; // Temporary storage used in swapping

int minPt, // Index of the smallest key in the remaining entries

j, k; // Loop counters

for ( j = 0 ; j

{

minPt = j;

for ( k = j+1 ; k

if ( keyList[k]

minPt = k;

temp = keyList[j];

keyList[j] = keyList[minPt];

keyList[minPt] = temp;

}

}

//--------------------------------------------------------------------

template

void quickSort ( DT keyList [], int numKeys )

// Quicksort routine. Sorts the first numKeys keys in keyList into

// ascending order.

{

quickPartition(keyList,numKeys,0,numKeys-1);

}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template

void quickPartition ( DT keyList [], int numKeys,

int left, int right )

// Recursive partner of the quickSort routine. Partitions the array

// entries between left and right into two subarrays. One subarray

// contains the keys that are less than or equal to splitValue, and

// the other contains the keys that are greater than splitValue.

// Recursively sorts each of these subarrays.

{

DT splitValue, // "Mid" value to use in splitting

temp; // Temporary storage used in swapping

int splitL, // Keys in [left..splitL-1] are

splitR; // Keys in [splitR+1..right] are > splitValue

splitValue = keyList[ ( left + right ) / 2 ];

splitL = left; // Start at left and move toward right

splitR = right; // Start at right and move toward left

do

{

// Go right until key >= splitValue found.

while ( keyList[splitL]

// Go left until key

while ( splitValue

if ( splitL

{

temp = keyList[splitL]; // Swap keys

keyList[splitL] = keyList[splitR]; // at limits

keyList[splitR] = temp;

splitL++; // Continue

splitR--; // partitioning

}

}

while ( splitL

// Sort each subarray.

if ( left

quickPartition(keyList,numKeys,left,splitR);

if ( splitL

quickPartition(keyList,numKeys,splitL,right);

}

//--------------------------------------------------------------------

template

void unknownSort ( DT keyList [], int numKeys )

// Unknown sort routine. Sorts the first numKeys keys in keyList into

// ascending order.

{

DT temp; // Temporary storage used in swapping

int j, k; // Loop counters

for ( j = 0 ; j

for ( k = numKeys-1 ; k > j ; k-- )

if ( keyList[k-1] > keyList[k] )

{

temp = keyList[k];

keyList[k] = keyList[k-1];

keyList[k-1] = temp;

}

}

//--------------------------------------------------------------------

//

// Laboratory C, In-lab Exercise 2 timesort.cpp

//

// Timing program for a set of sorting routines

//

//--------------------------------------------------------------------

// Computes the length of time that it takes to execute a given

// sorting routine on an array containing numKeys integers.

#include

#include

#include // For exit()

#include "timer.h"

#include "sort.h"

using namespace std;

//--------------------------------------------------------------------

// By default Windows XP has a time resolution of about 16 milliseconds

// This is called a quantum. To get 3 significant figures in a measured

// result you will need to ensure that you measure times at least

// 100 times longer than the minimum resolution. Tweak numRepetitions

// until you get a minimum time > 1.6s for 1000 keys.

//Default timing multiplier

const int numRepetitions = 100; // Number of times to repeat each

// search -- several repetitions

// may be needed in order to

// produce a meaningful timing

//Extra timing multipliers

const int SEL_SORT = 17; // Some algorithms are much faster

const int QCK_SORT = 140; // than the others and need an

const int UNK_SORT = 5; // extra boost to produce a reliable

// timing number. These have been tuned

// to produce similar times at 1000 keys.

//--------------------------------------------------------------------

//--------------------------------------------------------------------

int main ()

{

Timer copyTimer, // Timer for array copy

sortTimer; // Timer for sorting routine

int *masterKeyList, // Master array of integer keys

*keyList, // Array of integer keys to be sorted

numKeys, // Number of array entries

j, k; // Loop counters

double timeForCopy, // Time to copy array numRepetitions times

timePerSort; // Time to sort array once

// Get the number of keys.

cout

cin >> numKeys;

// Allocate both arrays of keys.

masterKeyList = new int [numKeys];

keyList = new int [numKeys];

if ( masterKeyList == 0 || keyList == 0 )

{

cout

exit(1);

}

// Initialize the master array of keys.

for ( j = 0 ; j

masterKeyList[j] = rand();

// Compute the time it takes to create numRepetitions copies of

// masterKeyList.

copyTimer.start();

for ( j = 0 ; j

for ( k = 0 ; k

keyList[k] = masterKeyList[k];

copyTimer.stop();

timeForCopy = copyTimer.getElapsedTime();

// Output header

//We're doing science here. Let's set the scientific flag for numerical output

//And set output precision slightly higher than measurement precision

cout

cout

cout

cout

cout

// Selection sort --

// Time numRepetitions calls to the selectionSort routine.

sortTimer.start();

for ( j = 0 ; j

{

for ( k = 0 ; k

keyList[k] = masterKeyList[k];

selectionSort(keyList,numKeys); // Sort key list

}

sortTimer.stop();

timePerSort =

( sortTimer.getElapsedTime() - timeForCopy ) / double(numRepetitions*SEL_SORT);

//Output sample info for Selection sort

cout

// QuickSort --

// Time numRepetitions calls to the quickSort routine.

sortTimer.start();

for ( j = 0 ; j

{

for ( k = 0 ; k

keyList[k] = masterKeyList[k];

quickSort(keyList,numKeys); // Sort key list

}

sortTimer.stop();

timePerSort =

( sortTimer.getElapsedTime() - timeForCopy ) / double(numRepetitions*QCK_SORT);

//Output sample info for QuickSort

cout

// Unknown sort --

// Time numRepetitions calls to the unknownSort routine.

sortTimer.start();

for ( j = 0 ; j

{

for ( k = 0 ; k

keyList[k] = masterKeyList[k];

unknownSort(keyList,numKeys); // Sort key list

}

sortTimer.stop();

timePerSort =

( sortTimer.getElapsedTime() - timeForCopy ) / double(numRepetitions*UNK_SORT);

//Output sample info for Unknown Sort

cout

return 0;

}

Follow the steps outlined in Part 1 and complete the sheet provided here Wor for Part 2 Complete the table by recording the Time per Sort column. You can use the following four sets of (Time per Sort) data to plot the graph. inter the number of keys : 1000 Enter the number of keys : 2000 Time per Sort Type Number of Total Time Sorts (s) Time per Sort(s) 1700 Selection sort QuickSort 14000 unknown sort Press any key to continue 1.628e+00 8.238e-01 6.648e-01 Sort Number of Total Time Sort(s) Type I Sorts 9.576e-84 selection sort! 1700 6.482e+00 5.879e-85 Quicksort 14000 2.930e+00 1.328e-03 unknown sort 500 2.649e-001 Press any key to continue Enter the number of keys: 4008 3.812e-03 1.449e-84 5.296e-63 500 Enter the number of keys : 3960 Time per Sort Time per Sort Type Number of Total Time | Sorts Number of Sorts Total Time (5) Sort(s) Type Sort(s) Selection sort 1700 QuickSort 14800 unknown sort 500 Press any key to continue 1.533e+011 3.398e+601 6.271e-001 9.016-03 Selection sort| 1780 2.426e-64 Quicksort 14800 1.254e-2 unknown sort Press any key to continue. 3.256e-01 5.727e+00 1.455e401] 1.915e-82 4.091e-84 2.918-82 580 Step 2: Complete the following table by recording the Time per Sort of the selectionSort(), quickSort(), and unknownSort() routines for each of the values of numKeys listed in the table. Execution Times of a Set of Sorting Routines Routine Number of Key 1000 election quickSanto o de now) O Step 3: Plot the results below 10 60 Sort Time (10 seconds) 10 Number of Keys in List (NumKeys Step 4: Consider the two routines in the table above with known big O execution times. Which one should run faster? Describe the expected shape of the curve (straight or curved) for both algorithms Step 5: Using the code in the file sort.h and your measured execution times as a basis, what is the execution time(Big O) of the unknownSort() routine. Briefly explain your reasoning behind this estimate. Follow the steps outlined in Part 1 and complete the sheet provided here Wor for Part 2 Complete the table by recording the Time per Sort column. You can use the following four sets of (Time per Sort) data to plot the graph. inter the number of keys : 1000 Enter the number of keys : 2000 Time per Sort Type Number of Total Time Sorts (s) Time per Sort(s) 1700 Selection sort QuickSort 14000 unknown sort Press any key to continue 1.628e+00 8.238e-01 6.648e-01 Sort Number of Total Time Sort(s) Type I Sorts 9.576e-84 selection sort! 1700 6.482e+00 5.879e-85 Quicksort 14000 2.930e+00 1.328e-03 unknown sort 500 2.649e-001 Press any key to continue Enter the number of keys: 4008 3.812e-03 1.449e-84 5.296e-63 500 Enter the number of keys : 3960 Time per Sort Time per Sort Type Number of Total Time | Sorts Number of Sorts Total Time (5) Sort(s) Type Sort(s) Selection sort 1700 QuickSort 14800 unknown sort 500 Press any key to continue 1.533e+011 3.398e+601 6.271e-001 9.016-03 Selection sort| 1780 2.426e-64 Quicksort 14800 1.254e-2 unknown sort Press any key to continue. 3.256e-01 5.727e+00 1.455e401] 1.915e-82 4.091e-84 2.918-82 580 Step 2: Complete the following table by recording the Time per Sort of the selectionSort(), quickSort(), and unknownSort() routines for each of the values of numKeys listed in the table. Execution Times of a Set of Sorting Routines Routine Number of Key 1000 election quickSanto o de now) O Step 3: Plot the results below 10 60 Sort Time (10 seconds) 10 Number of Keys in List (NumKeys Step 4: Consider the two routines in the table above with known big O execution times. Which one should run faster? Describe the expected shape of the curve (straight or curved) for both algorithms Step 5: Using the code in the file sort.h and your measured execution times as a basis, what is the execution time(Big O) of the unknownSort() routine. Briefly explain your reasoning behind this estimate