I am working on a project that asks us to implement different sorts and add counter variables to measure the runtime with different array sizes.
**My problem is that the output is not the same as the expected output**
I already completed the insertion sort and correctly counts the number of comparisons.
I am allowed to use reference parameter.
Any feedback is appreciated

**What I have tried:**
Output:

Array Size: 10 100 1000 10000
--------------------------------------------------------------------
Quick sort 16 384 6401 74378

Expected Output:

Array Size: 10 100 1000 10000
--------------------------------------------------------------------
Quick Sort 35 630 10292 132882

Whats inside the contents of the array for array size 10

The contents stay Constant with the used seed.

Insertion sort

[ 935, 942, 697, 299, 382, 579, 408, 181, 366, 505 ]
[ 181, 299, 366, 382, 408, 505, 579, 697, 935, 942 ]

#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <cmath>
static const int MIN_SIZE = 10;
template<class ItemType>
int insertionSort(ItemType theArray[], int first, int last) {
int count = 0;
for (int unsorted = first + 1; unsorted <= last; unsorted++) {
ItemType nextItem = theArray[unsorted];
int loc = unsorted;
while ((loc > first) && (count++,theArray[loc - 1] > nextItem)) {
theArray[loc] = theArray[loc - 1];
loc--;
}
theArray[loc] = nextItem;
}
return count;
}
template<class ItemType>
void order(ItemType theArray[], int i, int j) {
if (theArray[i] > theArray[j]) {
std::swap(theArray[i], theArray[j]);
}
}
template<class ItemType>
int sortFirstMiddleLast(ItemType theArray[], int first, int last) {
int mid = first + (last - first) / 2;
order(theArray, first, mid); order(theArray, mid, last); order(theArray, first, mid);
return mid;
}
template<class ItemType>
int partition(ItemType theArray[], int first, int last,int &counter) {
int pivotIndex = sortFirstMiddleLast(theArray, first, last);
std::swap(theArray[pivotIndex], theArray[last - 1]);
pivotIndex = last - 1;
ItemType pivot = theArray[pivotIndex];
int indexFromLeft = first + 1;
int indexFromRight = last - 2;
bool done = false;
while (!done) {
while (theArray[indexFromLeft] < pivot) {
counter++; indexFromLeft = indexFromLeft + 1;
}
while (theArray[indexFromRight] > pivot) {
counter++;
indexFromRight = indexFromRight - 1;
}
if (indexFromLeft < indexFromRight) {
std::swap(theArray[indexFromLeft], theArray[indexFromRight]);
indexFromLeft = indexFromLeft + 1;
indexFromRight = indexFromRight - 1;
}
else {
done = true;
}
}
std::swap(theArray[pivotIndex], theArray[indexFromLeft]);
pivotIndex = indexFromLeft;
return pivotIndex;
}
template<class ItemType>
int quicksort(ItemType theArray[], int first, int last) {
int result = 0;
int counter = 0;
if (last - first + 1 < MIN_SIZE) {
result = insertionSort(theArray, first, last);
}
else {
int pivotIndex = partition(theArray, first, last,counter);
result += quicksort(theArray, first, pivotIndex - 1);
result += quicksort(theArray, pivotIndex + 1, last);
result += counter;
}
return result; }
int* makeRandomArray(int n, int seed) {
srand(seed);
int * a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = rand() % 1000;
}
return a;
}
int main(){
const int seed = 9000;
int *a;
std::cout << "Quick sort";
int n = 10;
a = makeRandomArray(10, seed);
std::cout <<std::setw(13)<< quicksort(a, 0, n-1);
delete[] a;
n = 100;
a = makeRandomArray(100, seed);
std::cout <<std::setw(13)<< quicksort(a, 0, n-1);
delete[] a;
n = 1000;
a = makeRandomArray(1000, seed);
std::cout <<std::setw(13)<< quicksort(a, 0, n-1);
delete[] a;
n = 10000;
a = makeRandomArray(10000, seed);
std::cout <<std::setw(13)<< quicksort(a, 0, n-1)<<std::endl;
delete[] a;
return 0;
}

tip: use longer variables names to make code better readable.

The missing 2 line of header?

Or count not being the expected values?