Reference no: EM132278164

Consider the following sorting algorithm, called Monkey Sort:

void MonkeySort(int *theArray, int n) {

bool sorted = false;

while(sorted == false) {

for( int i = 0; i < n; i++) {

index = (rand() % (n - 1));

tmp = theArray[i];

theArray[i] = theArray[index];

theArray[index] = tmp;

}

sorted = true;

for( int i = 0; i < n - 1; i++) {

if(theArray[i] >= theArray[i + 1]) {

sorted = false;

break;

}

}

}

}

Derive the theoretical best, average, and worst case performance bounds of the MonkeySort algorithm. The way you prove the answer is more important than the answer here.