Click here to Skip to main content
15,030,701 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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 ] //unsorted
[ 181, 299, 366, 382, 408, 505, 579, 697, 935, 942 ] //sorted

C++
#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <cmath>
      /******************************/
      /* Start of Quick Sort Algorithm */
      /******************************/



static const int MIN_SIZE  = 10; // Smallest size of an array that quicksort will sort

/**
 * Sorts the items in an array into ascending order.
 */
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;
}

/**
 * Arranges two specified array entries into sorted order by
 * exchanging them, if necessary.
 * */
template<class ItemType>
void order(ItemType theArray[], int i, int j) {
    if (theArray[i] > theArray[j]) {
        std::swap(theArray[i], theArray[j]);
    }
}

/**
 * Arranges the first, middle, and last entry in an array in sorted order.
 */
template<class ItemType>
int sortFirstMiddleLast(ItemType theArray[], int first, int last) {
    int mid = first + (last - first) / 2;
    order(theArray, first, mid); // Make theArray[first] <= theArray[mid]
    order(theArray, mid, last);  // Make theArray[mid] <= theArray[last]
    order(theArray, first, mid); // Make theArray[first] <= theArray[mid]

    return mid;
}

/**
 * Partitions the entries in an array about a pivot entry for quicksort.
 */
template<class ItemType>
int partition(ItemType theArray[], int first, int last,int &counter) {
    // Choose pivot using median-of-three selection
    int pivotIndex = sortFirstMiddleLast(theArray, first, last);

    // Reposition pivot so it is last in the array
    std::swap(theArray[pivotIndex], theArray[last - 1]);
    pivotIndex = last - 1;
    ItemType pivot = theArray[pivotIndex];

    // Determine the regions S1 and S2
    int indexFromLeft = first + 1;
    int indexFromRight = last - 2;

    bool done = false;
    while (!done) {
        // Locate first entry on left that is >= pivot
        while (theArray[indexFromLeft] < pivot) {
          counter++;//I incremented Count here
          indexFromLeft = indexFromLeft + 1;
        }

        // Locate first entry on right that is <= pivot
        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;
        }
    }

    // Place pivot in proper position between S1 and S2, and mark its new location
    std::swap(theArray[pivotIndex], theArray[indexFromLeft]);
    pivotIndex = indexFromLeft;

    return pivotIndex;
}

/**
 * Sorts an array into ascending order. Uses the quick sort with
 * median-of-three pivot selection for arrays of at least MIN_SIZE
 * entries, and uses the insertion sort for other arrays.
 */
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 {
        // Create the partition: S1 | Pivot | S2
        int pivotIndex = partition(theArray, first, last,counter);
        // Sort subarrays S1 and S2
         result += quicksort(theArray, first, pivotIndex - 1);
         result += quicksort(theArray, pivotIndex + 1, last);
         result += counter;
    }
    return result; //return final count
}


      /******************************/
      /* Start of Sorting Benchmark  */
      /******************************/
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;

    /******************************/
    /* Start of Quick Sort    */
    /******************************/
    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;
}
Posted
Updated 19-Apr-21 8:47am
v4
Comments
KarstenK 19-Apr-21 13:25pm
   
The question isnt clear. Write a check function which verifies the sorted array for correctness.

tip: use longer variables names to make code better readable.
Szizzle 2 19-Apr-21 13:28pm
   
Ok updated it
Patrice T 19-Apr-21 13:28pm
   
What is the problem ?
The missing 2 line of header?
Or count not being the expected values?
Szizzle 2 19-Apr-21 13:29pm
   
My current output is not the same as the expected or "Solution" output. Just need suggestions on what is the reason for that.
Szizzle 2 19-Apr-21 13:30pm
   
yes, count not being the expected values

1 solution

Quote:
yes, count not being the expected values

The trick is that the algorithm is sensitive to data, Counts will change with every different dataset. The efficiency of your code matters too.
The fact that your data is correctly sorted is an indication that your code works correctly.
I am not sure switching to insertion sort on small array is part of quick sort. This is kind of change that change counts.
   
v2
Comments
Szizzle 2 19-Apr-21 14:14pm
   
The data stays constant with the seed, which can be seen in the makerandomarray, however changing the "seed" number will produce a different result and different array contents.
Szizzle 2 19-Apr-21 14:16pm
   
That result = insertionsort is provided by my instructor
Patrice T 19-Apr-21 14:25pm
   
2 possibilities
- either your code do not count everything.
- either your instructor's code is not efficient.
Szizzle 2 19-Apr-21 14:29pm
   
Maybe its that, I just placed counter in the 2 most logical areas. Inside those 2 while loops. Maybe theres more?
jeron1 19-Apr-21 14:25pm
   
Stepping through it (for the 10 entry case) yields no clues?
Szizzle 2 19-Apr-21 14:46pm
   
are you running it through a debugger?
jeron1 19-Apr-21 15:10pm
   
It was a question, along the lines of have you stepped through it using a debugger?
Szizzle 2 19-Apr-21 15:17pm
   
oh no, I havent But I'm wondering if its a problem with my insertion...
jeron1 19-Apr-21 15:34pm
   
Perhaps a good time to try?
CPallini 20-Apr-21 1:59am
   
5.
Patrice T 20-Apr-21 2:07am
   
Thank you

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900