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