dont use getcomptence in dksorting alg only use it for debugging purposes use getBelief

Each object in the array has a competence rating in the range of 0 to 100, and your goal is to sort these objects in order of increasing competence. However, your challenge is that the comparator function for these objects is unreliable in a way consistent with the Dunning-Kruger effecteach object holds a belief about its own competence that it compares against anothers competence to determine whether it is more or less competent than the other. When making this comparison, each object compares its belief value with the other objects true competence. Objects are only unreliable in evaluating themselves.

As an example, suppose that object a has competence 20 and believed competence of 40 and object b has competence 25 and belief 35. Object a would report that it is more competent than b, since its perceived competence of 40 is more than 25, while object b would report that it is more competent than a since 35 > 20. Since these two disagree on who is more competent,you would need to use information from other objects comparisons in order to determine the correct order between a and b.

You may assume that all of the following are true about the beliefs of these objects:

1. Objects with competence of at least 25 and less than 90 will have belief equal to their competence.

2. Objects with competence less than 25 will overestimate their competence.

3. Such objects will overestimate their competence by at least 1 but will not believe their competence to be 90 or more.

4. Below 25, objects with lower competence will have a higher belief in their competence. (In other words, competence and belief are negatively correlated in low performers.)

5. Objects with competence of 90 or more will underestimate their competence.

6. Such objects will underestimate their competence by at least 1, though they will never believe their competence to be less than 25.

7. At or above 90, objects with higher competence will have higher belief in their competence. (Competence and belief are positively correlated in high performers.)

8. If any two objects agree that one is more competent than the other, they are both correct.

For the sake of simplicity, you may also assume that no two elements have exactly the same competence values

You have been provided with C++ code containing a main function, a scoring function, and two implementations of the Subject class to test your proposed sorting algorithms. Outside of changing a few constants, you should not need to modify any of these files, though their functions and purpose are described here, so that you understand the environment in which your algorithm is being executed

complete the file named sort.cpp that implements the function void dksort(Subject* arr, int n) which sorts an array of n objects based on their comparator functions.Your submission may also include any helper functions required to implement dksort

driver.cpp

#include "dunningkruger.h" #include "sort.h"

#include #include #include using namespace std;

#define CLASS_TO_TEST SlightlyOff const int POP_SIZE = 100;

const int NTRIALS = 5; const unsigned int RANDOM_SEED[] = {0xDEADBEEF, 0xC0C0ABEE, 0xFEEDFACE, 0xDEBEDDED, 0xABEADED1};

int main() { clock_t start, end, timesum; int n; double scoresum; Subject* arr;

n = POP_SIZE;

arr = new CLASS_TO_TEST[n]; for (int i = 0; i < n; i++) arr[i].setCompetence(100.0 * i / n);

shuffle(arr, n);

scoresum = 0; timesum = 0; for (int i = 0; i < NTRIALS; i++) { cout << "Trial " << i + 1 << endl; srand(RANDOM_SEED[i]); shuffle(arr, n);

start = clock(); dksort(arr, n); end = clock();

scoresum += score(arr, n); timesum += end - start; } cout << "Average score: " << scoresum / NTRIALS << endl; cout << "Average time: " << (double) timesum / NTRIALS / CLOCKS_PER_SEC << " seconds" << endl;

delete[] arr;

return 0; }

dunnningkruger.cpp

#include "dunningkruger.h"

#include #include using namespace std;

Subject::Subject() { competence = -1; }

Subject::Subject(double comp) { competence = -1; setCompetence(comp); }

void Subject::setCompetence(double comp) { if (competence != -1) return;

competence = comp; if (competence < 0) competence = 0; else if (competence > 100) competence = 100; }

double Subject::getCompetence() const { return competence; }

bool Subject::considersThemselfBetterThan(const Subject& oth) const { return getBelief() > oth.competence; }

double Subject::getBelief() const { return competence; }

double SlightlyOff::getBelief() const { double belief = competence;

//Illusory superiority if (competence < LOW_COMPETENCE) belief = 1.01 * LOW_COMPETENCE - 0.01 * competence + 1.5;

//Illusory inferiority if (competence >= HI_COMPETENCE) belief = belief - 1.5;

return belief; }

double Delusional::getBelief() const { double belief = competence;

//Illusory superiority if (competence < LOW_COMPETENCE) belief = 3 * LOW_COMPETENCE - 2 * competence + 5.5;

//Illusory inferiority if (competence >= HI_COMPETENCE) belief = competence / 2 + LOW_COMPETENCE - 0.25;

return belief; }

bool Subject::operator<(const Subject& oth) const { return !considersThemselfBetterThan(oth); }

bool Subject::operator>(const Subject& oth) const { return considersThemselfBetterThan(oth); }

inline void swap(Subject& a, Subject& b) { double t = a.competence; a.competence = b.competence; b.competence = t; }

void shuffle(Subject* arr, int n) { for (int i = n-1; i >= 0; i--) { int idx = rand() % (i+1); swap(arr[i], arr[idx]); } }

double normcdf(double x) { static const double a1 = 0.254829592; static const double a2 = -0.284496736; static const double a3 = 1.421413741; static const double a4 = -1.453152027; static const double a5 = 1.061405429; static const double p = 0.3275911;

x /= sqrt(2.0);

// A&S formula 7.1.26 double t = 1.0 / (1.0 + p*x); double y = 1.0 - (((((a5*t + a4)*t) + a3)*t + a2)*t + a1)*t*exp(-x*x);

return 0.5*(1.0 + y); }

double score(Subject* arr, int n) { unsigned long long count = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (arr[i].competence >= arr[j].competence) count++;

return 2 - 2*normcdf(count * 6.0 / n / (n+1)); }

dunnningkruger.h

#pragma once

const double LOW_COMPETENCE = 25.0; const double HI_COMPETENCE = 90.0;

class Subject { friend double score(Subject* arr, int n); friend void swap(Subject& a, Subject& b); protected: double competence; virtual double getBelief() const; public: Subject(); Subject(double comp); void setCompetence(double comp); double getCompetence() const; bool considersThemselfBetterThan(const Subject& oth) const; bool operator<(const Subject& oth) const; bool operator>(const Subject& oth) const; };

class SlightlyOff : public Subject { private: virtual double getBelief() const; };

class Delusional : public Subject { private: virtual double getBelief() const; };

void swap(Subject& a, Subject& b); void shuffle(Subject* arr, int n); double score(Subject* arr, int n);

sort.h

#pragma once

#include "dunningkruger.h"

void dksort(Subject* arr, int n);

sort.cpp

//needs to be implemented

// can use getCompetence for debugging purposed but the alg should sort the value by there beilef

//use SlightlyOff and Delusional to access there getBeilef

// the dksort algorithm should not need getComptence to preform correctly only used for debugging to peek at a targets acually comptence instead of there beilef

makefile

CC=g++

CFLAGS=-std=c++11

INC=

LIB=

all: dksort

dksort: driver.o dunningkruger.o sort.o

$(CC) $(CFLAGS) -o $@ $^ $(LIB)

.cpp.o:

$(CC) $(CFLAGS) $(INC) -c -o $@ $^

clean:

rm -f *.o dksort