Author : Ted Jensen
Page : << Previous 11 Next >>
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare(&p[j-1], &p[j]))
{
t = p[j-1];
p[j-1] = p[j];
p[j] = t;
}
}
}
}
int compare(int *m, int *n)
{
return (*m > *n);
}
/*------------------ end of bubble3.c -------------------------*/
Note the changes. We are now passing a pointer to an integer (or array of integers) to bubble(). And from within bubble we are passing pointers to the elements of the array that we want to compare to our comparison function. And, of course we are dereferencing these pointer in our compare() function in order to make the actual comparison. Our next step will be to convert the pointers in bubble() to pointers to type void so that that function will become more type insensitive. This is shown in bubble_4.
/*------------------ bubble_4.c ----------------------------*/
/* Program bubble_4.c from PTRTUT10,HTM 6/13/97 */
#include <stdio.h>
int arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(int *p, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr,10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
void bubble(int *p, int N)
{
int i, j, t;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare((void *)&p[j-1], (void *)&p[j]))
{
t = p[j-1];
p[j-1] = p[j];
p[j] = t;
}
}
}
}
int compare(void *m, void *n)
{
int *m1, *n1;
m1 = (int *)m;
n1 = (int *)n;
return (*m1 > *n1);
}
/*------------------ end of bubble_4.c ---------------------*/
Note that, in doing this, in compare() we had to introduce the casting of the void pointer types passed to the actual type being sorted. But, as we'll see later that's okay. And since what is being passed to bubble() is still a pointer to an array of integers, we had to cast these pointers to void pointers when we passed them as parameters in our call to compare().
We now address the problem of what we pass to bubble(). We want to make the first parameter of that function a void pointer also. But, that means that within bubble() we need to do something about the variable t, which is currently an integer. Also, where we use t = p[j-1]; the type of p[j-1] needs to be known in order to know how many bytes to copy to the variable t (or whatever we replace t with).
Currently, in bubble_4.c, knowledge within bubble() as to the type of the data being sorted (and hence the size of each individual element) is obtained from the fact that the first parameter is a pointer to type integer. If we are going to be able to use bubble() to sort any type of data, we need to make that pointer a pointer to type void. But, in doing so we are going to lose information concerning the size of individual elements within the array. So, in bubble_5.c we will add a separate parameter to handle this size information.
These changes, from bubble4.c to bubble5.c are, perhaps, a bit more extensive than those we have made in the past. So, compare the two modules carefully for differences.
/*---------------------- bubble5.c ---------------------------*/
/* Program bubble_5.c from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <string.h>
long arr[10] = { 3,6,1,2,3,8,4,1,7,2};
void bubble(void *p, size_t width, int N);
int compare(void *m, void *n);
int main(void)
{
int i;
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%d ", arr[i]);
}
bubble(arr, sizeof(long), 10);
putchar('\n');
for (i = 0; i < 10; i++)
{
printf("%ld ", arr[i]);
}
return 0;
}
void bubble(void *p, size_t width, int N)
{
int i, j;
unsigned char buf[4];
unsigned char *bp = p;
for (i = N-1; i >= 0; i--)
{
for (j = 1; j <= i; j++)
{
if (compare((void *)(bp + width*(j-1)),
(void *)(bp + j*width))) /* 1 */
{
/* t = p[j-1]; */
memcpy(buf, bp + width*(j-1), width);
/* p[j-1] = p[j]; */
memcpy(bp + width*(j-1), bp + j*width , width);
/* p[j] = t; */
memcpy(bp + j*width, buf, width);
}
}
}
}
int compare(void *m, void *n)
{
long *m1, *n1;
m1 = (long *)m;
n1 = (long *)n;
return (*m1 > *n1);
}
/*--------------------- end of bubble5.c ---------------------*/
Note that I have changed the data type of the array from int to long to illustrate the changes needed in the compare() function. Within bubble() I've done away with the variable t (which we would have had to change from type int to type long). I have added a buffer of size 4 unsigned characters, which is the size needed to hold a long (this will change again in future modifications to this code). The unsigned character pointer *bp is used to point to the base of the array to be sorted, i.e. to the first element of that array.
We also had to modify what we passed to compare(), and how we do the swapping of elements that the comparison indicates need swapping. Use of memcpy() and pointer notation instead of array notation work towards this reduction in type sensitivity.
Again, making a careful comparison of bubble5.c with bubble4.c can result in improved understanding of what is happening and why.
We move now to bubble6.c where we use the same function bubble() that we used in bubble5.c to sort strings instead of long integers. Of course we have to change the comparison function since the means by which strings are compared is different from that by which long integers are compared. And,in bubble6.c we have deleted the lines within bubble() that were commented out in bubble5.c.
/*--------------------- bubble6.c ---------------------*/
/* Program bubble_6.c from PTRTUT10.HTM 6/13/97 */
#include <stdio.h>
#include <string.h>
#define MAX_BUF 256
char arr2[5][20] = { "Mickey Mouse",
Page : << Previous 11 Next >>