Insertion sort and Quicksort

This is a discussion on Insertion sort and Quicksort within the C++ Programming forums, part of the General Programming Boards category; Hello everyone. This is my first thread at this forum. I hope you guys can help me! Below I have ...

  1. #1
    Kae
    Kae is offline
    Registered User
    Join Date
    Feb 2006
    Posts
    2

    Question 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

  2. #2
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    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?

  3. #3
    Kae
    Kae is offline
    Registered User
    Join Date
    Feb 2006
    Posts
    2
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 11:43 AM
  2. Quick, Partiotion, and Insertion Sort
    By silicon in forum C++ Programming
    Replies: 0
    Last Post: 05-18-2005, 09:47 PM
  3. Insertion Sort Problem
    By silicon in forum C++ Programming
    Replies: 1
    Last Post: 05-08-2005, 01:30 PM
  4. Using quicksort and radix sort for an anagram program
    By RazielX in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 10:33 AM
  5. the fastest algorthm to order?
    By ^DJ_Link^ in forum C Programming
    Replies: 20
    Last Post: 03-18-2004, 08:00 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21