• 1

• 23
• 1
• 3

I'm trying to re-implement the C stdlib function qsort using a median of 3 quicksort.

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

This is my first major project in C, and I'd like to know how my style looks and what techniques I might be missing out on. Thanks for the help.

In sort.h, I have

/* returns > 0 if arg1 is greater than arg2, 0 if equal, < 0 if less*/
typedef int (*compare_func)(void *, void *);
/*Median of 3 quicksort Function*/
void quick_sort(void * arr, size_t nitems, size_t size, compare_func compare);

And in quick_sort.c I have

#include "sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
void swap_mem(void * ptr1, void * ptr2, size_t size){
 /*
 * Swaps the values at the addresses pointed at by ptr1 and ptr2
 */
 void * tmp = malloc(size);
 memcpy(tmp, ptr1, size);
 memcpy(ptr1, ptr2, size);
 memcpy(ptr2, tmp, size);
 free(tmp);
}
void median_of_3(void * arr, size_t start, size_t stop, size_t size, compare_func compare){
 /*
 * Performs median of 3 partitioning on an array starting at start and ending
 * at stop
 */
 int mid;
 /*determine midpoint of array to nearest integer multiple of size*/
 mid = ((start + stop)>>1)/size * size;
 /*sort the 3 item array by comparing middle value to first and last value*/
 if(compare(arr + stop, arr + start) < 0)
 swap_mem(arr + stop, arr + start, size);
 if(compare(arr + mid, arr + start) < 0)
 swap_mem(arr + mid, arr + start, size);
 if(compare(arr + stop, arr + mid) < 0)
 swap_mem(arr + stop, arr + mid, size);
 /*swap the second to last value of arr with the median value*/
 swap_mem(arr + mid, arr + stop - size, size);
}
void quick_sort_aux(void * arr, size_t start, size_t stop, size_t size, compare_func compare){
 /*
 * Recursive median-of-3 quick sort
 */
 /*Base Case 1: 1 item in array (already sorted)*/
 if(start >= stop) return;
 /*Base Case 2: sort 2 or 3 item array*/
 median_of_3(arr, start, stop, size, compare);
 if(stop - start <=2*size) return;
 /*Recursively sort larger arrays*/
 int l_ptr = start;
 int r_ptr = stop - 2*size;
 /*move all values to the proper side of the pivot*/
 while(l_ptr <= r_ptr){
 while(compare(arr + l_ptr, arr + stop - size) < 0 && l_ptr <= r_ptr)
 l_ptr+=size;
 while(compare(arr + r_ptr, arr + stop - size) >= 0 && l_ptr <= r_ptr)
 r_ptr-= size;
 if(l_ptr <= r_ptr)
 swap_mem(arr + l_ptr, arr + r_ptr,size);
 }
 /*swap the pivot back into place*/
 swap_mem(arr + l_ptr, arr + stop - size,size);
 /*recursively sort the two halves*/
 quick_sort_aux(arr, start, l_ptr - size, size, compare);
 quick_sort_aux(arr, l_ptr + size, stop, size, compare);
}
void quick_sort(void * arr, size_t nitems, size_t size, compare_func compare){
 /*
 * wrapper for recursive quick_sort_aux
 */
 quick_sort_aux(arr, 0, size*(nitems-1), size, compare);
}

This is my first time posting to StackExchange. Let me know how I can improve my question.