# Insertion sort and Quicksort

• 02-15-2006
Kae
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
• 02-16-2006
7stud
Quote:

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?
• 02-16-2006
Kae
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.