Thread: 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

I know what to add. I am, however, having trouble finding where exactly they need to be inserted.

So, is it safe to say that you didn't write either of those functions?

Well, the algorithms were in one of my textbooks and I wrote the functions from them. In case you're curious, I did add code for the comparisons and assignments, but the numbers that are being generated are just barely different than the ones I am manually coming up with.