### SORTS

Can someone help me with the last part of my code?
I need help with sorts. There must be 3 total but 1 has to be a working sort algorithm (selection sort) and the second one has to be a working search algorithm (linear search).

Assignment instructions:
Provide a verbose=true (or false) option to your sort functions. If verbose is false, sort the array silently. if verbose is true, display a step-by-step description of what the sort algorithm is doing. In your program, you start by testing on a very small array, using verbose=true. That will display the sorting steps as they occur. Later, on a large array, verbose=false, so no output is displayed. *See selectionSort to see how the verbose flag is used.*

You will modify my sort 1 and my sort 2, which initially don’t sort.

Next, measure the performance of your algorithms and find out which is best. Performance measuring code is provided. The sorting algorithm sorts increasingly large portions of bigArray. For large arrays, the verbose flag is false to prevent output.

For small data sizes, the time will be 0 milliseconds. To get a useful duration, it works better if it runs for at least 1/4 second (250 milliseconds). Two ways to get an algorithm to run longer: 1) increase the data size; 2) place a loop around the algorithm, so it runs many times. For example, perform a search 1000 times in a loop, and divide the duration by 1000.0 to get the milliseconds for one iteration.
Performance testing code is provided. It will test on multiple different array sizes. Try to keep the maximum execution time under a minute. Arrays of size: 1000, 2000, 4000, 8000, 16000, up to 64000 are provided. Include the performance results of your experimentation here. Example (for each entry, there is some number, in milliseconds):
 Algorithm 1000 2000 4000 8000 16000 32000 ... (Array size) ---------- ----- ----- ----- ----- ----- ------ ------ sort1 x xx xxx xxxx xxxxx xxxxxx sort2 y yy yyy yyyy yyyyy yyyyyy sort3 z zz zzz zzzz zzzzz yyyyyy search1 m mm mmm mmmm mmmmm mmmmmm search2 n nn nnn nnnn nnnnn nnnnnn

Observe: As the size of the array increases, the duration increases, but by how much?    Code for automating the performance testing of the algorithms is included. Read the code to understand how to performance test your own search and sort algorithms. Very short run-times (fast algorithms, small data) may register as 0 time, which is under 1 millisecond (1/1000th of a second). That could be OK. Some algorithms are very fast.
Extra credit option 1: (up to 10%) add yet another sort. Use good variable names, comments and verbose sorting steps to prove that you fully understand it. quick sort is a good choice, but there are many others.
 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162`` ``````#include #include #include using namespace std; const int BIGSIZE = 64000; int bigArray[BIGSIZE]; const int testSizes[] = {1000, 2000, 4000, 8000, 16000, 32000, BIGSIZE, 0}; // 0 is a sentinel // All numbers inside testSizes MUST BE less than or equal to BIGSIZE const int TARGET = 123456789; // TARGET is uses as a number to search for. // array helper functions: void showArray(int array[], int size, const string &msg="") { // displays every element in array cout<array[i+1]) return false; return true; } int unorderedCount(int array[], int size) { int unsorted_adjacent_pairs{}; for (int i=0; i<(size-1); ++i) if (array[i]>array[i+1]) ++unsorted_adjacent_pairs; return unsorted_adjacent_pairs; } const int AlgorithmNameMaxWidth=16; // maximum column width to display algorithm names const int TestSizeWidth=12; // maximum column width to display time to run algorithms const int DurationWidth=TestSizeWidth; const string SELECTION_SORT_NAME{"selection sort"}; void selectionSortConcise(int[], int); // from internet, not called void selectionSortTextBook(int[], int); // from our textbook, not called void selectionSort(int[], int, bool); // as expected for this lab const string SORT1_NAME {"my sort 1"}; void mySort1(int[], int, bool); // expected for this lab const string SORT2_NAME {"my sort 2"}; void mySort2(int[], int, bool); // expected for this lab bool linearSearchArray(int [], int, int, int&); // provided bool binarySearchArray(int [], int, int, int&); // expected for this lab float testSortAlgorithm1x(void sortAlgorithm(int [], int, bool), int array[], int arraySize, bool verbose=false) { for (int index = 0; index < arraySize; index++) array[index] = rand(); // initialize array with random values int startTime = clock(); // get the start time, in milliseconds sortAlgorithm(array, arraySize, verbose); // ALGORITHM UNDER TEST int stopTime = clock(); // get the stop time, in milliseconds float duration = stopTime - startTime; int unordered_pairs = unorderedCount(array, arraySize); if (unordered_pairs != 0) return -unordered_pairs; // return a negative count of unordered pairs to indicate sort failure else return duration; } void testSortAlgorithmNx(void sortAlgorithm(int [], int, bool), string sortName, int array[], int arraySize, bool verbose=false) { cout << endl << setw (AlgorithmNameMaxWidth) << left << sortName; for (int testCount=0; (testSizes[testCount] && testSizes[testCount] <= arraySize); ++testCount) cout << setw(DurationWidth) << right << testSortAlgorithm1x(sortAlgorithm, array, testSizes[testCount]); } float testLinearSearch(int array[], int arraySize, int retry=1000) { bool found = false; // true if TARGET is found in array int foundAt = -1; // index in array where TARGET was found int startTime = clock(); for (int repeat = 0; repeat < retry; ++repeat) // repeat test 1000 times to increase duration found = linearSearchArray(array, arraySize, TARGET, foundAt); // ALGORITHM UNDER TEST int stopTime = clock(); float duration = stopTime - startTime; return duration/retry; // divide duration by 1000 to get time for single search } // to test binary search. It works like testLinearSearch float testBinarySearch(int array[], int arraySize, int retry=1000) { return 0.0; } void testAlgorithms(int array[], int arraySize, bool verbose=false) { cout << setw (AlgorithmNameMaxWidth) << left << "Algorithm"; for (int testCount=0; testSizes[testCount]; ++testCount) cout << setw(TestSizeWidth) << right << testSizes[testCount]; cout << endl << string(AlgorithmNameMaxWidth, '='); for (int testCount=0; testSizes[testCount]; ++testCount) cout << setw(DurationWidth) << right << " ======="; testSortAlgorithmNx(selectionSort, SELECTION_SORT_NAME, array, arraySize); // provided testSortAlgorithmNx(mySort1, SORT1_NAME, array, arraySize); testSortAlgorithmNx(mySort2, SORT2_NAME, array, arraySize); cout<<"\n--------"; // separator between sort algorithms and search algorithms cout << endl << setw (AlgorithmNameMaxWidth) << left << "linear search"; for (int testCount=0; (testSizes[testCount] && testSizes[testCount] <= arraySize); ++testCount) cout << setw(DurationWidth) << right << testLinearSearch(array, testSizes[testCount]); cout << endl << setw (AlgorithmNameMaxWidth) << left << "binary search"; for (int testCount=0; (testSizes[testCount] && testSizes[testCount] <= arraySize); ++testCount) cout << setw(DurationWidth) << right << testBinarySearch(array, testSizes[testCount]); cout << endl; } void testSortOnSmallArray(void sortAlgorithm(int [], int, bool), string sortName) { int smallArray[] {7, 9, 3, 1, 8, 6, 2}; // for testing purposes const int SMALLSIZE = sizeof(smallArray)/sizeof(smallArray[0]); showArray(smallArray, SMALLSIZE, sortName + " start: smallArray is: "); sortAlgorithm(smallArray, SMALLSIZE, true); // true means verbose, show details showArray(smallArray, SMALLSIZE, sortName + " stop: smallArray is: "); cout << ((verifySorted(smallArray, SMALLSIZE)) ? "Verified: smallArray is sorted.\n\n" : "Oops!!!: smallArray is NOT sorted.\n\n"); } int main () { srand(time(0)); // seed the random number generator only once. cout << "Test sorting algorithms on small array:\n\n"; testSortOnSmallArray(selectionSort, SELECTION_SORT_NAME); testSortOnSmallArray(mySort1, SORT1_NAME); testSortOnSmallArray(mySort2, SORT2_NAME); float duration = 0.0; // time in milliseconds duration = testSortAlgorithm1x(selectionSort, bigArray, BIGSIZE); cout << fixed << setprecision(2); cout << "\nSelection sort on bigArray took: " << setw(7) << duration << " milliseconds." << endl; duration = testLinearSearch(bigArray, BIGSIZE); cout << "Linear search of bigArray took: " << setw(7) << duration << " milliseconds.\n\n"; testAlgorithms(bigArray, BIGSIZE); return 0; } // end of main ``````
this is the rest of my code
 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182`` ``````void mySort1(int array[], int size, bool verbose=false) { if (verbose) { cout << " "<< SORT1_NAME <<" has not been implemented.\n"; // replace when implemented } } void mySort2(int array[], int size, bool verbose=false) { if (verbose) { cout << " "<< SORT2_NAME <<" has not been implemented.\n"; // replace when implemented } } bool linearSearchArray(int array[], int size, int target, int &position) { for (int i = 0; i < size; ++i) if (array[i] == target) // found it! {position=i; return true;} position = -1; return false; } bool binarySearchArray(int array[], int size, int target, int &position) { } void selectionSortConcise(int array[], int size) { int i, idx, val; for (i = 0; i < (size - 1); i++) { idx = i; val = array[i]; for (int j = i + 1; j < size; j++) { if (array[j] < val) { val = array[j]; idx = j; } } array[idx] = array[i]; array[i] = val; } } void selectionSortTextbook(int array[], int size) { int startScan, minIndex, minValue; for (startScan = 0; startScan < (size - 1); startScan++) { minIndex = startScan; minValue = array[startScan]; for (int index = startScan + 1; index < size; index++) { if (array[index] < minValue) { minValue = array[index]; minIndex = index; } } array[minIndex] = array[startScan]; array[startScan] = minValue; } } void selectionSort(int array[], int size, bool verbose=false) { int minIndexSoFar = 0, minValueSoFar{array[0]}; for (int unsortedIndex = 0; unsortedIndex < (size - 1); unsortedIndex++) { minIndexSoFar = unsortedIndex; minValueSoFar = array[unsortedIndex]; for (int seekMinIndex = unsortedIndex + 1; seekMinIndex < size; seekMinIndex++) { if (array[seekMinIndex] < minValueSoFar) { if (verbose) cout << " prev min in array[" << minIndexSoFar << "]=" << minValueSoFar; minValueSoFar = array[seekMinIndex]; minIndexSoFar = seekMinIndex; if (verbose) cout << "; new min in array[" << minIndexSoFar << "]=" << minValueSoFar << endl; } } if (verbose) { cout << " swap left in array[" << unsortedIndex << "]=" << array[unsortedIndex]; cout << " with min in array[" << minIndexSoFar << "]=" << array[minIndexSoFar] << endl; } array[minIndexSoFar] = array[unsortedIndex]; array[unsortedIndex] = minValueSoFar; if (verbose) { cout << "After pass " << unsortedIndex << " the array is: "; showArray(array, size); cout << endl; } // ... continue seeking the minimum value in the smaller remaining portion. } }``````
> Can someone help me with the last part of my code?
¿what's the last part and what help do you need?
it looks like you've just copy-pasted your wall-of-text assignment

> if verbose is true, display a step-by-step description of what the sort algorithm is doing.
noise
Topic archived. No new replies allowed.