I'm trying to work my way through The C Programming Language, 2nd Edition, and I can't get my head around exactly what is happening in the following code.
The example from the book works just fine when sorting an array of strings but I get a SEGFAULT when sorting an array of integers.
I know it is probably because the integer value is being used as a pointer to a value and I think the problem happens when swap() is called for the first time but I can't work out how to fix the problem. (I don't want to have two separate quick sort functions).
#include <stdio.h>
#include <string.h>
#include <limits.h>
int atoi (char s_string[])
/* See K+R Ed 2 Page 43 */
{
int i_count, i_number;
i_number = 0;
for (i_count = 0; s_string[i_count] >= '0' && s_string[i_count] <= '9'; i_count++)
i_number = 10 * i_number + s_string[i_count] - '0';
return i_number;
}
static void swap (void *p_array[], int i_left, int i_right)
/* See K+R Ed 2 Page 96 */
{
void* p_temp;
p_temp = p_array[i_left];
p_array[i_left] = p_array[i_right];
p_array[i_right] = p_temp;
}
void qsort (void *p_array[], int i_left, int i_right, int (*compare)(void *, void*))
/* See K+R Ed 2 Page 120 */
{
int i_count, i_last;
if (i_left >= i_right) return; /* Do nothing */
swap (p_array, i_left, (i_left + i_right)/2);
i_last = i_left;
for (i_count = i_left +1; i_count <= i_right; i_count++)
if ((*compare)(p_array[i_count], p_array[i_left]) < 0)
swap(p_array, ++i_last, i_count);
swap (p_array, i_left, i_last);
qsort (p_array, i_left, i_last -1, compare);
qsort (p_array, i_last +1, i_right, compare);
}
int numcmp (char *s_left, char *s_right)
/* See K+R Ed 2 Page 121 */
{
int i_left, i_right;
i_left = atoi (s_left);
i_right = atoi (s_right);
if (i_left < i_right)
return -1;
else if (i_left > i_right)
return 1;
else
return 0;
}
int cmpint (int i_left, int i_right)
{
return (i_left > i_right) - (i_left < i_right);
}
int cmpstr (char *s_left, char *s_right)
{
return strcmp (s_left, s_right);
}
void prtint (int *array, size_t i_size)
{
size_t i_count;
if (i_size > 0)
{
printf ("(%d", array[0]);
for (i_count = 1; i_count < i_size; i_count++)
printf (", %d", array[i_count]);
}
printf (")\n");
}
void prtstr (char * const *array, size_t i_size)
{
size_t i_count;
if (i_size > 0)
{
printf ("(%s", array[0]);
for (i_count = 1; i_count < i_size; i_count++)
printf (", %s", array[i_count]);
}
printf (")\n");
}
int main(void)
{
int i_numbers[] = {INT_MAX, 5, 9, 4, 8, 3, 7, 10, 2, 1, 6, INT_MIN};
char *s_strings[] = { "One", "Two", "Three", "Four", "Five", "", "Seven", "Eight", "Nine" };
int i_size;
i_size = sizeof(s_strings)/sizeof(s_strings[0]);
prtstr (s_strings, i_size);
qsort ((void **)s_strings, 0, i_size -1, (int (*)(void *, void*))cmpstr);
prtstr (s_strings, i_size);
i_size = sizeof(i_numbers)/sizeof(i_numbers[0]);
prtint (i_numbers, i_size);
qsort ((void **)i_numbers, 0, i_size -1, (int (*)(void *, void*))cmpint);
prtint (i_numbers, i_size);
}
The qsort implementation here is for sorting arrays of pointers.
BTW: It also assumes that all pointers have the same size (and alignment) as void-pointers. That's the typical case but the C standard doesn't guarantee that.
As this is for sorting arrays of pointers, it can't be used for sorting arrays of int. As stated in the question, the swap function is problematic.
You may be able to change a few things in the code and use it to sort an array of int-pointers based on the pointed to value.
In main something like:
//int i_numbers[] = {INT_MAX, 5, 9, 4, 8, 3, 7, 10, 2, 1, 6, INT_MIN};
int a = 42;
int b = 100;
int c = 43;
int* i_numbers[] = {&a, &b, &c};
....
//qsort ((void **)i_numbers, 0, i_size -1, (int (*)(void *, void*))cmpstr);
qsort ((void **)i_numbers, 0, i_size -1, (int (*)(void *, void*))cmpint);
and in cmpint something like:
int cmpint (int *i_left, int *i_right)
{
//printf ("%d %d\n", *i_left, *i_right);
if (*i_left < *i_right) return -1;
if (*i_left > *i_right) return 1;
return 0;
}
and in prtint something like:
void prtint (int **array, size_t i_size)
{
size_t i_count;
if (i_size > 0)
{
printf ("(%d", *array[0]);
for (i_count = 1; i_count < i_size; i_count++)
printf (", %d", *array[i_count]);
}
printf (")\n");
}
I don't think this is guaranteed to work on all systems (due to the assumption on pointer size) but it works on my system. I get:
(42, 100, 43)
(42, 43, 100)
However, there is no way to use this qsort as a generic array sorting function as the size of the elements isn't known by this qsort.
The standard qsort uses "size of element" and "number of elements" (instead of array indexes) to get it correct. That makes it possible to implement a generic swap function.