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/