Insertion sort and Quicksort
Hello everyone. This is my first thread at this forum. I hope you guys can help me!
Below I have included the code for both the insertion sort and the quicksort in my C++ program. I need to add counters that will count the number of comparisons and assignments that take place. I need to add additional lines of code (such as: compareQuick++, assignmentQuick++, compareInsertion++, assignmentInsertion++).
I know what to add. I am, however, having trouble finding where exactly they need to be inserted.
Insertion Sort
Code:
void insertionSort(int insertionArray[], int n) {
for (int i = 1, j; i < n; i++) {
int tmp = insertionArray[i];
for (j = i; j > 0 && tmp < insertionArray[j-1]; j--)
insertionArray[j] = insertionArray[j-1];
insertionArray[j] = tmp;
}
}
Quicksort
Code:
void quicksort(int quickArray[], int first, int last) {
int lower = first+1, upper = last;
swap(quickArray[first],quickArray[(first+last)/2]);
int bound = quickArray[first];
while (lower <= upper) {
while (quickArray[lower] < bound)
lower++;
while (bound < quickArray[upper])
upper--;
if (lower < upper)
swap(quickArray[lower++],quickArray[upper--]);
else lower++;
}
swap(quickArray[upper],quickArray[first]);
if (first < upper-1)
quicksort (quickArray,first,upper-1);
if (upper+1 < last)
quicksort (quickArray,upper+1,last);
}
void quicksort(int quickArray[], int n) {
int i, max;
if (n < 2)
return;
for (i = 1, max = 0; i < n; i++)// find the largest
if (quickArray[max] < quickArray[i]) // element and put it
max = i; // at the end of data[];
swap(quickArray[n-1],quickArray[max]); // largest el is now in its
quicksort(quickArray,0,n-2); // final position;
}
Any help would be greatly appreciated.
Thanks,
Kae
