470,849 Members | 652 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,849 developers. It's quick & easy.

Sorting Array of Structures

How would I go about sorting this structure by title?

typedef struct {
char author[40];
char title[40];
char code[4];
int hold;
int loan;
} LIBRARY;

LIBRARY book[N];
This is what I've written:

void sortbytitle( LIBRARY *b, int n ) { /* n = number of books in stock
*/
LIBRARY temp[N];
int i;

for( i = 0; i < n; i++ ) {
if( strcmp( b[i].title, b[i + 1].title ) > 0 ) {
temp[i] = b[i];
b[i] = b[i + 1];
b[i + 1] = temp[i];
}
}

return;
}

I get no errors or warnings when I compile using Bloodshed Dev-C++.
However, my output then looks like this:
AUTHOR TITLE CODE #COPY #BORR #AVAIL
Golumbic Graph Theory G01 5 2 3
Jacobs Database Logic J01 3 1 2
Kanter Management Information K01 8 1 7
Kuo Numerical Methods K02 2 0 2
Habermann Operating Systems H01 10 5 5
Schroder C S01 7 2 5
Herzog Computing Structures H03 10 7 3
Holub Compiler Design H05 11 8 3
Galvin Operating Systems G02 15 2 13
Lane Data Communications L01 20 3 17
Kleinrock Queueing Systems K03 14 0 14
Kindred Data Systems K04 2 0 2
Horowitz Programming Languages H06 16 10 6

(Original output, before sort is called:
AUTHOR TITLE CODE #COPY #BORR #AVAIL
Habermann Operating Systems H01 10 5 5
Golumbic Graph Theory G01 5 2 3
Jacobs Database Logic J01 3 1 2
Kanter Management Information K01 8 1 7
Kuo Numerical Methods K02 2 0 2
Hughs Structured Programming H02 4 4 0
Schroder C S01 7 2 5
Herzog Computing Structures H03 10 7 3
Hunter Understanding C H04 6 6 0
Holub Compiler Design H05 11 8 3
Galvin Operating Systems G02 15 2 13
Lane Data Communications L01 20 3 17
Kleinrock Queueing Systems K03 14 0 14
Kindred Data Systems K04 2 0 2
Mano Computer Architecture M01 2 2 0
Horowitz Programming Languages H06 16 10 6

The sortbytitle() function is used in conjunction with
printbyavail()... which explains the three missing books in the output
produced by sortybytitle().)

The titles aren't sorted properly! What am I doing wrong?

Thank you muchly :)

--Allie

Feb 26 '06 #1
25 10979
Allie said:
How would I go about sorting this structure by title?

typedef struct {
char author[40];
char title[40];
char code[4];
int hold;
int loan;
} LIBRARY;

LIBRARY book[N];


#include <string.h>
#include <stdlib.h>

int complib(const void *vp1, const void *vp2)
{
const LIBRARY *p1 = vp1;
const LIBRARY *p2 = vp2;
return strcmp(p1->title, p2->title);
}

int main(void)
{
getyourdataintothearray();

qsort(book, sizeof book / sizeof book[0], sizeof book[0], complib);

printyourdata();

return 0;
}
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Feb 26 '06 #2
Allie wrote:
How would I go about sorting this structure by title?

typedef struct {
char author[40];
char title[40];
char code[4];
int hold;
int loan;
} LIBRARY;

LIBRARY book[N];


It may be easiest to use `qsort` function. Look it up.

--
BR, Vladimir

Man is a military animal,
Glories in gunpowder, and loves parade.
-- P.J. Bailey

Feb 26 '06 #3
Thanks for your response! :)

I get this as output now:

AUTHOR TITLE CODE #COPY #BORR #AVAIL
Schroder C S01 7 2 5
Holub Compiler Design H05 11 8 3
Herzog Computing Structures H03 10 7 3
Lane Data Communications L01 20 3 17
Kindred Data Systems K04 2 0 2
Jacobs Database Logic J01 3 1 2

It's missing 8 books o_O

--Allie

Feb 26 '06 #4
> It's missing 8 books o_O

....Or seven, rather.

Feb 26 '06 #5
That looks to me like a really naive code.

1.) the cycle will reach behind the buffer in it's last leap

2.) the algorithm seems to me like a one half of bubblesort, but I
cannot imagine, why you have your "temp" as a buffer, the other thing
is that assigning structure variable to other structure variable does a
blasphemous plenty of memory copying (and I do believe that true C-man
avoids that). The right way to sort array of structures is to sort an
array of pointers. And much, much better than (even not spoilt)
bubblesort is to use library func, like that:

#include <stdlib.h>
#include <string.h>

typedef struct {
char author[40];
char title[40];
char code[4];
int hold;
int loan;

} LIBRARY;

static int cmplib (const void *a, const void *b)
{
return (strcmp (((LIBRARY*)a)->title, ((LIBRARY*)b)->title));
}
void do_sort (LIBRARY **l, int count)
{
qsort (l, count, sizeof (LIBRARY*), cmplib);
}

Feb 26 '06 #6
To Richard: qsort( book, n, sizeof( book[0] ), comptitle ); gives me
the right output. You had written qsort( book, sizeof( book ) / sizeof
(book[0] ), sizeof book[0], comptitle ); Thanks for your help!

To Alesak: I'm not a very seasoned programmer. In fact, I'm just a
student still learning the C language. The last time I touched C was
nine months ago... so I'm a little rusty. But I appreciate any and all
help I get (because sometimes I don't know what I'm doing wrong so that
I can't look up the solution to my problem). So thank you :)

Feb 26 '06 #7
Allie wrote:
Thanks for your response! :)

I get this as output now:

How can we fix code we can't see? Post a complete, minimal program,
plus the data.

Also, read the information below.
Brian
--
Please quote enough of the previous message for context. To do so from
Google, click "show options" and use the Reply shown in the expanded
header.
Feb 26 '06 #8
Allie wrote:
How would I go about sorting this structure by title?
Unless you have specific reason not to I would suggest looking up qsort
in your C text book.
typedef struct {
char author[40];
char title[40];
char code[4];
int hold;
int loan;
} LIBRARY;

LIBRARY book[N];
This is what I've written:

void sortbytitle( LIBRARY *b, int n ) { /* n = number of books in stock
*/
LIBRARY temp[N];
Why make this an array? You only use each element once.
LIBRARY temp;
int i;

for( i = 0; i < n; i++ ) {
You are doing one too many elements. There is no element after the last
element for you to compare against and possibly swap with!
for( i = 0; i < n-1; i++ ) {

if( strcmp( b[i].title, b[i + 1].title ) > 0 ) {
temp[i] = b[i];
temp = b[i];
b[i] = b[i + 1];
b[i + 1] = temp[i];
b[i+1] = temp;
}
}

return;
}

I get no errors or warnings when I compile using Bloodshed Dev-C++.


<snip>

Not surprising, your only C error is going off the end of your array,
and compilers don't have to complain about that.

You also have a major algorithm error, but we only do C here not
algorithms. I believe comp.programming does algorithms, so if you need
to implement a sort algorithm (I'm guessing that is your assignment and
your reason for not using qsort) then that is the place to ask.

However, here are some hint for you:

How can you move an element from position 2 to position 0? Your
implementation can at most move it to position 1.

Google for "bubble sort" since I think that is what you are trying to
implement and it is also nice and easy to understand. There are more
efficient algorithms, but they are harder to understand and you should
start with the simplest approach.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc
Feb 26 '06 #9
"Allie" <fa**********@gmail.com> writes:
To Richard: qsort( book, n, sizeof( book[0] ), comptitle ); gives me
the right output. You had written qsort( book, sizeof( book ) / sizeof
(book[0] ), sizeof book[0], comptitle ); Thanks for your help!


Richard's sizeof(book) / sizeof(book[0] assumes you want to sort the
entire array; apparently you just want to sort the first n entries.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Feb 26 '06 #10
Flash Gordon <sp**@flash-gordon.me.uk> writes:
[...]
Google for "bubble sort" since I think that is what you are trying to
implement and it is also nice and easy to understand. There are more
efficient algorithms, but they are harder to understand and you should
start with the simplest approach.


Bubble sort is a decent good starting point if you're trying to
understand the process of sorting; it's fairly simple, and it's
relatively easy to understand how it works. But it also happens to be
one of the *least* efficient sorting algorithms, at least among those
that weren't deliberately designed for inefficiency.[*]

But the simplest way to sort something in C is to use the predefined
qsort() function. It has the advantage that the algorithm itself is
likely to be as efficient as possible, or nearly so. The
disadvantages are that the interface imposes some overhead (an
indirect function call for each comparison), and you can't necessarily
see the algorithm (which isn't necessarily Quicksort).
[*]
One of my favorite "pessimal" sorting algorithms is Permutation
Sort. Starting with an array of elements, generate all possible
permutations. Check each permutation to see whether it happens to be
sorted. (An optimized version allows you to stop at this point;
otherwise you can save the sorted permutation and continue to generate
all the others.)

Another really bad technique is Miracle Sort (which, strictly
speaking, doesn't qualify as an algorithm). Start with an array of
elements. Check whether it's sorted. If it is, you're done.
Otherwise, wait a while and check again. Pray for cosmic rays or
other fortuitous memory faults.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Feb 26 '06 #11
On 2006-02-26, Keith Thompson <ks***@mib.org> wrote:
"Allie" <fa**********@gmail.com> writes:
To Richard: qsort( book, n, sizeof( book[0] ), comptitle ); gives me
the right output. You had written qsort( book, sizeof( book ) / sizeof
(book[0] ), sizeof book[0], comptitle ); Thanks for your help!


Richard's sizeof(book) / sizeof(book[0] assumes you want to sort the
entire array; apparently you just want to sort the first n entries.


or "book" is a pointer and "n" is the number of entries in the array it
points at the first element of.
Feb 26 '06 #12
Keith Thompson <ks***@mib.org> writes:
Another really bad technique is Miracle Sort (which, strictly
speaking, doesn't qualify as an algorithm). Start with an array of
elements. Check whether it's sorted. If it is, you're done.
Otherwise, wait a while and check again. Pray for cosmic rays or
other fortuitous memory faults.


My guess is that it's more likely for the processor to
malfunction and decide that the data is sorted, when it really is
not,than it is for the malfunction to change the data to sorted
order.
--
"I ran it on my DeathStation 9000 and demons flew out of my nose." --Kaz
Feb 27 '06 #13
Jordan Abel <ra*******@gmail.com> writes:
On 2006-02-26, Keith Thompson <ks***@mib.org> wrote:
"Allie" <fa**********@gmail.com> writes:
To Richard: qsort( book, n, sizeof( book[0] ), comptitle ); gives me
the right output. You had written qsort( book, sizeof( book ) / sizeof
(book[0] ), sizeof book[0], comptitle ); Thanks for your help!


Richard's sizeof(book) / sizeof(book[0] assumes you want to sort the
entire array; apparently you just want to sort the first n entries.


or "book" is a pointer and "n" is the number of entries in the array it
points at the first element of.


In the original code (since snipped), "book" was an array.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Feb 27 '06 #14
Ben Pfaff <bl*@cs.stanford.edu> writes:
Keith Thompson <ks***@mib.org> writes:
Another really bad technique is Miracle Sort (which, strictly
speaking, doesn't qualify as an algorithm). Start with an array of
elements. Check whether it's sorted. If it is, you're done.
Otherwise, wait a while and check again. Pray for cosmic rays or
other fortuitous memory faults.


My guess is that it's more likely for the processor to
malfunction and decide that the data is sorted, when it really is
not,than it is for the malfunction to change the data to sorted
order.


Not if the technique lives up to its name.

(Amusing typo: I initially left the 'v' out of "lives".)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Feb 27 '06 #15
Keith Thompson wrote:
Flash Gordon <sp**@flash-gordon.me.uk> writes:
[...]
Google for "bubble sort" since I think that is what you are trying to
implement and it is also nice and easy to understand. There are more
efficient algorithms, but they are harder to understand and you should
start with the simplest approach.


Bubble sort is a decent good starting point if you're trying to
understand the process of sorting; it's fairly simple, and it's
relatively easy to understand how it works. But it also happens to be
one of the *least* efficient sorting algorithms, at least among those
that weren't deliberately designed for inefficiency.[*]

But the simplest way to sort something in C is to use the predefined
qsort() function. It has the advantage that the algorithm itself is


<snip>

Yes, I know. I even said in the text you snipped, "Unless you have
specific reason not to I would suggest looking up qsort in your C text
book." I went on to say, still before the bit you snipped, "... so if
you need to implement a sort algorithm (I'm guessing that is your
assignment and your reason for not using qsort) ..."

Personally I have never bothered implementing a sort algorithm myself
and probably never will. If I need something better than qsort I'll ask
experts and then use an implementation written by someone else.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc
Feb 27 '06 #16
Flash Gordon <sp**@flash-gordon.me.uk> writes:
Keith Thompson wrote:
Flash Gordon <sp**@flash-gordon.me.uk> writes:
[...]
Google for "bubble sort" since I think that is what you are trying to
implement and it is also nice and easy to understand. There are more
efficient algorithms, but they are harder to understand and you should
start with the simplest approach.

Bubble sort is a decent good starting point if you're trying to
understand the process of sorting; it's fairly simple, and it's
relatively easy to understand how it works. But it also happens to be
one of the *least* efficient sorting algorithms, at least among those
that weren't deliberately designed for inefficiency.[*]
But the simplest way to sort something in C is to use the predefined
qsort() function. It has the advantage that the algorithm itself is


<snip>

Yes, I know. I even said in the text you snipped, "Unless you have
specific reason not to I would suggest looking up qsort in your C text
book." I went on to say, still before the bit you snipped, "... so if
you need to implement a sort algorithm (I'm guessing that is your
assignment and your reason for not using qsort) ..."


So you did. My apologies for not reading carefully enough.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Feb 27 '06 #17
Ben Pfaff wrote:
Keith Thompson <ks***@mib.org> writes:
Another really bad technique is Miracle Sort (which, strictly
speaking, doesn't qualify as an algorithm). Start with an array of
elements. Check whether it's sorted. If it is, you're done.
Otherwise, wait a while and check again. Pray for cosmic rays or
other fortuitous memory faults.


My guess is that it's more likely for the processor to
malfunction and decide that the data is sorted, when it really is
not,than it is for the malfunction to change the data to sorted
order.


Another possibility is operator malfunction, making the other
malfunctions more or less moot. Many of us are already pushing our
MTBF values.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
Feb 27 '06 #18
Allie said:
To Richard: qsort( book, n, sizeof( book[0] ), comptitle ); gives me
the right output. You had written qsort( book, sizeof( book ) / sizeof
(book[0] ), sizeof book[0], comptitle );


What I wrote was based on the information you gave me. If you gave me the
wrong information, that is your lookout, not mine.

Incidentally, you have misquoted me. I most certainly did not write:

sizeof( book ) / sizeof (book[0] )

If you wish to become a successful programmer, you will need to develop a
more pedantic approach with regard to accuracy, precision, and correctness.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Feb 27 '06 #19

CBFalconer wrote:
Many of us are already pushing our MTBF values.


Gather ye rosebuds while ye may.

Feb 27 '06 #20
Richard Heathfield wrote:
Incidentally, you have misquoted me. I most certainly did not write:

sizeof( book ) / sizeof ( book[0] )


Your original qsort( book, sizeof book / sizeof book[0], sizeof
book[0], comptitle ); did not work... so I had to adjust it.

This is what I get as output when I use your qsort:

Inventory of books printed in alphabetical order by title:

AUTHOR TITLE CODE #COPY #BORR #AVAIL
Galvin Operating Systems G02 15 2 13
Golumbic Graph Theory G01 5 2 3
Habermann Operating Systems H01 10 5 5
Herzog Computing Structures H03 10 7 3
Holub Compiler Design H05 11 8 3
Horowitz Programming Languages H06 16 10 6
Hughs Structured Programming H02 4 4 0
Hunter Understanding C H04 6 6 0
Jacobs Database Logic J01 3 1 2
Kanter Management Information K01 8 1 7
Kindred Data Systems K04 2 0 2
Kleinrock Queueing Systems K03 14 0 14
Kuo Numerical Methods K02 2 0 2
Lane Data Communications L01 20 3 17
Mano Computer Architecture M01 2 2 0
Schroder C S01 7 2 5

The books are listed alphabetically by author because that's what the
previous function (using qsort( book, n, sizeof( book[0] ), compauthor
);) did. sortbytitle() didn't do anything to the library.

Feb 27 '06 #21
Allie said:
Richard Heathfield wrote:
Incidentally, you have misquoted me. I most certainly did not write:

sizeof( book ) / sizeof ( book[0] )

Your original qsort( book, sizeof book / sizeof book[0], sizeof
book[0], comptitle );


That looks more like it.
did not work... so I had to adjust it.
Then you have used it in a different context to that in which I posted it,
which was in the context of an array at file scope. What may have happened
is that you have decided to use a function to wrap around the qsort (which
is fine), and then decided to send the book array in as a parameter. In
that context, it would be converted to a pointer to the first element in
that book array, and the sizeof book / sizeof book[0] calculation would
break as a result.

In that new context, you would indeed have to supply the number of elements
in the array "by hand", as you now seem to have done.

<snip>
The books are listed alphabetically by author because that's what the
previous function (using qsort( book, n, sizeof( book[0] ), compauthor
);) did. sortbytitle() didn't do anything to the library.

^^^^^^^^^^^

Aha! My hypothesis appears to be correct.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Feb 27 '06 #22
Richard Heathfield wrote:
[...] What may have happened
is that you have decided to use a function to wrap around the qsort (which
is fine), and then decided to send the book array in as a parameter. In
that context, it would be converted to a pointer to the first element in
that book array, and the sizeof book / sizeof book[0] calculation would
break as a result.

In that new context, you would indeed have to supply the number of elements
in the array "by hand", as you now seem to have done.


That is what happened, yes. Once again, thank you :)

--Allie

Feb 27 '06 #23
Richard Heathfield <in*****@invalid.invalid> writes:
Allie said:
To Richard: qsort( book, n, sizeof( book[0] ), comptitle ); gives me
the right output. You had written qsort( book, sizeof( book ) / sizeof
(book[0] ), sizeof book[0], comptitle );


What I wrote was based on the information you gave me. If you gave me the
wrong information, that is your lookout, not mine.


Quoting the article that started this thread:

] How would I go about sorting this structure by title?
]
] typedef struct {
] char author[40];
] char title[40];
] char code[4];
] int hold;
] int loan;
] } LIBRARY;
]
] LIBRARY book[N];
]
]
] This is what I've written:
]
] void sortbytitle( LIBRARY *b, int n ) { /* n = number of books in stock
] */
] LIBRARY temp[N];
] int i;
]
] for( i = 0; i < n; i++ ) {
] if( strcmp( b[i].title, b[i + 1].title ) > 0 ) {
] temp[i] = b[i];
] b[i] = b[i + 1];
] b[i + 1] = temp[i];
] }
] }
]
] return;
] }

The code is wrong in a number of ways (the sorting algorithm doesn't
work, and the use of an array of temporaries is unnecessary), but
given the declarations of book (an array of N LIBRARY objects) and
sortbytitle (a function taking a pointer to LIBRARY and an int n,
"number of books in stock"), it seemed reasonably obvious from the
beginning that N is the total size of the array and n is the number of
array elements that contain valid values.

The use of both N and n as identifiers is legal, but confusingly poor
style.

Richard, I'm not surprised that you missed this, but it was there.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Feb 27 '06 #24
Keith Thompson said:

Richard, I'm not surprised that you missed this, but it was there.


Fair enough. In fact I took one quick look at his code and thought "blech,
let's crack out a qsort ASAP!" so I'm not surprised I missed it, either.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Feb 27 '06 #25
Keith Thompson wrote:
Flash Gordon <sp**@flash-gordon.me.uk> writes:
Keith Thompson wrote:
<snip>
Yes, I know. I even said in the text you snipped, "Unless you have

<snip>
So you did. My apologies for not reading carefully enough.


Not a problem.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc
Mar 2 '06 #26

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

7 posts views Thread by Federico G. Babelis | last post: by
7 posts views Thread by Foodbank | last post: by
5 posts views Thread by DKC | last post: by
2 posts views Thread by Allie | last post: by
5 posts views Thread by lemlimlee | last post: by
5 posts views Thread by jrod11 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.