SORTS

[KENnIG1591]

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.

[KENnIG1591]

#include <iostream>
#include <iomanip>
#include <random>
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<<msg;
  for (int i{}; i<size; ++i)
    cout << setw(2) << array[i]; // assumes small numbers
  cout << endl;
}

// Useful to verify that array is really sorted!
bool verifySorted(int array[], int size) {
  // returns true if array is in ascending order, else false.
  for (int i=0; i<(size-1); ++i)
    if (array[i]>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 <change code>

const string SORT2_NAME {"my sort 2"};
void mySort2(int[], int, bool);    // expected for this lab <change code>

bool linearSearchArray(int [], int, int, int&); // provided
bool binarySearchArray(int [], int, int, int&); // expected for this lab <change code>

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
}

// <add code> 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

[KENnIG1591]

this is the rest of my code

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

[ne555]

> 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