ritchie wrote:
Hi all!
Still working on this program!
Just to recap, I am writing a program to sort an array with four
different sort algorythms.
I am having a little trouble at the moment though!
Now, I am trying to calculate, with each sort, how many times during
the sort the array elements are compared and swapped.
I am coping the original array into a temp (iTmp) array to be sorted.
Then, I am using a menu to call each Sort function where I am passing
in iTmp plus the array's
size to be sorted.
-----------------------------------------
while ((iMenuChoice = menu()) != QUIT) // print menu & loop until
QUIT
switch( iMenuChoice ) {
case 1: // user enters 1: selection sort....
selectionSort( iTmpArr, SIZE );
break;
.
.
.
}
}
-----------------------------------------------
Within each sort function I call 'displaySorted', where I pass in
iTmp(copied array), array size, comparisons & swaps (calculated from
functions).
-------------------------------------
void displaySorted( int iTmpArr[], int iMax, int iComparison, int
iSwaps )
{
int i;
printf("Your Sorted Array:\n");
for(i=0; i<=MAX-1; i++ )
printf("%4d", iTmpArr[i]);
printf("\n");
printf( "Comparisons: %d \n", iComparison );
printf( "Swaps: %d \n", iSwaps );
-----------------------------------------------------+
The problem though, is that each time I call the next sort from the
menu (while still in SWITCH statement until QUIT ) the comparisons and
swaps are being incorrectly calculated.
I know this is because the functions are getting the same array.
I am coping the original array into iTmp BEFORE the SWITCH which is
within the while loop.
I don't believe it would matter, but I would to the array
copying and printing in the while loop.
Is there anywhere else I should be copying the arrays?
I tried to copy the arrays before each function call in the SWITCH but
this didn't work.
Anyone have any ideas?
I assume that when you say it doesn't work that the problem is
incorrect values in the number of comparisons and number of swaps.
If so, you should look carefully at how you define and use these
variables in the sort and/or comparision functions. Here is
an example, untested, of using these variables in a bubblesort and
selectionsort function.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void PointertoOrigin( int *a, int **pa, size_t);
void bubblesort(void *base, size_t n, size_t size,
int (*cmp)(const void *el1, const void *el2),
size_t *comparisons, size_t *swaps);
void selectionsort(void *base, size_t n, size_t size,
int (*cmp)(const void *el1, const void *el2),
size_t *comparisons, size_t *swaps);
void swap(void *e1, void *e2, size_t size);
int cmp(const void *e1, const void *e2);
void PrintArrays(int *a, int **pa,size_t n);
int menuselection(void);
int main(void)
{
int array[10] = {4,3,6,1,8,10,2,5,7,9};
int *parray[10];
size_t comparisons, swaps;
int choice;
while(1)
{
PointertoOrigin(array,parray,10);
choice = menuselection();
if(choice == 'q' || choice == 'Q') break;
if(choice < '1' || choice > '2')
{
puts("Invalid entry. Try again");
continue;
}
switch(choice)
{
case '1': bubblesort(parray,10, sizeof(*parray),
cmp, &comparisons,&swaps);
break;
case '2': selectionsort(parray,10, sizeof(*parray),
cmp, &comparisons,&swaps);
break;
}
PrintArrays(array,parray,10);
printf("Number Comparisons: %u\n"
"Number swaps: %u\n\n\n",
comparisons, swaps);
}
return 0;
}
void PointertoOrigin( int *a, int **pa, size_t n)
{
size_t i;
for(i = 0; i < n;i++)
pa[i] = &a[i];
return;
}
void bubblesort(void *base, size_t n, size_t size,
int (*cmp)(const void *el1, const void *el2),
size_t *comparisons, size_t *swaps)
{
size_t i, sorted = 0;
char *p = (char *) base;
*comparisons = *swaps = 0;
while(!sorted)
{
sorted = 1;
for(i = 0;i < n-1; i++)
{
(*comparisons)++; /* increment the comparison variable */
if(cmp(p+(i*size),p+((i+1)*size))>0)
{
(*swaps)++; /* increment the swap variable */
swap(p+(i*size),p+((i+1)*size),size);
sorted = 0;
}
}
}
}
void swap(void *e1, void *e2, size_t size)
{
char buf[256], *p1 = (char *)e1, *p2 = (char *)e2;
size_t ms;
for(ms = size; 0< ms; )
{
size_t m = ms < sizeof(buf)?ms:sizeof(buf);
memcpy(buf,p1,m);
memcpy(p1,p2,m);
memcpy(p2,buf,m);
ms -= m, p1+=m, p2+=m;
}
return;
}
int cmp(const void *e1, const void *e2)
{
int *i1 = *(int **)e1, *i2 = *(int **)e2;
return (*i1<*i2)?-1:(*i1!=*i2);
}
void PrintArrays( int *a, int **pa, size_t n)
{
size_t i;
printf("The unsorted array: ");
for(i = 0; i < n;i++) printf("%d ",a[i]);
printf("\nThe sorted pointers : ");
for(i = 0; i < n;i++) printf("%d ", *pa[i]);
putchar('\n');
return;
}
void selectionsort(void *base, size_t n, size_t size,
int (*cmp)(const void *el1, const void *el2),
size_t *comparisons, size_t *swaps)
{
size_t position, smallest_idx,i;
char *p = (char *)base;
*comparisons = *swaps = 0;
for(position = 0; position < n-1; position++)
{
smallest_idx = position;
for(i = position+1;i < n; i++)
{
(*comparisons)++;
if(cmp(p+(i*size),p+(smallest_idx*size)) < 0)
smallest_idx = i;
}
if(smallest_idx != position)
{
(*swaps)++;
swap(p+(smallest_idx*size),p+(position*size),size) ;
}
}
}
int menuselection(void)
{
char choice[16];
printf("\nSorting test\n\t1) BubbleSort\n\t"
"2) SelectionSort\nEnter the number"
"('q' to quit): ");
fflush(stdout);
fgets(choice,sizeof choice, stdin);
return (int)*choice;
}
--
Al Bowers
Tampa, Fl USA
mailto:
xa******@myrapidsys.com (remove the x to send email)
http://www.geocities.com/abowers822/ 
