bubble sort array of structs in C....?

Question

include
#include
#include
#include
#include
#include
#include

struct content
{
char *pro_name;

int priority;

int quanta;
}ps[2000];

main (int argc, char **argv)
{

int status;
struct stat inode;
int fd;
char *buffer;
int i = 0;
char *saveptr1;
char *saveptr2;
char *line;
int n = 0;


/* Check the command line arguments */
if (argc != 2)
{
printf("syntax is: %s filename\n", argv[0]);
exit (1);
}

/* Check the name exists and is a file */
if ((stat(argv[1], &inode) == -1) || (!S_ISREG(inode.st_mode)))
{
printf("%s is not a file\n", argv[1]);
exit(2);
}

/* Open the file for reading */
fd = open(argv[1], O_RDONLY, 0);

if (fd == -1)
{
printf("%s cannot be opened\n", argv[1]);
exit(3);
}

buffer=(char*)malloc(inode.st_size * sizeof(char) + 1);

buffer[inode.st_size+1] = '\0';

/* Begin processing the file here */

status = read(fd, buffer, inode.st_size);

if (status == -1)
{
printf("%s cannot be read\n", argv[1]);
exit(4);
}

printf("\ninode size:%d | status size:%d\n\n",(int)inode.st_size, status);

/* extract first string from string sequence */
line = strtok_r(buffer, "\n",&saveptr1);

/* loop until finishied */
while (line !=NULL)
{
/* extract string from string sequence */
ps[i].pro_name = strtok_r(line, " ",&saveptr2);
ps[i].quanta = atoi(strtok_r(NULL, " ",&saveptr2));
ps[i].priority = atoi(strtok_r(NULL," ", &saveptr2));

/* print string after tokenized */
printf("name: %s\nquanta: %d\npriority: %d\n", ps[i].pro_name, ps[i].quanta, ps[i].priority);

line = strtok_r(NULL,"\n",&saveptr1);
i++;
}

/* test to see if array worked to access individual content */
printf("\nProcess Name: %s --- its Quanta (CPU Time) is: %d\n\n", ps[4].pro_name, ps[4].quanta);

close(fd);
free(buffer);
}

Now i need to find a way of sorting the contents of the file i read in.

the file i read in has this content :
Line01 5 7
Line02 6 1
LIne03 1 3

i have split it so Line01 goes into pro_name, then the number after "5" goes into quanta then "7" goes into priority. now i need to find a way of arranging the contents of quanta into ascending order and then do the same with priority.... have looked at using bubble sort but i have had a few goes and i have no how idea how i will do it with the array of structs

any help would be appreciated

thank you

Answer 1

To make sorting easier, you could define an array of pointers to your structures; then sorting just becomes a matter of rearranging the pointers. Or, you could have an array of structures, as you do, and the sort function would have to rearrange the contents of the structs. In either case, you're going to need a way of comparing the structures, and it sounds like you want at least a couple of different ways of comparing, so you can sort using different keys.



See below for a simple example of how I would do this. You mentioned bubble sort, but I used selection sort since it's better. You might notice that in selectionSort I do a shallow struct-to-struct copy, simply copying the char *name and not the contents of the char array. I think this is reasonable, and saves time. A good enhancement to my code would be a swap function for selectionSort to use, that can take care of exchanging contents of the structs. Then the swap could be done however you like, and selectionSort wouldn't have to bother with the details.



#include

#include

#include



const int N = 4;

const int MAX_VAL = 100;



const char *names[] = {

    "John Smith", "Mary Jones", "Alice Alvarez", "Joe Zeller" };

const int ages[] = { 45, 24, 32, 17 };

const int years[] = { 2010, 2008, 2009, 2001 };



typedef struct {

    char *name;

    int age;

    int year;

} data_t;



typedef int (*cmp)(data_t *,data_t *);

int cmpName(data_t *, data_t *);

int cmpAge(data_t *, data_t *);

int cmpYear(data_t *, data_t *);



void selectionSort(data_t *, int, cmp);

void printArray(const data_t *, int);



int main(int argc, char *argv[]) {

    data_t *dataArray;

    int i;



    /* allocate array of structs */

    dataArray = (data_t *)malloc(N * sizeof(data_t));



    /* fill array */

    for (i = 0; i < N; i++) {

        dataArray[i].name = malloc(strlen(names[i]) + 1);

        strcpy(dataArray[i].name, names[i]);

        dataArray[i].age = ages[i];

        dataArray[i].year = years[i];

    }

   

    printf("unsorted : ");

    printArray(dataArray,N);

    selectionSort(dataArray,N,cmpName);

    printf(" sorted by name : ");

    printArray(dataArray,N);

    selectionSort(dataArray,N,cmpAge);

    printf(" sorted by age : ");

    printArray(dataArray,N);

    selectionSort(dataArray,N,cmpYear);

    printf(" sorted by year : ");

    printArray(dataArray,N);





    /* deallocate */

    for (i = 0; i < N; i++) {

        free(dataArray[i].name);

    }

    free(dataArray);

   

    return 0;

}



int cmpName(data_t *d1, data_t *d2) {

    return strcmp(d1->name,d2->name);

}



int cmpAge(data_t *d1, data_t *d2) {

    int z = 0;



    if (d1->age < d2->age) {

        z = -1;

    } else if (d1->age > d2->age) {

        z = 1;

    }

    return z;

}



int cmpYear(data_t *d1, data_t *d2) {

    int z = 0;



    if (d1->year < d2->year) {

        z = -1;

    } else if (d1->year > d2->year) {

        z = 1;

    }

    return z;

}



void selectionSort(data_t *a, int n, cmp compare) {

    int i, j, min;

    data_t t;



    for (i = 0; i < n; i++) {

        min = i;

        for (j = i+1; j < n; j++) {

            if (compare(&a[j],&a[min]) < 0) {

                min = j;

            }

        }

        t = a[min];

        a[min] = a[i];

        a[i] = t;

    }

}



void printArray(const data_t *a, int n) {

    int i;



    puts("");

    for (i = 0; i < n; i++) {

        printf("%-15s : %2d : %2d\n", a[i].name, a[i].age, a[i].year);

    }

    puts("");

}



#if 0



unsorted :

John Smith : 45 : 2010

Mary Jones : 24 : 2008

Alice Alvarez : 32 : 2009

Joe Zeller : 17 : 2001



    sorted by name :

Alice Alvarez : 32 : 2009

Joe Zeller : 17 : 2001

John Smith : 45 : 2010

Mary Jones : 24 : 2008



    sorted by age :

Joe Zeller : 17 : 2001

Mary Jones : 24 : 2008

Alice Alvarez : 32 : 2009

John Smith : 45 : 2010



    sorted by year :

Joe Zeller : 17 : 2001

Mary Jones : 24 : 2008

Alice Alvarez : 32 : 2009

John Smith : 45 : 2010



#endif

Answer 2

It looks like you're overwriting pro_name each time you read a new record. You should make pro_name an actual string rather than a pointer, e.g.



#define MAX_NAME_LEN 40

#define MAX_RECORDS 2000



struct content

{

....char pro_name[MAX_NAME_LEN];

....int priority;

....int quanta;

} ps[MAX_RECORDS];



Then use strcpy to copy the name from your buffer to the pro_name field.



Also I don't understand why you're using low level I/O to read your file - this seems like a lot of extra work (and potential sources of error) for nothing - what's wrong with using fopen/fscanf/etc ?

Answer 3

Another way to go is using the standard function qsort (prototype in stdlib.h)

In case your structure would be as Paul suggested you could use qsort as follows:

struct content

{

....char pro_name[MAX_NAME_LEN];

....int priority;

....int quanta;

} ps[MAX_RECORDS];



qsort takes the following parameter:

void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );



compare is a function pointer with the following signature:

int compare(const void *arg1, const void *arg2);



you could implement it as follows:



// please note: the following would perform comparison

// in priorities:

// in case the comparison of strings is equal, it would

// compare by priority and if priorities are identical it

// would compare by quanta.

// in case you wish to change the order, you just need

// to prefix the return values with -;

int compare(const void *arg1, const void *arg2)

{

struct content *a = (struct content *)arg1,

*b = (struct content *)arg2;

int iCompare = strcmp(a->pro_name, b->pro_name);

if (iCompare != 0) {

return iCompare;

}

iCompare = a->priority - b->priority;

if (iCompare != 0) {

return iCompare;

}

return a->quanta - b->quanta;

}





Now that you have your compare function implemented, you can call qsort as follows:

qsort(ps, sizeof(struct content), MAX_RECORDS, compare);



in this sample MAX_RECORDS is probably not the number of records you want to provide, but rather the number of records you have read into your array.



I hope this helps.