# Qsort-ing structures

Discussion in 'C Programming' started by Albert, Feb 19, 2009.

1. ### AlbertGuest

Hi:

I did a 4-hour programming contest this morning-early afternoon and I
had the following problem which I'll put in a nutshell, hopefully
that's enough to get even the vaguest idea as to what my code (when I
post it) was to intentionally do

--
You love playing Space Invaders. It's where ONE row of enemy bots are
on the top of the screen. You're on the bottom and may move only
horizontally. When you fire, you fire straight up till the bullet
destroys an enemy. You love the game so much that you stay all night
playing it. Therefore, you eventually get to the last and hardest
level. In this level, some of the screen is covered with polygons. If
the polygon happens to cover a particular column, firing at that
column won't do anything. So if the input tells you how wide and how
tall the screen is (I believe it was from 3 -> 10^7 for both
dimensions) and you assume that the whole top row is covered with
enemies, and in the input you're given the number of polygons and the
points of the corners of them, work out how many enemies you can
--

What I ended up doing was creating a struct representing a polygon. It
stored the number of points needed to describe the polygon (which was
part of the input data), it had an array of all the x coordinate
values inputted for this particular polygon and stored also the
smallest and largest x value in the array. The reason I didn't store
the y coordinate is because it's not needed in my algorithm (which I
believe is correct, would have been fast enough had I managed to code
it properly...).

Once you've stored all the input into an array of ships (I declared my
type as struct ship {...} ships [10^5 + 2] you sort the ships[] from
ship with the lowest x coordinate to the highest (ie by the ship's sx
[smallest x] increasing).

Then, essentially you sweep from the leftmost ship to the rightmost
ship. You find the difference of each ship's smallest and largest x
coordinate and subtract it from the variable, nfire (the number of
enemies you can destroy which starts off as the width inputted) and at
the end of the algorithm you output nfire.

The catch is when one ship is in front of another. Or, one ship's x
coordinate is in between another ship's smallest and largest x
coordinate. In this case, subtracting differences of smallest and
largest values from nfire wouldn't work because there will surely be
test cases where the ships 'overlap'. So - that's why I wantED to sort
my ships array. Continually searching through each ship for similar x
coordinates would timeout. A maximum of 10^5 ships can be described
and such an algorithm would take O(nships^2) which is unusable,
considering the assumption that a computer can process approximately
10^8 (but really it should be 3 * 10^8 but we like powers of ten)
instructions per second (and the time limit in most problems in this
olympiad are 1 second). So I thought the inbuilt qsort() would work
but I couldn't get it to work.

Let's simplify the problem before I get the full problem statement
again (can't access it outside the competition times anymore until
sometime) and my code which I left saved on the school network.

struct ship {
int sx;
} ships[10^5];

fscanf()....//into ships.sx

qsort(ships, 10^5, //comparison function//);

How do I get qsort to sort the array of structures accordign to sx?

Thanks
Albert

Albert, Feb 19, 2009

2. ### CBFalconerGuest

Gordon Burditt wrote:
>
>> Once you've stored all the input into an array of ships (I
>> declared my type as struct ship {...} ships [10^5 + 2] you
>> sort the ships[] from ship with the lowest x coordinate to the
>> highest (ie by the ship's sx [smallest x] increasing).

>
> You do realize, don't you, that 10^5 as a C expression is not
> 10000 but a much smaller number? ^ is not an exponentiation
> operator in C. If you declared your array as somestruct[10^5],
> you're going to have a massive array overflow if you read in
> 10000 data points.

Who, may I ask, is 'you'?

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>

CBFalconer, Feb 21, 2009

3. ### AlbertGuest

I wrote:
> Let's simplify the problem before I get the full problem statement
> again...[M]y code [was] saved on the school network*
> [snip]

The 'full problem statement' and the code which I have since typed up

Note that the code currently deals with the input only. I've been
trying to divide this program into several functions and I'm trying to
get the design right for now.
I've been fiddling around with header files and #include's; I can't
get the files to all compile because I don't really understand how all
these declartions work across multiple files. Could you please suggest
as to how to split the current source code into files and how to
#include them in each of the files?

@Richard: Thanks for the code; I got three out of 20 test cases
correct without a sort (and that O(n) algorithm has been putting me
off lately) since I had the correct algorithm, but strictly given non-
overlapping polygons. I was expecting to have a problem in coming up
with slow algorithms but instead I couldn't get a sort to work for a
correct AND a O(nlog(n)) algorithm!

@Burditt: Actually I didn't realise that during the contest. I think
that's why my results said (for around the first 10 cases) my program
generated either the incorrect answer or that it crashed...

@CBFalconer: Is that a rhetorical question?

*I saved my source files along with a temp copy of Dev-cpp portable in
the C:\ during the contest; logging off automatically wiped (and
wipes) any changes made on a school computer. I forgot to keep a copy
of my original source file on my USB :|

Thanks a lot,
Albert

Albert, Feb 28, 2009
4. ### AlbertGuest

Albert, Mar 1, 2009
5. ### Nate EldredgeGuest

Albert <> writes:

> When I try to compile each of the .c files at
> - why?

main.c should #include "setup.h". The other files compile fine for me.

What errors do you get, what compiler are you using, and how are you
running it? There might be something wrong in that process.

Nate Eldredge, Mar 1, 2009
6. ### Ike NaarGuest

Ike Naar, Mar 1, 2009
7. ### AlbertGuest

Nate Eldredge <> wrote:
> main.c should #include "setup.h".  The other files compile fine for me.

#include "setup.h"
to main.c

> What errors do you get what compiler are you using, and how are you

running it? There might be something wrong in that process.
gcc errchk.c
/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
reference to `WinMain@16'
collect2: ld returned 1 exit status

gcc main.c
C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x3a): undefined reference to
`open_file'
C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x48): undefined reference to
`setup'
collect2: ld returned 1 exit status

gcc setup.c
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0x5b): undefined reference
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xa2): undefined reference
C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xb4): undefined reference
/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
reference to `WinMain@16'
collect2: ld returned 1 exit status

Albert, Mar 1, 2009
8. ### Nate EldredgeGuest

Albert <> writes:

> Nate Eldredge <> wrote:
>> main.c should #include "setup.h".  The other files compile fine for me.

>
> #include "setup.h"
> to main.c
>
>> What errors do you get what compiler are you using, and how are you

> running it? There might be something wrong in that process.
> gcc errchk.c
> /mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
> reference to `WinMain@16'
> collect2: ld returned 1 exit status

Running `gcc' on a file without other arguments tries to compile that
file into its own program. None of those files constitutes a complete
program by itself, which is why this doesn't work.

Try

gcc -o myprog.exe errchk.c main.c setup.c

Nate Eldredge, Mar 1, 2009
9. ### Ike NaarGuest

In article <>,
Albert <> wrote:
>gcc errchk.c
>/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
>reference to `WinMain@16'
>collect2: ld returned 1 exit status
>
>gcc main.c
>C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x3a): undefined reference to
>`open_file'
>C:\WINDOWS\TEMP/cceqbaaa.o:main.c.text+0x48): undefined reference to
>`setup'
>collect2: ld returned 1 exit status
>
>gcc setup.c
>C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0x5b): undefined reference
>C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xa2): undefined reference
>C:\WINDOWS\TEMP/ccuibaaa.o:setup.c.text+0xb4): undefined reference
>/mingw/lib/libmingw32.a(main.o):main.c.text+0x104): undefined
>reference to `WinMain@16'
>collect2: ld returned 1 exit status

Try this:
gcc main.c errchk.c setup.c

Ike Naar, Mar 1, 2009
10. ### AlbertGuest

Nate Eldredge wrote:
> Try
>
> gcc -o myprog.exe errchk.c main.c setup.c

I just did. Your suggestion worked. Thank you.

Albert, Mar 1, 2009
11. ### AlbertGuest

Now I need a
struct mship ms[MAXMSHIPS+1] that setup() and main() can access
instead of a local array that only setup() manipulates. How do I get
the external declarations and definitions right?

Albert, Mar 1, 2009
12. ### Barry SchwarzGuest

On Sun, 1 Mar 2009 12:47:53 -0800 (PST), Albert
<> wrote:

>Now I need a
>struct mship ms[MAXMSHIPS+1] that setup() and main() can access
>instead of a local array that only setup() manipulates. How do I get
>the external declarations and definitions right?

No external declarations needed. Define ms in main and pass it as an
argument to setup. If main and setup are in different translation
units, define struct mship in a header and #include that header in
both source files.

--
Remove del for email

Barry Schwarz, Mar 2, 2009
13. ### AlbertGuest

Barry Schwarz wrote:
> Define ms in main and pass it as an argument to setup.

I've now done that.
In the first for loop in setup.c, will ms.left = INT_MAX;
become (ms+i)->left = INT_MAX?

Thanks
Albert

Albert, Mar 3, 2009
14. ### Ben BacarisseGuest

Albert <> writes:

> Barry Schwarz wrote:
>> Define ms in main and pass it as an argument to setup.

>
> I've now done that.
> In the first for loop in setup.c, will ms.left = INT_MAX;
> become (ms+i)->left = INT_MAX?

No need. I'd use the first form always.

--
Ben.

Ben Bacarisse, Mar 3, 2009
15. ### AlbertGuest

Ben Bacarisse wrote:
> Albert <> writes:
> > In the first for loop in setup.c, will ms.left = INT_MAX;
> > become (ms+i)->left = INT_MAX?

>
> No need.  I'd use the first form always.

Is it the same???

Albert, Mar 4, 2009
16. ### Barry SchwarzGuest

On Mon, 2 Mar 2009 23:21:23 -0800 (PST), Albert
<> wrote:

>Barry Schwarz wrote:
>> Define ms in main and pass it as an argument to setup.

>
>I've now done that.
>In the first for loop in setup.c, will ms.left = INT_MAX;
>become (ms+i)->left = INT_MAX?

Without any context (most of aren't going to bother remembering the
details of your post from days ago), the answer is who knows.

ms is defined to be *(ms+i) but simply substituting one for the
other runs afoul of precedence and associativity. The compiler is
smart to figure it out so that the expression ms.left will be
evaluated as (*(ms+i)).left. I think this is equivalent to your
expression (ms+i)->left. Whether the generated code tries to do it
this way is an implementation detail.

--
Remove del for email

Barry Schwarz, Mar 4, 2009
17. ### Ben BacarisseGuest

Albert <> writes:

> Ben Bacarisse wrote:
>> Albert <> writes:
>> > In the first for loop in setup.c, will ms.left = INT_MAX;
>> > become (ms+i)->left = INT_MAX?

>>
>> No need. Â I'd use the first form always.

>
> Is it the same???

Why don't you tell me what you think each one means. I find a diagram
helps, but drawing in Usenet posts is a pain.

--
Ben.

Ben Bacarisse, Mar 4, 2009