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.
1 Answer 1
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.
qsort()usesint (*compar)(const void*,const void*). \$\endgroup\$