-1
\$\begingroup\$

Unfortunately, my earlier question was put on hold due to "code that doesn't work", but I realised that there were holes in my question, so here it is again, revamped.

You probably know the QuickSort algorithm, where you select a pivot and place elements lower than it on one side, and those bigger than it on the other. I have successfully implemented the QuickSort algorithm - using the first element of the given array as the pivot as well as using the last element (which can just be done by swapping the first and last element).

However, I am stuck on the last case, which involves using the median of three. This is where you get the array, compare the first element, the last element, and the middle element (not the median, but the element in the middle of the unsorted array). You compare these three elements, and select the one which is between the others to be the pivot.
E.g., given the array: {7, 5, 1, 6, 3, 4, 2, 8, 9},
you compare the 1st, middle and last element, which is 7, 3 and 9 respectively.
Of these three elements, the number 3 is the median, thus you choose that to be your pivot. What about an array with even length, 2k? Well, you just choose the kth element. So, in the array {1, 2, 3, 4} the middle is 2.

That out of the way, lets get to the real problem: In quicksort, you compare the pivot element to all other elements - with an array of size k, there are k-1 comparisons. My job is to count the number of comparisons that is done by the median of three quicksort algorithm. This can be easily done, by adding k-1 as above, every-time quicksort is called.

As mentioned prior, I am able to count the number of comparisons, when using the first element as the pivot, and the second element as the pivot, but I am stuck with the median of three case.
Before I show the code, I will clarify how I tested my code. This programming problem is from an online course I am doing, and they have some inputs you can test your code on to check its correctness, here they are10 number input, 100 number input and 1000 number input.

The answers should be:

input   choice of pivot
 size  first  last median
   10     25    29    21
  100    615   587   518
 1000  10297 10184  8921

Here is my C implementation of QuickSort with the median of three rule:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
// using last element as pivot now

//the size of the input, change for the test case you are testing
#define TOTAL_NUM 100

//the location of the input file, you may have to change this for your own use
#define DATA_FILE "C:\\Users\\HSJJ\\Desktop\\Jainil's Programs\\QuickSort_median_pivot\\QuickSort.txt"

int array[TOTAL_NUM] = {0};
int Partition(int *array, int l, int r);
int QuickSort(int *array, int l, int r);

int comparisons = 1;

void swap(int *array, int index1, int index2)
{
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}

int read_file_to_array(char *file_name, int *array, int len)
{
    FILE *fp = NULL;
    int i;
    fp = fopen(file_name, "r");
    if(fp == NULL)
        return -1;
    for(i = 0; i < len; i++)
        fscanf(fp, "%d",&array[i]);
    fclose(fp);
    return 0;
}

int Partition(int *array, int l, int r)
{
    //int middle = l + ((r - l + 1)  / 2) - 1;
    int n = r - l;
    int middle = ((n - (n % 2)) / 2) + l;
    //int middle = (r + l)/2;

    // order left and middle value
    if(array[l] > array[middle]) {
        swap(array, l, middle);
    }
    // order left and right values
    if(array[l] > array[r]) {
        swap(array, l, r);
    }
    // order middle and right values
    if(array[middle] > array[r]) {
        swap(array, middle, r);
    }
    swap(array, l, middle);
    int p = array[l];
    int i = l + 1;
    int end = 0;
    int j;
    for (j = l + 1; j <= r; j++)
    {
        if (array[j] < p){
            int k = array[j];
            array[j] = array[i];
            array[i] = k;
            i++;
        }
        end = j;
    }
    //swap A[l] and A[i-1]
    int a = array[l];
    array[l] = array[i-1];
    array[i-1] = a;
    QuickSort(array, l, i - 2);
    QuickSort(array, i, end);
}

int QuickSort(int *array, int l, int r)
{
    if (l < r)
    {
        Partition(array, l, r);
        comparisons = comparisons + (r - l);
    }
    else
    {
        return 0;
    }
}
int main()
{
    if(read_file_to_array(DATA_FILE, array, TOTAL_NUM) != 0)
    {
        printf("can't read number from file");
        return -1;
    }
    else
    {
        QuickSort(array, 0, TOTAL_NUM - 1);
    }
    comparisons = comparisons - 1;
    printf("%i and %i" ,comparisons, array[TOTAL_NUM - 1]);
}

If you have any questions, please ask, do not put my question on hold again.

\$\endgroup\$
  • \$\begingroup\$ Seems you are not counting comparisons, but trying to compute the count. Think about having a function for key comparison, passing & calling that per function pointer - qsort() uses int (*compar)(const void*,const void*). \$\endgroup\$ – greybeard Dec 24 '16 at 8:12
  • \$\begingroup\$ @greybeard I'm sorry, I don't quite understand. If I am correct, you use the comparison variable as a function parameter and pass to by reference via a pointer. \$\endgroup\$ – Jainil Shah Dec 24 '16 at 9:45
  • \$\begingroup\$ @greybeard I don't quite understand, could you procure some pseudocode please \$\endgroup\$ – Jainil Shah Dec 24 '16 at 9:49
  • \$\begingroup\$ Still don't have a solution yet \$\endgroup\$ – Jainil Shah Dec 24 '16 at 11:05
  • 2
    \$\begingroup\$ The median of {7, 3, 9} is 7. The median is the middle element, when the elements are sorted into order. Quicksort does not work well is the pivot is at one end of the array. Picking median-of-3 or median-of-5 is a way to avoid having the pivot too close to the end of the array. \$\endgroup\$ – rossum Dec 24 '16 at 11:09
1
\$\begingroup\$

I don't intend to (directly) address/solve your counting problem, but comment on the code presented:
// using last element as pivot now
is an example of a comment not getting updated when the code is - place comments as near to the code they comment as possible, and check comments, too.

#defines for input size & path: there are ways that do not require a recompile.

int Partition(int *array, int l, int r) lacks a specification, in the code:
What is it to return? What are required and admissible side effects?
While the first two parameters are not hard to interpret, it would be nice to have r stated explicitly to be inclusive or exclusive.
You code picking a pivot index/value directly into a function named Partition - consider to factor out PickPivot(). (Do you try to follow a coding convention? Some of your function names are CamelCase, others lower.)
You spend many lines to place the median of three at middle, even with three comments about the individual conditional swaps (something else to potentially factor out), but
without a comment for the three combined.
Not naming p pivot piques me more than l&r - not sure why.
Why are i&j declared outside the for?
Why do you need end?
Next, it gets weird: an open coded swap,
followed by indirectly recursive calls to QuickSort() (still in Partition())
‐ and no return for an int function - you should be getting a warning.

In QuickSort(), you manipulate int comparisons (size_t or long might be more appropriate) in a way that looks evident - it misses the comparisons in selecting the pivot.
(Partition() misses the opportunity to save comparisons capitalising on array[l] <= array[middle] == p <= array[r].)
And, again, int QuickSort() does not (always) return a value.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.